ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2741 - インビジブル

動的計画法(DP) メモ化再帰

問題
 提出コード

解法

ゲーム系で、ぱっと貪欲な解法がなさそうだったので、メモ化再帰をすることにしました。6次元DPです。
$dp[i][j][k][l][p][q]$ とし、それぞれの添え字が
$i:$ 先手が次にスタックにカードを置くとき上から何枚目のカードを置くか
$j:$ 後手が次にスタックにカードを置くとき上から何枚目のカードを置くか
$k:$ 次にパスが行われたとき、先手は直近で出した何枚分のカードが得点になるか
$l:$ 次にパスが行われたとき、後手は直近で出した何枚分のカードが得点になるか
$p:$ 次のターンはどちらか(0なら先手、1なら後手)
$q:$ 直前のターンまでで何回連続でパスをしたか
の状態のときに、これ以降のゲームで得られる得点の値とします。
$p = 0$ ならば、これ以降の遷移の中で値が最大のもの、 $p=1$ ならば、これ以降の遷移の中で値が最小のものをその時点での値にすればよいです。
初期値は、スタックが空の状態で、2連続パスが行われた場合にゲーム終了なので、
$dp[i][j][k][l][p][3] = 0$
としておけばよいです。スタックが空じゃない状態からパスを連続で行うことになるので、 $q=3$ になります。
また、 $a_{i} , b_{j}$ は0-indexedになおしておきます。

$p=0$ のとき
先手のターンです。まず、スタックにカードを置くパターンから考えていきます。
このパターンを考慮するのは、 $i$ が $n$ を超えていない、つまり山札がまだ存在している場合のみです。
もし、次に出すカードが妨害カード、つまり $a_{i}=-1$ の場合は、それ以降で次にパスした場合に後手が手に入れることができる得点は、今出した妨害カード以降の得点カードになります。よって、 $l=0$ になります。
よって、この行動による遷移先は、
$dp[i+1][j][k+1][0][1][0]$
となります。
もし、得点カードだった場合は、相手の得られる得点に変動はないので、
$dp[i+1][j][k+1][l][1][0]$
となります。
次に、パスするパターンです。
まず、スタックが空になるので、見るべき遷移先は、
$dp[i][j][0][0][1][q+1]$
となります。
加えて、 $(直近k枚の先手のカードによる得点) - (直近l枚の後手のカードによる得点)$
が加算されます。
この合計と、最初の2パターンのうちの片方(先手の山札が切れていたら存在しません)のうち、より大きい方が $dp[i][j][k][l][p][q]$ の最終的な得点になります。

$p=1$ のとき
後手のターンです。先ほどとほぼ同様なので、遷移先だけ書くと、
$b_{j} = -1$ のとき
$dp[i][j+1][0][l+1][0][0]$
$b_{j} \neq -1$ のとき
$dp[i][j+1][k][l+1][0][0]$
パスするとき
$dp[i][j][0][0][0][q+1]$
このパターンは、先ほどと同様 $(直近k枚の先手のカードによる得点) - (直近l枚の後手のカードによる得点)$ が加算されます。
こちらも、これらの中で最小値を求めると、 $dp[i][j][k][l][p][q]$ の値になります。

これらを利用して計算していき、 $dp[0][0][0][0][0][1]$ を求めれば答えになります。

感想

考察自体は結構はやかったのですが、例によってバグらせました。
この手の問題はよく見かけるので、パパっと解きたいところです。