Google Code Jam 2010 Round 1A

寝坊して、45分くらい遅刻して、15分前には諦めてた...。
適当にやったのが落ちたけど、通過する程度のスコア。

A

NxNの盤面に二色の石が置かれているので、これを右寄せにする操作をした後に、K個以上並んでいる色があるかどうか答えよ、という問題。

愚直に実装するだけ。左寄せにすると結果が違うので注意する。

B

N個の整数の配列について、挿入・削除・修正、の処置を行い、隣接する要素の差分がMを超えないようにする。このときの最小のコストを答えよ、という問題。

削除だけは独立した操作で、挿入については修正と連動している。今現在の値を覚えておいて、次の値を消すか、修正するかを考える。修正する場合は取り得るすべての値について吟味し、もし差分がMを超えるようならば、適当な数だけ値を挿入する。これを最後まで繰り返せば良い。典型的なDPの問題。

C

二つの整数AとBについて、交互に好きな方から他方を任意の回数だけ引く、という処理を行う。先に0以下の数字を作った方が負け。kのとき、AとBの組が複数与えられるので、何通りの勝てる組があるか答えよ、という問題。

1M個程度の大きさ1M程度の区間グラフで組が与えられるので、勝てる範囲を計算していく。fibのパスの途中で勝ち負けが反転するとかがあるので、その辺りを細かく実装していけば解けそう。