第１０回 日本情報オリンピック 予選

問題１〜問題５

省略。

問題６

「JOか否か」だけを気にするとき、
ある行に生じうるパターンは約10000通り。（フィボナッチ）


dp[20][10000]を宣言。
dp[i][j]を、i行目がパターンjになるような、0〜i行目の埋め方の場合の数と定義。
埋める変数が20*10000個、一つ埋めるのに10000*20。全部で400億。


……予選だからこんな手抜き解法でも通ってしまうよね？　いいの？
と思ったけれど、これはこれで、そこまで簡単でもないからいいのかな。


（追記）
フィボナッチではなく、2^20通りと思ってしまうと、
20*20*(2^20)解法を使わなければ間に合わない。
つまり、フィボナッチ or 一マスずつ進める解法に気づけば通る仕様か。理解。