DP 練習セット(EDPC編)

Pocket

こんにちは、ふるやん(@fuurya1223)です。

先日、DP (動的計画法)の練習に関してこんなツイートをしました。

この練習法は良いと思うのですが、検索結果という不確定要素に依存するのが微妙です。

ということで、本記事では DP 練習者向けに、いくつかの DP 問題について

  • 状態( DP 配列の添字)の持ち方(つまり DP 配列の定義)
  • 出力するもの
  • 初期化

のみを記載しました。

DP が苦手な方は、この記事を見て「漸化式を考える」もしくは「サンプルケースで DP 配列の表を直接埋めてみる」などの練習をしてみましょう。

漸化式というのは、DP 配列を更新するための式のことで、遷移などと言ったりもします($dp[i][j]=dp[i-1][j]+dp[i][j-1]$ みたいな)

「そもそも DP ってなんやねん」という方はこちらの記事などお読みください。

DP入門:Educational DP Contest A・B

以下の記述には、一部の DP 問題のみしか記載できていませんが、思いついたら追加していこうと思います。

「この問題を追加してほしい」という要望があれば、僕のツイッターアカウントやマシュマロ(匿名質問サービス。ツイッターアカウントのプロフィールに記載)からお伝え下さい。

また、解説と異なるテーブル定義をしている問題もあります。

そのような問題について「この方法での解説が欲しい」という要望があれば、こちらもツイッターかマシュマロにお願いします。解説記事を書きます。

※注意

添字を 1 始まりのまま利用したり、0 始まりに変えたり、問題によって扱いが異なります。うまいこと解釈して実装してください。

初期化の部分で $dp[0][0]=1, dp[*][*]=0$ などと表記している部分がありますが、$[*][*]$ は「明記した $[0][0]$ 以外のすべて」というように解釈してください。実装の際は順序を逆にして「全部 $0$ で配列を生成してから $[0][0]$ に $1$ を入れる」とするのが楽です。

追記:

ページが長くなったので、このページを EDPC 限定とし、TDPC と通常コンテストをそれぞれ別ページに分けました。

EDPC の難問に差し掛かったら、そちらのページの方もご覧ください。

DP 練習セット(TDPC編)

DP 練習セット(通常コンテスト編)

DP問題と状態の持ち方一覧

Educational DP contest : DP まとめコン

EDPC – A「Frog 1」, B「Frog 2」

足場の番号を 1 減らして、足場 $0$ から足場 $N-1$ までにしておきます。

状態の持ち方

$dp[i]=$ 足場 $0$ から足場 $i$ に行くために必要な最小コスト

出力するもの

$dp[N-1]$

初期化

$dp[0]=0$ (最初から足場 $0$ にいるので足場 $0$ に行くコストは 0 )

配る DP の場合: $dp[i]=\infty\ (i\neq 0)$

EDPC – C「Vacation」

状態の持ち方

$dp[i][j]=$ $i$ 日目に活動 $j$ をしたときの、$i$ 日目時点での幸福度の取りうる最大値

ただし、$i=0$ のときは幸福度 $0$ とする。

出力するもの

$\max_{0\le j\le 2} (dp[N][j])$

初期化

すべて $0$

EDPC – D「Knapsack 1」

考察

考慮すべき重さの最大値 $W$ が $10^5$ 以下なので、重さを添え字にするとメモリが足ります。

価値を添え字にするとメモリが爆発します。

状態の持ち方

$dp[i][j]=$ $i$ 番目の品物までを使って合計の重さを $j$ にするときの価値の最大値

出力するもの

$\max_{j}(dp[N][j])$

初期化

すべて $0$

EDPC – E「Knapsack 2」

考察

考慮すべき重さの最大値 $W$ が $10^9$ まであるので、重さを添え字にできません。

品物の個数が $100$ 以下で、価値の最大値が $10^3$ なので、全て入れても価値の合計は $10^5$ 以下です。

そのため、価値を添え字にできます。

状態の持ち方

