493.1

450の割には意外と通っていないみたい？

300

N個のものの中に一つだけ白いものがM番目に入っている。白いものを含む連続するK個を選択して、逆順に並び替える、という操作を行って、L番目に移動させるという行動を交互に行う。目的を達成した方が勝利とするとき、最適に行うとしてどちらが勝利するか。

同じ手順をやって返すことができるので、相手が勝てる状態で渡してくれることは起きない。つまりお互いの初手だけを考慮すれば良い。先手は自分が動かして勝てるなら勝ち、後手は相手がどのように動かしても勝てる方法があるなら勝ち。それ以外は引き分け。

450

見てない。

1000

テーブルの上に連続した凸形状にものを置くことを考えるとき、何通りの置き方が可能か答えよ、という問題。テーブルはセル上になっており、凸形状とは、ある点とある点が同じxないしy座標の場合、二点間には置いていない場所が存在しないことである。

xないしy軸に沿ってDPすれば良さそう。ものが置いてある区間と、さらに過去にそれよりも大きい領域が使われていたかどうかを区間の両側について考慮する。(もし使われていれば、これから使う際には現在の区間と競合してしまう。)状態の更新がかなり面倒で、何も考えずにやるとN^2かかってしまい、DPのテーブルがN^3の大きさで、全体がN^5になって終わらない。これは一つ前の状態から遷移可能なものの合計を計算しているためで、各ステップごとに合算したものを別のテーブルに保存するようにすれば、N^4くらいになるんじゃないかなぁ、という感じ。実装が大変なので検証は全然していない...。