552.1

ちょっと実装が重いとすぐこれだ...。

250

三色のボールがそれぞれいくつかずつあって、同じ色が隣り合わないように一辺の長さがNの正三角形に並べることを考える。このとき正三角形はいくつ作れるか、という問題。

基本的には同じ数ずつ必要だが、時々1個余分に一つ用になる。正三角形の数と作れるかどうかの関係は単調なはずなのでバイナリサーチしてやる。必要な最低個数を割り当てた後に、余分なのを捻出できるかどうかでやるだけ。

500

二次元グリッド上に矩形を重ならないように二つ取る。内部に配置されている二種類のものの差分が指定された数以内のときに、最大の個数を囲いたい。最大の個数を答えよ、という問題。

取り敢えず一つの矩形を選択してしまえば、後はその矩形と重ならない領域4つに分割して、それぞれについて、差分の範囲と最大の個数を何らかの形で記憶しておいて取り出すだけ。

データ構造弱いな...。

900

見てない。