396.1

実装と数学。

250

ある文字列が周期K以下の周期的な文字列になるように書き換えたい。最小の書き換え文字数を答えよ、という問題。

周期全部について調べる。周期が決まれば、最初の数文字を拾って、周期ごとに文字数カウントをして、全文字数から最大出現文字数を引いてやる。後はそれを足しこんでいく。

500

二次元盤面上に黒い石が並んでいる。上下左右でつながっている黒い石を一つの塊として見たときに、塊内の黒い石を二つ任意に選んだときに、黒い石だけ辿って移動して、マンハッタン距離で到達できるようにしたい。最終的な黒い石の配置を答えよ、という問題。

要は、同じ行または同じ列にある二つの同じ塊内の黒い石で挟まれる領域には白い石があってはいけない、ということなので、それに従って更新するだけ。

1000

Nimをする前に交互にいらない山を除去する操作を一度ずつ行う。先手が必ず勝つには、最低いくつの石(除いた山の合計値)を除く必要があるか答えよ、という問題。

たとえば、先手はどれか一つの山以外を全部除去してしまえば必ず勝てることが保証されている。この場合は一番でかい山を残せばいい。(これは割とどうでもいいけど。)

最終的には、後手がどうやってもXORが0になるような山の残し方をできないようにしてやれば良い。これは二進数で見たときの各桁を次元と見て、直交基底を作ればいいことに相当する。後は、極大(要素数ではなく二進数と見て和が最大)なものを見つけてやれば良い。

ここで、ある要素を追加して直行でならなくなる状況において、一つ追い出すのであれば、より小さいものを追い出すことが望ましい。二進数で考えたときの大小関係が重要なので、一番重みの大きいビットから計算させていけば良い。つまりソートして大きい順に基底に加えていって、直行でなくなるヤツを片っ端から追い出せば良い。