GCJ 2015 Round 2

例年に比べると簡単な気がする。

A

二次元盤面上に矢印が書いてあって、その方向に進まないといけない。どの矢印を開始点にしても、無限に移動し続けられるように、矢印の向きを変えるとき、最小いくつ変更する必要があるか答えよ、という問題。

取り敢えず、矢印の先に矢印があれば、その矢印は放置しても良さそう。なので、矢印の先に矢印がないなら、適当に向きを変える必要がある。後は、変えた数をカウントするだけ。矢印がなければできない。

B

特定の温度で、特定の量の水がいくらかある。これらを好きなように混ぜて、できるだけ多くの目的の温度の水にしたい。そのときの量を答えよ、という問題。

温度はキープしないといけないので、既にその温度なら好きに使える。温度が違うなら、高いのと低いのを混ぜる必要がある。取り敢えずたくさん同じ温度にしたいので、できるだけ温度が目的のに近い方から貪欲に使うのが良い。後は、混ぜるのがいなくなるまで頑張るだけ。

C

Aグループに属しているものと、Bグループに属しているものが与えられる。それとは別にAグループかBグループか分からないけれど、同じグループに属している情報が与えられる。両方のグループに属している要素の最小数を答えよ、という問題。

同じグループに属している関係を辺にしてグラフを作れば、AグループからBグループに到達できることで、両方に属していることになるので、やるだけ。グラフが結構大きくなるような気はするものの、比較的疎なグラフなので、最小費用流でも通った。

D

左右のみつながった2次元グリッドについて、各グリッドが、書かれている数字と同じ数だけ同じ数字と隣接している、という条件を満たす数字の書き方は何通りあるか答えよ、という問題。ただし、左右はつながっているので、回転して同じになるものは同じとみなす。

2を横に並べるか、3を横に二行並べるか、後は、1が2個くっついているのを回避するように2を敷き詰めるか。後者は1の関係で回転すると一致しないケースが作れたりするので、うまくそれを頑張りましょう、という問題。やること自体はとても簡単っぽいが、なかなかにやっかい。