こんにちは、ふるやん（@fuurya1223）です。
この記事は DP を練習したい競プロerに向けて作った下記の記事の TDPC 編です。
上の記事を読んでいない方は、そちらを先にご覧ください。
このページでは、AtCoder Typical DP Contest の各問題について、DP 配列の持ち方などのヒントを記載しています。
ヒントから DP 配列を更新する漸化式を考えたり、DP 配列の表を実際に埋めてみたりして練習しましょう。
まだ問題追加の途中です。
僕が解き次第、追加していきます。
DP問題と状態の持ち方一覧
AtCoder Typical DP Contest
TDPC – A「コンテスト」
状態の持ち方
$dp[i][j]=$ $i$ 問目までで $j$ 点を取る方法が存在するか（bool）
出力するもの
$dp[N][j]$ に存在する true の個数
初期化
$dp[0][0]=$ true
$dp[0][*]=$ false
TDPC – B「ゲーム」
両者が自分の得点の最大化を目指すと考えると難しいです。
最終的に両者の得点の合計が「すべてのものの価値の合計」という定数になることを利用して、すぬけ君は「すぬけ君の得点ーすめけ君の得点」を最大化しようとし、すめけ君はこれを最小化しようとする、と考えましょう。
状態の持ち方
$dp[i][j]=$ 左の山から $i$ 個、右の山から $j$ 個のものが取られた状態から開始するときの最適値
このような添字の定義をすることで、$i+j$ の偶奇を見ればどちらの手番か分かるようになります。
出力するもの
$dp[0][0]$
初期化
$dp[A][B]=0$（山が空の状態から始めると両者 $0$ 点で終わります。）
TDPC – C「トーナメント」
人を $0$ から $2^K-1$ までとします。
遷移がちょっと難しいです。
状態の持ち方
$dp[i][j]=$ 人 $i$ が $j$ 回勝つ確率
出力するもの
$0\le i\le 2^K-1$ のすべての $i$ について、$dp[i][K]$
初期化
$dp[*][0]=1$ （全員 0 勝はできる）
TDPC – D「サイコロ」
考察
$D$ が非常に大きいので、「$i$ 回振ったときに目の積を $D$ で割った余りが $j$ である確率」のような状態の持ち方が不可能です。
積について考えるので、サイコロの目に存在する素因数 $2,3,5$ の指数のみを考えれば良いですね。
$10^18<2^60$ なので、指数として考える値はそれぞれ $60$ 以下でよいです。
状態の持ち方
$dp[i][p_2][p_3][p_5]=$ $i$ 回振ったときに、出た目の積に含まれる素因数 $2$ の個数が $p_2$、$3$ の個数が $p_3$、$5$ の個数が $p_5$ になる確率
出力するもの
$D=2^a 3^b 5^c$ のとき、$\sum_{p_2\ge a, p_3 \ge b, p_5 \ge c}dp[N][p_2][p_3][p_5]$
初期化
$dp[0][0][0][0]=1$（0 回振ったとき、目の積を 1 とするので、素因数にいかなる素数も含まれない）
$dp[0][*][*][*]=0$
TDPC – E「数」
EDPC – S「Digit Sum」 と全く同じです。
TDPC – F「準急」
考察
下記のように状態を持つと、配列サイズが $NK$ になってしまい、メモリが足りません。
添字 $i$ を省略し、遷移の計算をうまく高速化すると、メモリも計算時間も $O(N)$ にすることができます。
状態の持ち方
$dp[i][j]=$ 駅 $i$ までの止まり方を決めたときに、$j$ 駅連続で止まっているような止まり方の個数
（具体的にこの配列を持つわけではないです）
出力するもの
$\sum_j dp[N][j]$
初期化
$dp[0][0]=1$（開始時点はまだ止まっていないので 0 連続停車）
$dp[0][*]=0$
TDPC – G「辞書順」
考察
DP 以外の考察が難しいです。
ここでいう部分列は連続している必要はありません。
また、別の位置にある同じ文字を使う場合、区別されません。（”abab” の部分列 “ab” を考えるとき、(1,2), (1,4), (2,4) のいずれを取り出したものかを考慮する必要はありません）
まず、答えが “Eel” になるか（部分列が $K$ 種類あるか）を考えます。
別の位置から同じ文字を選んで同じ部分列を作ることを回避したいです。
そのために「部分列を構成する際に、ある文字を選ぶとき、$s$ の中でとりうる最も左側の文字を採用する」というルールを決めます。
例えば、”cabcabc” という文字列から部分列 “ac” を作るときに、必ず「2 文字目の ‘a’ と 4 文字目の ‘c’ を使う」と決めます。「5 文字目の ‘a’ と 7 文字目の ‘a’」という選び方を不正とします。
このように決めると、”ac” の末尾に文字を付け足した “acb” を考えるとき、「4 文字目の ‘c’ 以降の最初の ‘b’」のみを考えればよくなり、場所の選び方が一意になります。
また、この決め方で「本来作れる部分列が作れなくなる」というような問題は発生しません。
こう考えることで、「各文字から、それより右側で最初に見つかる ‘a’, ‘b’, …, ‘z’ の位置まで矢印を伸ばす」という有向グラフを構成することができます。これはすでに頂点がトポロジカル順に並んだ DAG です。
したがって、「ある文字を先頭とする部分列の作り方」を末尾から DP で計算することができます。
$s$ の先頭にダミーの「先頭」を表す頂点 $0$ を追加しておけば、$0$ から始まる部分列の個数が、構成できる部分列の種類数になり、”Eel” 判定ができるようになります。
この DP 配列を使えば、 $K$ 番目を探すこともできます。
状態の持ち方
$dp[i]=$ $s$ の $i$ 文字目を先頭とする部分列の種類数
なお、$s$ の $0$ 文字目にはダミーの文字があると考えて、すべての部分列はこのダミー文字から始めないといけないとします。
出力するもの
$dp[0]<K$ なら “Eel”
そうでなければ、$K$ 番目の部分列を 1 文字目から順に構成して出力します。
初期化
特になし
TDPC – H「ナップザック」
考察
色の種類数の制約が厄介です。
気持ちとしては、下記のような状態の持ち方をしたいですが、そのままやると色の種類数に関する遷移が書けなくて失敗します。
$i$ 番目のものを採用したときに色の種類数が増えるかどうかを簡単に判定するため、始めにすべてのものを色でソートしておきます。
こうすると、同じ色は必ず連続して並びます。
遷移もちょっとむずかしいです。うまく高速化しましょう。
また、添字 $i$ を省略することでメモリを節約します。
状態の持ち方
$dp[i][j][k][l]=$ $i$ 番目までのものからいくつかナップザックに入れたときに、重さの合計が $j$ で色の種類数が $k$ で、最後に入れたものの色が $l$ であるような入れ方の価値の合計の最大値
出力するもの
$\max_{j\le W,k\le C,l}dp[N][j][k][l]$
初期化
$dp[0][0][0][0]=0$（空の状態では、最後に入れた色は 0 であるとします）
TDPC – I「イウィ」
考察
区間 DP です。
まず、「区間 $[l, r)$ を消し切ることが可能か」を考えます。可能な場合、$r-l$ は $3$ の倍数であり、可能な操作回数の最大値は $\frac{r-l}{3}$ です。
消し切れるか不明な区間について、その区間を最適に消していったとき、必ずいくつかの「消し切ることが可能な区間」と「消されない区間」に分割でき、一緒に消される “iwi” は連続する「可能な区間」に含まれます。
状態の持ち方
$dp1[l][r]=$ 区間 $[l,r)$ を消し切ることが可能か（bool）
$dp2[l][r]=$ 区間 $[l,r)$ についての最大操作回数
出力するもの
$dp2[0][|s|]$（$|s|$ は $s$ の文字数）
初期化
特になし
TDPC – J「ボール」
投げによって状態が変化しない可能性（DAG における自己ループ）がありますが、それは幾何分布の期待値を使って潰すしましょう。
状態の持ち方
$dp[S]=$ ものが残っている座標の集合が $S$ であるときの残り投げ回数の期待値が最小になるように投げるときの期待値
出力するもの
$dp[$ $x_i$ の集合 $]$
初期化
特になし（bit DP ゆえにメモ化再帰で書くので負の数を入れておくとよい）
TDPC – K「ターゲット」
考察
円でマトリョーシカを作るときの、採用する円の個数の最大値を求める問題。
すべての円は $x$ 軸上にあるので、円というより区間です。
$O(N^2)$ の遷移だと時間が間に合わないので、DAG を作って最長経路、という方針はダメです。
区間の左端が小さい順ソートしてから見ていくと、右端のみ考慮すれば良いので考えやすいです。
区間の左端でソートしておくと、採用する円が必ず「外側→内側」の順で並びます。
したがって、区間の右端についてはかならず減少列になります。
よって、区間の左端でソートしてから区間の右端を並べた列について「狭義単調減少する部分列の最大長さ」を計算すれば良いことになります。
なお、左端が同じであるような円を両方採用しないように、そのような円では右端が大きくなるように並べましょう。そうすると、狭義単調減少の制約から自然に除外されます。
結局、この問題は Longest decreasing subsequence (LDS) を計算するだけになります。 Longest Increasing subsequence (LIS) と同じなので、詳しくは LIS について調べてください。
状態の持ち方
$dp[i][j]$ = $i$ 番目までの要素をみたときに、長さ $j$ の狭義単調減少部分列を作るときの右端の値の最大値（どうせなら右端の値は大きいほうが良いに決まっている）
実際は、添字 $i$ は省略して配列を使いまわします。
出力するもの
$dp[N][j]<\infty$ となるような最大の $j$
初期化
$dp[0][*]=\infty$
TDPC – L「猫」
状態の持ち方
$dp[i][j]=$ 猫 $i$ までを並べるときに、猫 $i$ が自信より左側 $j$ 匹と距離 1 以内である（猫 $i$ との距離が 1 以下である最も右の猫が猫 $i-j$ である）場合の幸福度の合計値の最大
出力するもの
$\max_j dp[N][j]$
初期化
$dp[0][0]=0$
TDPC – M「家」
考察
時間制限が 8 sec です。
$dp[i][j]=$ $H$ 階の部屋 $1$ から $H-i$ 階の部屋 $j$ に降りる方法の数
としたいですが、$H$ の最大値が $10^9$ なのでダメです。
すべての階で同じ構造であることから、階ごとの遷移がすべて同じになります。
そのため、ダブリングなり何なりの計算方法が使えそうです。
なので、まず「同じ階の中で、同じ部屋を通らずに部屋 $i$ から部屋 $j$ に行く方法の数」を考えましょう。
ここに DP を使います。
同じ部屋を通ってはいけないので、「すでに通った部屋の集合」を状態に持ちましょう。
状態の持ち方
同じ階の中で考えます。
まず、部屋 $k$ に行く方法の数を数える処理について考えます。
$dp[S][j]=$ すでに通った部屋の集合が $S$ であり、現在部屋 $j$ にいる状態から、部屋 $k$ に行く方法の数
この DP を $0\le k\le R-1$ のすべての $k$ について行います。
（初期状態も変えるので、この DP を $R^2$ 回行います。）
出力するもの
「同じ階の中で、同じ部屋を通らずに部屋 $i$ から部屋 $k$ に行く方法の数」が
$dp[\{i\}][i]$（$\{i\}$ は $i$ のみを要素に持つ集合。二進数表現を用いると $2^i$）
で計算できます。
$R^2$ 回の DP の結果を用いて、$H$ 階の部屋 $1$ から $1$ 階の部屋 $1$ に行く方法の数をうまく計算しましょう。
初期化
特になし（メモ化再帰を用いるので負の数を入れておくと良いでしょう）
TDPC – N「木」
全方位木 DP です。
頂点を基準に考えたいので、問題を「初めに一つの頂点からなる集合を用意し、集合に含まれる頂点のいずれかと隣接する頂点を追加していく順番の総数」と言い換えます。
この順番の総数を数え上げると、問題の答えそのものが得られるわけではありませんが、この結果から問題の答えはすぐに計算できます。
状態の持ち方
$dp1[i]=$ 頂点 $i$ を根とする部分木について、頂点 $i$ のみからなる頂点集合から開始し、隣接する頂点を追加していくときの順番の総数
$dp2[i]=$ 木全体について、頂点 $i$ のみからなる頂点集合から開始し、隣接する頂点を追加していくときの順番の総数
出力するもの
$\sum_i dp2[i]$ から簡単に計算される値（計算については考えてみましょう）
初期化
特になし
TDPC – O「文字列」
状態の持ち方
$dp[i][j]=$ $i$ 種類目までの文字を並べる方法のうち、同じ文字が隣り合う箇所の個数が $j$ であるような並べ方の総数
例えば “AAABCCDD” は、$j$ の値は $4$ に対応します。（最初の “AAA” で 2 箇所、後ろの “CC”, “DD” でそれぞれ 1 箇所）
出力するもの
$dp[26][0]$
初期化
0 種類目の文字は無いので、空文字列についての値で初期化します。
$dp[0][0]=1$
$dp[0][*]=0$
TDPC – P「うなぎ」
木 DP です。
遷移をきれいに書くにはちょっとコツが必要です。
また、可能なすべての遷移を漏れなく書くように、細心の注意を払いましょう。
状態の持ち方
$dp1[i][j]=$ 頂点 $i$ を根とする部分木に $j$ 本のパスを書く方法のうち、頂点 $i$ を使用しない書き方の総数
$dp2[i][j]=$ 頂点 $i$ を根とする部分木に $j$ 本のパスを書く方法のうち、頂点 $i$ を辺の端点として使用する書き方の総数
$dp3[i][j]=$ 頂点 $i$ を根とする部分木に $j$ 本のパスを書く方法のうち、頂点 $i$ を辺の途中の点として使用する書き方の総数
出力するもの
$dp1[r][K]+dp2[r][K]+dp3[r][K]$（$r$ は根の頂点番号。ふつうは $0$）
初期化
特になし