競プロ典型90問 023 満点の想定解法の解説

Avoid War（★7）

023–04b.cppを解説する。

横一列の各マスに情報を入れる

前準備で横一列の各マスに情報を入れるがこれが結構多い。

前準備1

cnt[j]
jの場所を基準にして状態がいくつあるか

state[j][idx]
jの場所を基準にしたidx番目の状態

Map[j][state]
jの場所を基準にした状態stateは、jの何番目か、そこには置けるか

少しややこしいのが j の場所を基準にした状態には j に置いたものは含まないこと。

cnt[j] は、最終的に j の場所を基準にして状態がいくつあるか。また、カウントの途中では現在値として使用する。

前準備2

各マスの、各状態について以下を設定する。図では2行あるが、書き込みは1行(図で言うと6回)である。ここはマスの添字が i になっている。

t0
そのマスに置かなかったときの状態

t1
そのマスに置いた時の状態

nex0[i][j]
そのマスに置かない状態は、次のマスの何番目の状態か

nex1[i][j]
そのマスに置いた状態は、次のマスの何番目の状態か。そのマスに置けないなら-1

DP部分

dp[i][j][k]
(i, j)の場所を基準にしてk番目の状態の置き方をするものが何通りか

処理の流れは

1. dp[0][0][0]=1 開始マスより前には何も置かない状態がひとつある
2. (0, 0)に置かない情報を dp[0][1][...] に書く
3. (0, 0)に置けるなら置く情報を dp[0][1][...] に書く
4. 繰り返し
5. (H-1, W-1)を調べて dp[H][0][...] に書く
6. dp[H][0][...] を調べて出力