TCO 2013 Round 1A

Qualification相当のため、問題自体は比較的やさしめ。平均的なDiv2よりは難しいとは思うけれども。

250

整数配列が与えられるので、全部の要素の最大値と最小値の差が1になるように値を書き換えるとき、書き換える量の最小値を答えよ、という問題。

最終的な値の範囲を決めて、そこに到達するのに必要なコストを全部計算してやるだけ。

500

穴がいくつか開いている状態で、等距離ジャンプを繰り返して穴に落ちないようにしたい。ジャンプの距離の最小値を答えよ、という問題。

取り敢えずジャンプの距離を小さくしたい。もし全部の穴を大幅に飛び越しているのなら、ジャンプ距離をちょっと短くすれば、穴の端に近付くはず。つまり、最小距離のジャンプでは、どこかの穴の端にぎりぎり到達するようになっているはず。後はジャンプ回数をできるだけ大きい方から試してやって、他の穴に落ちないのを確認してやれば良い。

枝をかるために、穴の幅の最大値以上のジャンプじゃないとダメ、とかやらなくてもいいことしてた。精度に絶対の自信がないのであれば、doubleでやるのは避けた方が良いと思います。

1000

二次元トーラス上の各マスに矢印が書かれている。矢印に従って移動した結果、必ず最初の位置に戻ってくるように矢印を書き換えることを考えるとき、最小の書き換え個数はいくつか答えよ、という問題。

要は出ていく矢印の個数は一個で、入ってくる矢印の個数も一個になるように調整しつつ、できるだけ矢印を動かさないようにしたいということ。なので、出ていく方と入ってくる方にマスを分割して考えて、二部グラフマッチングにしてやると、良い。後は矢印の向き変更を伴う方にはコストを乗せてやる必要があるので、最小重みの二部グラフマッチングになる。最小費用流やるだけ。