$dp[i][j]=$ $i$ 番目の品物までを使って合計の価値を $j$ にするときの重さの最小値

出力するもの

$dp[N][j]\le W$ となる最大の $j\ (0\le j\le 10^5)$

初期化

$dp[0][0]=0$( 0 番目の品物は無いので、何も入れない価値 $0$ の場合に重さ $0$ である)

$dp[0][*]=\infty$(何も入れずに 0 以外の価値を達成できないので、そのときの重さの最小値は $\infty$ とする)

EDPC – F「LCS」

経路復元による解法と、ズボラな解法があります。

経路復元の方を身につけておきたいです。

経路復元の解法では、まず「最長共通部分列(LCS; longest common sequence)の長さはいくらか?」という問題に答えます。

その後、LCS長 の計算で用いた DP テーブルを使って、その長さを達成する文字列を後ろから復元します。

状態の持ち方

$dp[i][j]=$ $S$ の $i$ 文字目までと $T$ の $j$ 文字目までで作れる共通部分列の長さの最大値

ただし、「$0$ 文字目まで」は空文字列のこととする。

出力するもの

$dp[|S|][|T|]$($|S|$ は $S$ の長さ)

初期化

$dp[0][*]=0$

$dp[*][0]=0$

経路復元

$i=|S|,j=|T|$ として開始する。「答えの文字列」は最初、空文字列とする。

$dp[i][j]$ の値が $dp[i-1][j]$ と一致する場合、$S$ の $i$ 文字目は使用しないので、$i$ の値を $1$ 減らす。

$dp[i][j]$ の値が $dp[i][j-1]$ と一致する場合、$T$ の $j$ 文字目は使用しないので、$j$ の値を $1$ 減らす。

$dp[i][j]$ の値が $dp[i-1][j-1]+1$ と一致する場合、$S$ の $i$ 文字目が $T$ の $j$ 文字目と一致するので、その文字を「答えの文字列」に追加し、$i,j$ を $1$ 減らす。

これを $i,j$ のどちらかが $0$ になるまで続ける。

そうして得られた「答えの文字列」を反転させたものが、求める LCS である。

EDPC – F「LCS」(ズボラな解法)

DP テーブルを、文字列を要素とする二次元配列とする。

そのままではメモリが爆発するので、計算に関与しない部分をクリアしていく。

状態の持ち方

$dp[i][j]=$ $S$ の $i$ 文字目までと $T$ の $j$ 文字目までで作れる最長共通部分列(文字列)

ただし、「$0$ 文字目まで」は空文字列のこととする。

出力するもの

$dp[|S|][|T|]$($|S|$ は $S$ の長さ)

初期化

$dp[0][*]=$””(空文字列)

$dp[*][0]=$””

EDPC – G「Longest Path」

DAG(有向無閉路グラフ)の上で DP を行う問題です。

トポロジカルソートをしてループを回すことでも解けますが面倒です。

メモ化再帰を使ってうまく実装すれば、トポロジカルソートが不要になります。

少し難しいので飛ばしても問題ないと思います。

ヒント:再帰関数「int f(int p): 頂点 $p$ を始点とする有向パスの長さの最大値を返す関数」を実装する

状態の持ち方

$dp[i]= $ 頂点 $i$ を始点とするような有向パスの長さの最大値

出力するもの

$\max_j dp[j]$

初期化

$dp[*]=-1$(メモ化再帰を行うので、未計算の意味で負の数を入れておきます)

EDPC – H「Grid 1」

状態の持ち方

$dp[i][j]=$ スタート地点からマス $(i,j)$ に移動する方法の数を $10^9+7$ で割った余り

ただし、マスの番号を $(0,0)$ から $(H-1,W-1)$ になるように $1$ 減らして考える。

また、壁のマスにおいてはこの値を参照しないので無意味な情報が入る(実装で楽するために $0$ を入れておいても良い。壁のマスに移動する方法は無いので)。

出力するもの

$dp[H-1][W-1]$

初期化

$dp[0][0]=1$(スタート地点には「移動しない」という 1 通りの手段でたどり着ける)

