こんにちは、ふるやん（@fuurya1223）です。
この記事は DP を練習したい競プロerに向けて作った下記の記事の通常コンテスト編です。
上の記事を読んでいない方は、そちらを先にご覧ください。
このページでは、AtCoder の通常コンテストの DP 問題について、DP 配列の持ち方などのヒントを記載しています。
ヒントから DP 配列を更新する漸化式を考えたり、DP 配列の表を実際に埋めてみたりして練習しましょう。
まだ問題追加の途中です。
見つけ次第、追加していきます。
DP問題と状態の持ち方一覧
300 点問題
ABC 129 – C「Typical Stairs」
状態の持ち方
$dp[i]=$ $i$ 段目にたどり着く方法の数
出力するもの
$dp[N]$
初期化
$dp[0]=0$
配る DP の場合； $dp[i]=0$
ABC 099 – C「Strange Bank」
状態の持ち方
$dp[i]=$ ちょうど $i$ 円引き出すための操作回数の最小値
出力するもの
$dp[N]$
初期化
$dp[0]=0$
ARC 060 – C「高橋君とカード / Tak and Cards」
状態の持ち方
$dp[i][j][k]=$ 先頭 $i$ 枚から $j$ 枚選んで合計を $k$ にする方法の数
出力するもの
$\sum_{1\le j\le N} dp[N][j][jA]$
初期化
$dp[0][0][0]=1$
$dp[0][*][*]=0$
400 点問題
ABC 118 – D「Match Matching」
状態の持ち方
$dp[i]=$ マッチを $i$ 本使って作れる数の最大値（を表す文字列）
桁数が異常に大きくなるので、整数型で保持できません。
そのため、数を文字列で管理します。大きい方の数（文字列）を返す関数を自作しましょう。
出力するもの
$dp[N]$
初期化
$dp[0]=$”$0$”
大きい方を返す関数の実装によっては空文字列で初期化しても良いかもしれません。
ABC 054 – D「Mixing Experiment」
状態の持ち方
$dp[i][j][k]=$ $i$ 番目までの薬品を使って、物質 A を $j$ グラム、物質 B を $k$ グラムだけ買うときの最小コスト
出力するもの
$\min_{j:k=Ma:Mb}(dp[N][j][k])$
初期化
$dp[0][0][0]=0$（薬品を買わずに物質 A を $j$ グラム、物質 B を $k$ グラムにすることはコスト $0$ で可能）
$dp[*][*][*]=\infty$（最小を計算していくため。最終的に $\infty$ のままだと、作れないという意味になる）
ABC 104 – D「We love ABC」
状態の持ち方
出力するもの
$dp[N][2]$
初期化
$dp[0][*]=0$
なお、遷移は結構難しいです。
ABC 122 – D「We Like AGC」
考察
ダメな文字列のパターンは「AGC」「A?GC」「GAC」「ACG」「AG?C」の 5 通りなので、「OK な文字列に 1 文字足して OK な文字列を作る方法」を考えるときは、元の文字列の末尾 3 文字だけ考慮すれば良いということが分かります。
状態の持ち方
$dp[i][c_1][c_2][c_3]=$ 長さ $i$ の OK な文字列のうち、末尾が “$c_1c_2c_3$” であるものの個数（$c_n$ は A, C, G, T をそれぞれ 0, 1, 2, 3 に割り当てる）
実装上は、「int A = 0, C = 1, G = 2, T=3;」などと定義しておくと便利です。
出力するもの
$\sum_{c_1}\sum_{c_2}\sum_{c_3}dp[N][c_1][c_2][c_3]$
初期化
長さ 0 で、後ろに何をおいても NG にならないような文字列が 1 つある、としたいです。
そのため、適当に「長さ 0 で、末尾が “TTT” の文字列が 1 つ、他は 0 個」として良いです。
$dp[0][T][T][T]=1, dp[0][*][*][*]=0$（$[*][*][*]$ は $[T][T][T]$ 以外のことです）
500 点問題
CODE FESTIVAL 2018 qual A – C「半分」
考察
2 で割る（切り捨て）は二進数表現で桁を 1 つ減らすことと同じ。そのため、数列 $A_i$ を、各要素の二進数での桁数 $D_i$ に置き換えて、「 1 つ選んで 1 引く（ 0 は 0 のまま）」という操作に言い換えられる。
最終的に全要素が 0 でない場合は、元の $D_i$ 列から合計で $K$ 引いたものが作れる。
最終的にいずれかの要素が 0 になる場合は、元の $D_i$ 列から、0 ができるように合計で $K$ 以下だけ引いたものが作れる。（差分は 0 の場所で消費できるため）
また、下記の DP テーブルの 2 つ目の添字について、$K$ まで必要が無いことが考察から分かる（考えてみましょう）。
状態の持ち方
DP テーブルを 2 つ持つ
$dp1[i][j]=$ $i$ 番目までから $j$ だけ引いてできる、全要素が 0 以外の数列の個数
$dp2[i][j]=$ $i$ 番目までから $j$ だけ引いてできる、いずれかの要素が 0 の数列の個数
出力するもの
$dp1[N][K]+\sum_{j=0}^K dp2[N][j]$
初期化
$dp1[0][0]=1$（ 0 番目は存在しないので、0 番目までに 0 は無いし引くこともできない）
他は 0
ABC 129 – E「Sum Equals Xor」
状態の持ち方
$dp1[i]=$ $a,b$ の上から $i$ 桁目までを決めたとき、いずれかの桁で $a+b$ における値が $L$ における値を下回るような決め方の個数を $10^9+7$ で割った値
$dp2[i]=$ $a,b$ の上から $i$ 桁目までを決めたとき、すべての桁で $a+b$ における値が $L$ における値と一致するような決め方の個数を $10^9+7$ で割った値
出力するもの
$dp1[|L|]+dp2[|L|]$（ただし $|L|$ は $L$ の二進数表記での桁数）
初期化
$dp1[0]=0,dp2[0]=1$
600 点問題
ARC 097 – E「Sorted and Sorted」
最終状態では、黒と白でソート済みになっています。
この最終状態を基準に考えていきます。
数は 1 減らして $0$ から $N-1$ までになるようにして考えます。
なお、以下の値を事前に計算しておくと遷移が書きやすいです。
- 黒 $i$ より右にある $j$ 以下の黒の個数 $bb[i][j]$
- 黒 $i$ より右にある $j$ 以下の白の個数 $bw[i][j]$
- 白 $i$ より右にある $j$ 以下の黒の個数 $wb[i][j]$
- 白 $i$ より右にある $j$ 以下の白の個数 $ww[i][j]$
状態の持ち方
$dp[i][j]=$ 最終状態の先頭 $i+j$ 個目までにおいて、黒 が $i$ 個、白が $j$ 個置かれているようにするための、黒 $i-1$ 以下と白 $j-1$ 以下の間での swap 回数の最小値
出力するもの
$dp[N][N]$
初期化
$dp[0][0]=0$
700 点以上の問題
ARC 073 – F「Many Moves」（900）
考察
$dp[q][i][j]=$ $q$ 回動かした後に駒が $i,j$ にある状態への最小コスト
としたいですが、配列サイズが $QN^2$ だと大きすぎます。
$x_q$ への移動の直後には、片方の駒が必ず $x_q$ にあることが分かるので、駒 2 つの位置情報を持つのは無駄です。
$dp[q][i]=$ $q$ 回動かした後に駒が $x_q$ と $i$ にある状態への最小コスト
とすると、配列サイズを減らせます。
また、配列を使いまわして添字 $q$ を省略すると、配列サイズが $N$ になります。
1 回の更新の計算量が $\Omega(N)$ （線形以上）だと時間が間に合いませんが、更新の性質を考えて、DP 配列の持ち方を工夫すると高速化できます。
この問題は解説記事を書いています→ ARC073-F「Many Moves」とインラインDP
状態の持ち方
イメージは
$dp[q][i]=$ $q$ 回動かした後に駒が $x_q$ と $i$ にある状態への最小コスト
ですが、実際には添字 $q$ は省略され、さらに特殊な形のデータ構造を 2 本持ちます。
出力するもの
$\min_i dp[Q][i]$
初期化
0 番目のクエリを $A$ とし、もう一つの駒が $B$ にある状態でのコストが 0 であるとしておくと、計算が楽です。
$x_0=A$
$dp[0][B]=0$
$dp[*][*]=\infty$
配点なし
ARC 016 – C「ソーシャルゲーム」
解説記事を書いています→ ARC016-C「ソーシャルゲーム」
状態の持ち方
$dp[S]=$ すでに手に入っているカードの集合が $S$ である状態からコンプリートするまでの最適なくじ引き回数の期待値
出力するもの
$dp[\emptyset]$（$\emptyset$ は全要素の集合。集合を二進数で表現するなら $0$ ）
初期化
$dp[\Omega]=0$（$\Omega$ は全要素の集合。集合を二進数で表現するなら $2^N-1$ ）
特になし（メモ化再帰で実装する場合は未計算の部分に負の値など入れておきましょう）
ARC 057 – B「高橋君ゲーム」
状態の持ち方
$dp[i][j]=$ $i$ 日目までに勝率が上がった日が $j$ 日あるような勝ち方のうち最小の勝数
出力するもの
$dp[N][j]\le K$ となる $j$ の最大値
初期化
$dp[i][0]=0$
$dp[1][1]=1$
$dp[*][*]=\infty$
ABC 008 – D「金塊ゲーム」
空間が広いですが、クレーンの個数 $N$ が小さいので座標圧縮をします。
状態の持ち方
$dp[l][d][r][u]=$ 左下を $(l,d)$、右上を $(r,u)$ とする長方形が残った場合の、その領域で取れる金塊の最大個数
出力するもの
$dp[0][0][H-1][W-1]$
初期化
特になし