511.1

250

見てない。

500

0から511までの数字のいずれかが書かれたカードが数枚ある。交互に1枚ずつ選択していき、登場したカードの論理和が511になった方が負けであるとき、どちらが勝つか答えよ、という問題。

ただのゲーム木探索。ただし、現時点での論理和の値から、ゲームを何ターン遅延させられるかが分かるので、どちらのプレイヤーが必ず論理和を大きくしなくてはならないかが決まる。なので、論理和が大きい方から、プレイヤーの手番が決まれば、どちらのプレイヤーが勝つかを決定できるので、DPするだけ。

1000

1次元のライフゲームの一部が伏せられた状態が与えられる。Tターン後にK個以上のセルが生き残っている配置は何通り可能か答えよ、という問題。

二つ並んで生きているか、二つ並んで死んでいるか、のときには次のターンでも状態が変わらない。なので、二つ同じ状態が並んでいる位置をDPで決めていけば良い。交互になっている場合、同じ数ならば数は変わらず、一つ違う場合(二つ以上違うことはない)多い方が毎ターン一つずつ増加していく。(もちろん交互に並んでいる領域の長さで停止する。)これをDPすれば通ると思う。

途中で必要数以上生きていることが分かれば、残りは何が来てもいいはず、ということもできなくはないけれど、Kが十分に大きいと効果なさそうなので、単純にDPだけで通るんじゃないかなぁと。(後でちゃんとやる。)