EDPC – I「Coins」

状態の持ち方

$dp[i][j]=$ $i$ 番目までのコインのうち、表になるコインが $j$ 枚である確率

ただし、$0$ 番目までのコインは $0$ 枚なので、必ず表が $0$ 枚であるとする(こうすると実装が楽)

出力するもの

$\sum_{\frac{N+1}{2}\le j\le N}dp[N][j]$

初期化

$dp[0][0]=1$($0$ 番目までのコインには表が無い)

$dp[0][*]=0$

EDPC – J「Sushi」

状態の持ち方

$dp[i][j][k]=$ 寿司が $1$ 個の皿が $i$ 枚、$2$ 個の皿が $j$ 枚、$3$ 個の皿が $k$ 枚あるときの、寿司がなくなるまでの操作回数の期待値

出力するもの

$a_i$ に含まれる $1,2,3$ の個数を $n_1,n_2,n_3$ としたときの、

$dp[n_1][n_2][n_3]$

初期化

$dp[0][0][0]=0$(すでに寿司が無ければ残り操作回数は必ず $0$ )

EDPC – K「Stones」

2人ゲーム問題の典型的な考え方として、「自分の手番で状態を “負け状態” に変えられるなら、その状態は “勝ち状態” である」というものがあります。

“勝ち状態” というのは、「その状態で手番が回ってきた場合に必勝である状態」です。

今回の場合、石が 0 個の場合は “負け状態” です。 0 個だと操作を行えないので。

ゲーム終了状態からさかのぼりながら、状態を確定させていくことができます。

状態の持ち方

$dp[i]=$ 石が $i$ 個残っているときに手番が回ってきたプレイヤーが勝つ場合は true, 負ける場合は false

出力するもの

$dp[K]$ が true なら “First”、 false なら “Second”

初期化

$dp[0]=$ false

EDPC – L「Deque」

区間の両端を添え字に持つ「区間 DP」の最も簡単な例です。

半開区間としても閉区間としても解けますが、僕は半開区間 $[l,r)$ で考えることが多いです。

状態の持ち方

$dp[l][r]=$ $a_l,a_{l+1},\dots ,a_{r-1}$ の状態から開始して、両者が最適に行動したときの $X-Y$ の値

出力するもの

$dp[0][N]$

初期化

特になし

$dp[i][i]=0$ になるので、すべて $0$ にしておくと便利かと思います

EDPC – M「Candies」

下記の DP テーブルを使用して遷移を書くと、$O(NK^2)$ になってしまいます。

しかし、遷移の漸化式をうまく利用して、$O(NK)$ に改善できます。

状態の持ち方

$dp[i][j]=$ $i$ 人目の子供までに $j$ 個の飴を配る方法の数を $10^9+7$ で割った余り

出力するもの

$dp[N][K]$

初期化

$dp[0][0]=1$(0 人の子供には 0 個配ることだけが可能)

$dp[*][*]=0$

EDPC – N「Slimes」

区間 DP の典型例。

こちらも、僕は半開区間で考えています。

遷移を考えるのに頭を使います。

状態の持ち方

$dp[l][r]=$ $a_l,a_{l+1},\dots ,a_{r-1}$ のスライムが並んだ状態から、それらのスライムを 1 匹にするための最小コスト

出力するもの

$dp[0][N]$

初期化

特になし

$dp[i][i]=0$ になるので、すべて $0$ にしておくと便利かと思います

EDPC – O「Matching」

bit DP と呼ばれる問題の典型例です。

bit DP とは、添字に “集合” を持つ DP のことであり、集合がビット列で管理されるためこの名で呼ばれます。

bit DP はメモ化再帰で実装すると書きやすいことが多いです。

状態の持ち方

$dp[i][S]=$ $i$ 番目までの男性が、集合 $S$ に属する女性たちとすでにペアを作っている場合の、残りの男女で作れるペアのパターン数

つまり、$i$ 番目までの男性と集合 $S$ に属する女性を消したときのペアパターン数です。

