593.1

時間足りないのは純粋に頭悪いから。

250

六角形グリッドの適当な点に色を塗っていく。隣接する点には同じ色にならないように指定されたマスを塗るとき、最低何色必要か答えよ、という問題。

3色あれば十分なので、それより少なくできるか調べる。2色でDFSすればいいっぽい。綺麗にコード書けない...。

450

値がA以上B以下のものがいくつかあって、二つの集合に分けることを考える。二つの集合の合計値の差分として可能な最大値ができるだけ小さくなるように分割するときのその値を答えよ、という問題。

一つ目の集合がX以上Y以下で、二つ目の集合がP以上Q以下になるように分けるとすると、X<=Pを仮定してやれば、X<=P<=Qになるで、Yがどこに入るかを考えてやる。目的の値を最小化するためには、X<=P<=Q<=Yになるようにするのが最適と分かる。で、Xが大きくなったらYを小さくしてやらないといけなくなることから、結局A+Bの値を考慮して二つの集合に分割してやれば良い。

ということで、可能な分割を全部調べてやって、最適になるものから、最終的に目的の値がどうなるかを算出してやればおしまい。

1000

見てない。