396.1

250

文字列Sが与えられるので、S[i]=S[i+p]なる周期的な文字列にSを書き換えるとき、pが与えられた値以下にするには、何文字書き換える必要があるか答えよという問題。

周期が決まれば、N文字おきに文字を拾い、その中で一番多く出てくる文字に変更することで、周期的な文字列への変換に必要な最小の数が求まる。これを可能な周期長について試して、一番小さいものを答えれば良い。

500

白黒画像が与えられる。黒い点は隣接する点はつながっているとして、つながっている点がグループをなす。グループ内の任意の二点について、黒い点を通る移動距離の最小値がマンハッタン距離に等しくなるように、白黒画像を変更せよ、という問題。

結局同じグループに属する二点がx軸ないしy軸に平行な直線に乗る時に、間に白い点があってはいけない、ということなので、間を黒い点で埋めていく。この仮定で、グループが合併したりするので、収束するまで繰り返せば良い。

かなりいい加減なルーチンで実装したものの、実行速度は問題にならなかった模様。

1000

Nimの前に、好きな山を全て取り除いて良い、という処理をお互いに行う。このとき、先手側が勝つためには、いくつ取れば良いか答えよ、という問題。

山集合のうち、すべての部分集合が先手必勝となるように山を取り除く。つまり、全ての部分集合が先手必勝になるもののうち、最大のものを求めればよい。一次独立な山を追加して回る、ということをやれば良いらしいが、大きい方から順に入れていってよい、というのが余り直感的ではない気がする...。

Nimの必勝法知らない時点で解けない問題。まじめにDPとかで解けるかどうかは検討した方が良さそう。数学的知識がない時点でダメだなぁ...、という感じ。