出力するもの

$dp[0][\emptyset]$($\emptyset$ は空集合を表す。ビット列で表現すると $0$)

初期化

$dp[N][\Omega]=1$($\Omega$ は全女性の集合。ビット列で表現すると $11\dots1$)

EDPC – P「Independent Set」

木 DP の典型例です。

木 DP では、各頂点が「自分を根とする部分木についての値」を持ちます。

根無し木の場合、特に制約が無ければ、適当に根を決めます。

状態の持ち方

$dpB[i]=$ 頂点 $i$ を黒く塗るときのパターン数を $10^9+7$ で割った値

$dpW[i]=$ 頂点 $i$ を白く塗るときのパターン数を $10^9+7$ で割った値

出力するもの

$dpB[r]+dpW[r]$($r$ は根の番号。ふつうは $0$ を根とするので $0$)

初期化

特になし

葉については、$dpB[i]=1,dpW[i]=1$ となります。

EDPC – Q「Flowers」

考察

「ある花を抜かなくても単調増加に違反しないか」を考えるとき、その花より左側にある残った花のうち、最も右側にあるものの高さだけを気にすればよいです。

そのため、「右端の高さ」を状態に持たせます。

そのまま遷移の漸化式を考えると、あり得る高さの最大値が $N$ なので、 $O(N^2)$ になってしまいますが、漸化式の形を利用して高速化できます。

状態の持ち方

$dp[i][j]=$ $i$ 番目までの花について、右端の高さが $j$ になるような、単調増加になるようにいくつかの花を抜いたときの残りの花の美しさの総和の最大値

としたいですが、こうするとテーブルのサイズが $N^2$ 程度になってしまい、メモリが足りません。

遷移について考えると、$i$ 番目の花について考えるとき、$dp[i-1][*]$ から変化する部分は $dp[i][h_i]$ だけです。

したがって、$dp[j]$ の配列を使いまわしていくことができます。(こういう実装の仕方を in-place と表現したりします)

出力するもの

$N$ 番目の花まで見た後で、$max_j dp[j]$

初期化

$dp[*]=0$

EDPC – R「Walk」

「長さ $K$ のパスは何通りか」といえば、あれです。

あんまり DP っぽくない問題です。

下記の通りに状態を持つと DP 配列の大きさが $N^2K$ になってダメなので、添字 $k$ を持たずにできるといいですね。

「DP の更新式をにらむと、DP 的ではない高速計算方法が思いつく」みたいな感じの問題です。

なお、頂点番号を $0$ から $N-1$ として書いています。

状態の持ち方

$dp[i][j][k]=$ 頂点 $i$ から頂点 $j$ までの、長さ $k$ のパスの個数

出力するもの

$\sum_{0\le i\le j< N-1}dp[i][j][K]$

初期化

$dp[i][j][1]=a_{i,j}$(実際には 3 次元配列として持つわけではないですが、あくまでイメージとして)

EDPC – S「Digit Sum」

桁 DP の典型例です。

桁 DP では上の桁から数を決めていきますが、「上限値($K$)に張り付いているか、緩んだか」という状態を保持します。

「張り付いている」というのは、「その桁までずっと上限値と一致するように桁の数を決めた場合」を意味し、この場合は上限値の制約から、次の桁に利用できる数に制限が掛かります。

「緩んだ」というのは、「途中で上限値を下回るように桁の数を決めた場合」を意味し、この場合はすでに上の桁で上限値より小さくなっているので、次の桁には $0$ から $9$ まですべての数を使えます。

状態の持ち方

$dp1[i][j]=$ 途中で $K$ を下回るように $i$ 桁目まで決めたときに、各桁の和を $D$ で割った余りが $j$ になるような方法

$dp2[i][j]=$ ずっと $K$ と一致するように $i$ 桁目まで決めたときに、各桁の和を $D$ で割った余りが $j$ になるような方法

出力するもの

$dp1[N][0]+dp2[N][0]-1$( $1$ を引いているのは、$0$ を除くため)

