419.1

250

undoのあるコマンド列が与えられるので、最終的な状態を答えよ、という問題。

前から見て行って、undoがあったら該当するコマンドの直前の状態に戻す、という方針が一つ。後ろから見て行って、undoがあったら該当するコマンドまでスキップする、という方針がもう一つ。

500

K人でN個の石の状態からNimをするとき、勝つ可能性のある人のリストを答えよ、という問題。ただし石の個数に応じて取れる石の数が決まる。

必ず勝てるならそのように行動し、勝つ可能性があるなら、勝つ可能性のある手からランダムに選び、そうでなければ全部の手からランダムに選ぶ、というルーチンを着実にシミュレーションするだけ。DPで下から組んでいく。

1000

すべてのノードが高々一通りの閉路にしか含まれないグラフで、ノードのPermutationは何通りあるか答えよ、という問題。

すべてのノードと枝について、グラフを再帰的に辿って、どのノードが同じトポロジーかを調べて、同じグループ内でPermutateするような感じ？と適当に書き残しておく。