AOJ 2741 : インビジブル
ゲーム系の問題。
困るのはスタックで配列で持っていたりすると解けない。
しかしよく考えてみると「最後に-1を出したのはいつか」
を持てばスタックの状態を表現できる。
（これだけでは不十分で最後にパスしたインデックスを
高速に求められるようにしておく必要があるが
これはTreeMapを使えば実装できる）
memo[turn][pass][index1][index2][block1][block2] :=
turnの手番でpass回パスして
互いのデッキのインデックスが
それぞれindex1, index2で、
相手のデッキのblock1, block2番目の後に
-1のカードが置いてあるときの
自分にとって価値が最大の点数
オーダーはギリギリ大丈夫だけど
これ以上は増やせない。
パスするときは、相手のblockインデックスか、
前にパスしたときの互いのインデックスの
大きいほうを取り出し、今指しているインデックスまで
足していき、点数を計算する。
このとき、点数計算を愚直にやるとさらに
O(n + m)かかってしまうので
あらかじめ累積和を取っておいてO(1)で
求められるようにしておく。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2311971#1
最初誤読していたり、埋め込んだバグを取るのが大変だったりで
解くのに3時間くらいかかりました・・・。半分ぐらいに減らしたい。
でも自力で解けたのは嬉しくて、図書館でやっていたのに
ACしたときはつい大声をあげてしまいました・・・。