初期化

$dp2[0][0]=1$(まだ桁を埋めていないので、値としては $0$ です。このとき、まだ上限値を下回っていません)

$dp1[0][*]=dp2[0][*]=0$

EDPC – T「Permutation」

考察

途中まで決めたとき、その先の決め方に影響を与えるのは、すでに決めた中で右端の数字だけです。なので、

「左から $i$ 番目まで数字を決めたときに、右端が $j$ であり、残りの数の集合が $S$ である場合の並べ方の個数」

とやりたくなる気持ちがありますが、到底間に合いません。

ここで、「その先を決めるときに重要なのは、右端の数が残りの数の上から何番目か」が同じであれば、その具体的な集合の構成がどうであれ、並べ方の個数が全く同じであることに気づくと素晴らしいです。

状態の持ち方

$dp[i][j]=$ $i$ 番目まで数字を決めたときに、右端の数が残りの数の上から $j$ 番目であるように並べる方法の個数($j$ は 0 始まりとする)

出力するもの

$dp[N][0]$

初期化

$dp[0][N]=1$

$dp[0][*]=0$

EDPC – U「Grouping」

bit DP 的に、ビットで管理する集合を添字とします。

bit DP なので、メモ化再帰で書くと楽です。

遷移が高度典型です。キーワードは「部分集合」。

状態の持ち方

$dp[S]=$ 集合 $S$ のうさぎたちをいくつかのグループに分けるときの、得点の最大値(ここに $S$ に属さないうさぎの得点は入っていない)

出力するもの

$dp[\Omega]$($\Omega$ は全要素の集合。数で表すと $2^N-1$)

初期化

特になし(未計算か計算済みかの判定のため、$-\infty$ を入れておく)

サイズ 1 の集合 $s$ については $dp[s]=0$ となる(再帰の終了条件)。

EDPC – V「Subtree」

「全方位木 DP 」です。

普通のの木 DP では、各頂点を根とする部分木についての値(つまり、下向きの値)のみを計算しますが、全方位木 DP では、親方向も考慮した、すべての辺への値から自身の値を計算します。

そのため、DFS を 2 回行うことになります。

1 回目の DFS では普通の木 DP の気持ちで、各部分木について葉方向のみを考慮した値を計算します。そうすると、根については全方向の情報が得られます。

その後、根から DFS をしながら、「親方向の情報」を降ろしていきます。

つまり、2 回目の DFS では、各頂点で「 1 回目の DFS で計算済みの葉方向の情報」と「今持ってきた親方向の情報」を併用して、自身の「全方向の情報」を計算します。

状態の持ち方

$dp1[i]=$ 頂点 $i$ を根とする部分木について、頂点 $i$ を黒く塗るときの塗り方の個数

$dp2[i]=$ 木全体について、頂点 $i$ を黒く塗るときの塗り方の個数

出力するもの

$0\le v\le N-1$ のすべての $v$ について $dp2[v]$

初期化

特になし(葉 $l$ において、$dp1[l]=1$ とします)

EDPC – W「Intervals」

考察

右から 01 を埋めていくことを考えましょう。

$i$ 番目の文字を ‘1’ にしたとき、スコアが変化する場合としない場合があります。

スコアが変化する場合とは、 $i$ 番目を含む区間が与えられていて、かつ、それまでその区間内に ‘1’ を入れていない場合です。

逆に、$i$ 番目を含む区間がなかったり、$i$ 番目を含む区間すべてについて、すでにその区間内に ‘1’ を入れている場合、$i$ 番目を ‘1’ にしてもスコアは変化しません。

ということで、「右端の ‘1’ がどこか」を状態として持つと良さそうです。

なお、この遷移の高速化には遅延伝播セグメント木が必要です。

状態の持ち方

$dp[i]=$ 右端の ‘1’ が $i$ 番目であるような文字列のうち、最大のスコア

ただし、$0$ 番目の文字は ‘1’ であるとします。こうしておくとシンプルになって便利です。

