631.1

愚直にやるだけ気味なセット。

250

N*Nのマス目が白か黒に塗られている。特定の行を白または黒に染める操作を行って、どの列を見ても同じ色がN/2+1個以上続いていないようにしたい。必要な操作の最小回数を答えよ、という問題。

とにかく真ん中の二列を白と黒に塗ってしまえば、条件は満たされるので、最初から条件が満たされているか、特定の一列を白または黒に塗ると条件が満たされるかを調べるだけ。

500

なんかモノが配置されている場所と個数の配列が与えられる。それぞれのモノは独立に、場所を高々K移動することができる。この状態で、最終的にモノが複数個配置されている場所の個数を最小化したい。その個数を答えよ、という問題。

とにかく、一個ずつ配置できるならそうして、そうでなければ一箇所にまとめる、という感じ。座標でソートしてやって、一個ずつなら左側に、まとめるなら右側に、というような感じ。細かいことは考えるの面倒なのでDPやれば通る。

1000

適当に木をつけかえつつ、木の上の二点間の枝のうち最大重みのものの重みを返却するという操作を繰り返せ、という問題。

ライブラリゲーにしか見えなかったので、やらずに寝た。