534.1

簡単な問題を正確にすばやく解きましょう、という問題セット...。

250

N個のマスが一列に並んでいるボードにいくつか石が置いてある。石は右側のマスが空であるか、右とその右に石があって更にその右のマスが空であれば、その空のマスに移動できる。一番右端のマスに到達した石は除去される。交互にプレイするとき、最後に移動できなくなった方が負けというルールで、どちらが勝つか答えよ、という問題。

探索するだけ。ある盤面で勝てるかどうかは、可能な選択のうちどれかで勝てないこと、というのを小さい盤面から順に決めていくだけ。右端のマスの石が除去されるのが非常に厄介なだけ。

500

ある整数を与えられた整数のリストの部分集合を使って積算だけで表現したい。部分集合に入れることのできる要素は互いに素であるものとする。このとき、部分集合の選択方法は何通りあるか答えよ、という問題。

まず、作りたい整数を割った商との最大公約数が1にならないような整数をすべて除去する。こうすれば、計算過程で互いに素であるかどうかの判定はいらなくなる。後は残った整数に対して、1にならないように注意しながら、他の整数との最大公約数を求めていく。最後に残った1以外の値は、作りたい整数を作るときに1度だけかけないといけない値になる。これの倍数はこれで割って、同様の作業を繰り返すと、同様の整数がいくつか出てくる。これらの積が作りたい整数になるとき、答えが存在することになる。後はDPで全パターン試すだけ。

1000

文字列Aを変換して文字列Bを作りたい。変換は隣接する文字のスワップか、ある文字の書き換えのどちらかしかできない。最小変換個数を答えよ、という問題。

AとBで違う文字の個数が上限値。スワップをどう使うか、という問題。スワップする場合、長さNの区間を一連のスワップ作業で解決しようと思った場合、N-1が下限値になる。(全部違う文字なので、最後の一回以外は一文字ずつしか合致しない。)つまり、ある座標を決めて、長さNの区間をN-1回のスワップで解決できるような、最小のNを書く座標に求めてやれば良い。複数のスワップで実現できるものは、これを有限回組み合わせればできる。後はDPするだけ。

ある区間がスワップで合致させられるかは、AとBの最初の文字と、次の文字を比較して、Aに合致する文字がBに出てくるか、Bに合致する文字がAに出てくるかする限り続けてやる。同時に満たされた場所がスワップの完了地点。ちなみに同じ文字が出てきた場合は打ち切って良い。(それを除いたN-1文字を書き換えれば済むので。)