なお、この DP 配列はセグメント木の更新によって変化するので、計算する度に $\max$ をとっていくか、セグメント木とは別の配列として保存するかしておく必要があります。

出力するもの

$\max_i dp[i]$

初期化

$dp[0]=0$ (右端の ‘1’ が 0 番目、すなわち文字列が “00…0” であるとき、スコアは 0 です)

EDPC – X「Tower」

考察

「$i$ 番目のブロックまで見たとき」や「塔の上から $i$ 番目まで決めたとき」などと考えたくなりますが、そのままだとダメです。

なぜなら、塔を作れるブロックの組み合わせでも、上下の並べ方によっては不可能になることがあるからです。

しかし、この問題では、すべての 2 つのブロックの組について「両方採用するならどちらを上にすべきか」が確定します。

「最適な順番が確定するからその順番でソートして貪欲」という問題がありますが、これはその DP 版です。

ソートの仕方は考えてみましょう。

状態の持ち方

$dp[i][j]=$ (上にするべきブロックが前になるようにソートした状態で)$i$ 番目のブロックまでを使って、重さが $j$ になる塔を作るときの価値の総和の最大値

出力するもの

$\max_j dp[N][j]$

初期化

$dp[0][0]=0$ (ブロックを使わなければ重さ 0 、価値 0 の塔ができる)

EDPC – Y「Grid 2」

考察

最初、座標圧縮するのかと思いましたが、破滅します。

「すべての壁を回避する経路」は難しいので、補集合である「 1 つ以上の壁を通る経路」を数えて、全経路から引きましょう。

「 1 つ以上の壁を通る経路」を数えるとき、「壁 1 を通る経路、壁 2 を通る経路、……」をそれぞれ数えると「壁 1 と壁 2 を両方通る経路」などをダブルカウントしてしまいます。

ダブルカウントを回避したいですが、包除原理も使いにくそうなので、オーソドックスにいきます。

つまり、排反事象(被りのない集合)に分割します。

分割方法は「壁 1 を最初に通る経路、壁 2 を最初に通る経路、……」とします。

こうすると、被りがありません。

遷移については、$O(N^2)$ が許されるので、頑張って考えてみましょう。

組合せの計算において、最大で $2\times 10^5$ の階乗や階乗逆元が必要になることに注意しましょう。

状態の持ち方

$dp[i]=$ 壁 $i$ を(通る壁の中で)最初に通る経路の個数

なお、$dp[i]$ の計算で「$(1,1)$ から壁 $i$ までの行き方」のみを考慮するか、「$(1,1)$ から壁 $i$ を通って $(H,W)$ に行く行き方」まで考慮するかの選択肢がありますが、どちらでも解くことは可能です。

ただし、後者の場合は遷移の式が少し複雑になるので、私は前者で解きました。

出力するもの

$(1,1)$ から $(H,W)$ へ行く経路の数から $\sum_i dp[i]$ を引いた値

なお、$dp[i]$ の計算で「$(1,1)$ から壁 $i$ までの行き方」のみを考慮した場合は、引く値が

$\sum_i dp[i]\times($ 壁 $i$ から $(H,W)$ へ行く経路の数 $)$

になります。

初期化

特になし

EDPC – Z「Frog 3」

考察

序盤の敵が強くなってラスボスになるって良いですよね。

A, B 問題と同様の配列設定ですが、現在地より右側のすべての足場まで移動することが可能となっています。

そのため、普通に実装すると計算量が $O(N^2)$ となってしまいます。

遷移の漸化式を整理すると、一次式と $\min$ が組み合わさった形になります。

そのため、あの有名テクニックが使えます。

状態の持ち方

$dp[i]=$ 足場 $0$ から足場 $i$ に行くために必要な最小コスト

出力するもの

$dp[N-1]$

初期化

$dp[0]=0$ (最初から足場 $0$ にいるので足場 $0$ に行くコストは 0 )

Pocket

スポンサーリンク
レクタングル大
レクタングル大

シェアする

  • このエントリーをはてなブックマークに追加

フォローする