560.1

ひより過ぎだけど、通さないことには話にならないので、しばらくは現状維持予定。

250

キーに割り当てることのできる文字数と、各文字の使用回数が与えられるので、打鍵回数最小になるような割り当ての時に必要な打鍵回数を答えよ、という問題。

頻度が多いものから順に割り当てていくだけ。やるだけ。

500

格子点がいくつか与えられたときに、1x1の正方形の中心に新しい点を置いて、既存の点を消すという処理を繰り返す。最終的な盤面が与えられるので、最初の盤面から繰り返された処理の回数の最大値を答えよ、という問題。

たとえばK回処理が行われたとすると、一辺が(K+1)の正方形の中にびっしり点があるときに限り、その中央に一個点が残る。逆に言うと、最終的な盤面に存在する点の周りにびっしりと点を敷き詰めてやれば、状態をさかのぼることができる。その後で新しい点ができていないことを確認すれば良く、また新しい点ができるかどうかがコロコロ変わることはないので、二分探索で十分。

正方形を敷き詰めて、その中に新しい正方形があるかどうかの判定は座標圧縮とかでもいいのかも知れないけれど、一番単純にやるなら、敷き詰めた正方形の上下左右を眺めてやれば十分。つまり最終的な盤面に存在する点の上下左右に新しい点ができないようにすれば良い。最初からある点と分けて考えるので、若干面倒。

1000

見てない。そろそろ見たい。