Grenache's blog

競技プログラミング初心者です。

カテゴリ： DP(動的計画法)

問題概要

問題文はこちらを参照してください。

コンテスト後の解説放送中に話題に出たＤＰを使った解法を書きました。数値が$n$以下という制限がないのでいわゆる桁ＤＰというよりは、「AtCoder Typical DP Contest Q 連結」の解説のような1文字ずつ増やしていくＤＰが近いのかなと思います。また、$n$番目の組み合わせを求めるというのは、「AtCoder Typical DP Contest G 辞書順」の解説に出てくるやり方です。

解法

まずは作問者の方の解説に書いてある条件をもとに、この問題を「"3"と"5"からなる長さ$1～L$の文字列のうち、1桁目が"5"であり、各桁の数字の和が3の倍数であるような文字列の組み合わせの中で、$n$番目の数を求めよ」と読みかえます。

漸化式の定義： $$dp[i+1][l][(k + d[l])\mod 3]+=dp[i][j][k]$$ $$d[l]=\{3, 5\}$$

$dp[i][j][k]$：$i$文字目(1桁目から数える)が$d[j]$という数のときにそれまでの各桁の数字の和を3で割った余りが$k$である文字列の組み合わせの数
$(0\le i \le 25,\ 0\le j,l \le 1,\ 0\le k \le 2)$

初期値：$dp[1][1][2]=1$(1文字目が"5"のとき、つまり3で割った余りが2のときのみ存在する)

求める解：$dp[i][j][0]$。$i$文字目が$d[j]$のときに各桁の数字の和を3で割った余りが0である組合せの数となる。

このように$i$文字目の状態から$l$のループを回して$i+1$文字目として"3"または"5"のときそれぞれの遷移を配るＤＰで行います。今回はサンプルより最大の文字列の長さが25とわかるので、$i=25$までのＤＰを求めておくことができます。

まずは$n$番目の数が何桁なのかを求めるために、$n$から$dp[i][j][0]$を小さいほうから順に引いていきます。そしてそれが0以下になるところ(小さいほうからの累積和が初めて$n$以上になるところ)が求める桁数になります。この結果は作問者の方の解説では数え上げによって求められていたものと同じです。

yukicoder294-1

桁数と先頭の数がわかったら、その中で$n'$番目の数は何なのかを求めます。上記の例では結局、4文字目が"5"で長さが4の条件を満たす文字列(2つある)の中で1番目の組み合わせを求めることになります。これは4文字目から1文字目までどのような遷移をたどってきたかを戻りながら求める$n'$番目の数を決定していきます。遷移を戻っていくためには決定した数字によって3で割った余りが変化していくところを考えていく必要があります。

yukicoder294-2

考察

この解説ではわかりやすいかと思って$i$文字目が$d[j]$("3"または"5")のときの組み合わせの数という状態を作りました。ちなみにuwiさんの回答では$j$に関する状態は作られていません($dp[i][k]$：$i$文字目までで各桁の数字の和を3で割った余りが$k$の組み合わせの数)。その代り$i$文字目がどちらなのかを決定する際にＤＰの$i-1$の値を使って決定されています。この解説では$i$文字目を決定するためにＤＰの$i$の値を使っています。結局やっていることは一緒だと思います。

問題概要

問題文はこちらを参照してください。

これも「AtCoder Typical DP Contest Q 連結」を考えているときに参考になった問題です。ほぼ、「SRM671 Div1 Easy BearCries」の解説と同じ内容で、情報量少なめです。

解法

「Q 連結」の解説で書いたように、この問題を下記と同じ考え方で解いていきます。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

まずは問題を「'A'~'Z'または'?'からなる長さ$L$の文字列において、"KUROI"の部分列に分解できる最大の個数を求めよ。」と言い換えてみます。('?'は'A'～'Z'のどれかに当てはまる)

この条件を判定するために必要なすべての状態についてですが、1文字ずつ文字を増やしていったときに、部分列は"K"だけ、"KU"、"KUR"と状態が変化をしていきます。これらの個数をカウントすることで全体の状態を管理していきます。

  1. "K"だけ(他の文字と組み合わさっていない)が$jk$個ある状態
  2. "KU"が$ju$個ある状態
  3. "KUR"が$jr$個ある状態
  4. "KURO"が$jo$個ある状態
  5. "KUROI"の状態の最大値

問題が部分列"KUROI"が最大何個できるのかなので、ＤＰの値としてこの値を更新するようにします。つまり、5.の状態になったらＤＰの値を1増やすという遷移を考えます。'?'の場合は'K','U','R','O','I'のすべての可能性があるとして遷移させます。これら以外の文字は何もしません。

この問題も与えられた文字列によって状態の遷移先が決まっていきます。

漸化式の定義： $$\begin{array}{l} d=dp[i][jk][ju][jr][jo]とする\\ dp[i+1][jk+1][ju][jr][jo]=\max\{dp[i+1][jk+1][ju][jr][jo],\ d\}\\ \hfill (i+1文字目が'K'または'?'\land jk\lt 20)\\ dp[i+1][jk-1][ju+1][jr][jo]=\max\{dp[i+1][jk-1][ju+1][jr][jo],\ d\}\\ \hfill (i+1文字目が'U'または'?'\land ju\lt 20\land jk\gt 0)\\ dp[i+1][jk][ju-1][jr+1][jo]=\max\{dp[i+1][jk][ju-1][jr+1][jo],\ d\}\\ \hfill (i+1文字目が'R'または'?'\land jr\lt 20\land ju\gt 0)\\ dp[i+1][jk][ju][jr-1][jo+1]=\max\{dp[i+1][jk][ju][jr-1][jo+1],\ d\}\\ \hfill (i+1文字目が'O'または'?'\land jo\lt 20\land jr\gt 0)\\ dp[i+1][jk][ju][jr][jo-1]=\max\{dp[i+1][jk][ju][jr][jo-1],\ d+1\}\\ \hfill (i+1文字目が'I'または'?'\land jo\gt 0)\\ \end{array}$$

$dp[i][jk][ju][jr][jo]$：$i$文字目までの文字列を部分列に分割したときに、"K"のみのものが$jk$個あり、"KU"のものが$ju$個、"KUR"のものが$jr$個、"KURO"のものが$jo$個ある状態で"KUROI"ができている最大の数 $(0\le i\le L,\ 0\le jk,ju,jr,jo\le 20)$

$L$：文字列の長さ

初期値：$dp[0][0][0][0][0]=0$、それ以外は$-INF$(適切な負の値)

求める解：$\max\{dp[i][jk][ju][jr][jo]\}$(すべての値の中の最大の数)

「SRM671 Div1 Easy BearCries」と違って、

  • 求めるものが組合せの数ではなく、最終形の"KUROI"になる最大の数である。なので、初期値として$-INF$で初期化が必要。
  • ワイルドカードの'?'が含まれている。なので、解が最大になるように遷移が追加される。
などがあげられますが、基本的な流れは同じ問題と思います。

また、この問題は解説にもあるように次の点に注意が必要です。

  • 全体の文字列の長さから"KUROI"は最大20個しかできないので、各文字の状態の管理の上限を20にしても構わない。(だからTLEしない)
  • 遷移を発生させない関係ない文字のときは、$i$のときの値が$i+1$のときに移っていかないので、ＤＰの領域を再利用するか、関係ない文字のときも$i$から$i+1$のときに値を遷移させる($dp[i+1][jk][ju][jr][jo]=dp[i][jk][ju][jr][jo]$)必要がある。

考察

後で考えると分かるんですけどね。本番では$100^5$になって間に合わないと思っていました。

問題概要

問題文はこちらを参照してください。

「AtCoder Typical DP Contest Q 連結」を考えているときに参考になった問題です。この問題の解説で書いているのと同じような解法が使えます。

解法

「Q 連結」の解説で書いたように、この問題を下記と同じ考え方で解いていきます。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

まずは問題を「";"と"_"からなる長さ$L$の文字列において、すべてが";_+;"の部分列に分解できる組合せの数を求めよ。」と言い換えてみます。(厳密な定義ではありませんがざっくりとしたイメージ。"_+"は1個以上の"_"が当てはまるとします。)

この条件を判定するために必要なすべての状態についてですが、1文字ずつ文字を増やしていったときに、部分列は";"だけ、";_+"、";_+;"と状態が変化をしていきます。これらの個数をカウントすることで全体の状態を管理していきます。

  1. ";"だけ(他の文字と組み合わさっていない)が$j$個ある状態
  2. ";_+"(1個以上の"_"と組み合わさった";")が$k$個ある状態
  3. ";_+;"(最終的な形の組み合わせ)が$l$個ある状態

ここで、3.の状態は個数を考える必要はなく、1.の";"だけが0個、2.の";_+"が0個であれば、";_+;"だけができたとみなすことができます。従って状態の遷移は以下のようになります。

  • $i+1$文字目が";"なら、新たな部分列の左端の候補と考え、1.の個数が1個増える状態に遷移する($j$個から$j+1$個へ)。
  • $i+1$文字目が";"なら、部分列";_+"とつなげて最終形になると考え、2.の個数がが1減る状態に遷移する($k$から$k-1$へ)。その際に、どの部分列";_+"につなげるかという$k$個の候補が存在する(組み合わせ数は$k$倍になる)。
  • $i+1$文字目が"_"なら、部分列";"とつなげて部分列";_"になると考え、1.の個数が1減って、2.の個数が1個増える状態に遷移する($j,k$から$j-1,k+1$へ)。その際にどの部分列";"とつなげるかという$j$個の候補が存在する(組合せ数は$j$倍になる)。
  • $i+1$文字目が"_"なら、部分列";_+"の"_"の個数が増えると考えて、2.の"_"が増えるだけで状態は変わらない($j,k$から$j,k$へ)。しかし、どの部分列";_+"の"_"の個数が増えるかという$k$個の候補が存在する(組み合わせ数は$k$倍になる)。

このように、「Q 連結」と違って、$i+1$文字目で考えられるすべての状態("0"または"1"を足す)を調べるのではなく、与えられた文字列によって状態の遷移先が決まっていきます。

漸化式の定義： $$\begin{eqnarray} dp[i+1][j+1][k] & += & dp[i][j][k]\ (i+1文字目が';')\\ dp[i+1][j][k-1] & += & dp[i][j][k]\cdot k\ (i+1文字目が';'\land k\gt 0)\\ dp[i+1][j-1][k+1] & += & dp[i][j][k]\cdot j\ (i+1文字目が'\_'\land j\gt 0)\\ dp[i+1][j][k] & += & dp[i][j][k]\cdot k\ (i+1文字目が'\_') \end{eqnarray}$$

$dp[i][j][k]$：$i$文字目までの文字列を部分列に分割したときに、";"のみのものが$j$個あり、";_+"のものが$k$個ある組合せの個数 $(0\le i\le L,\ 0\le j\le L,\ 0\le k\le L)$

$L$：文字列の長さ

初期値：$dp[0][0][0]=1$

求める解：$dp[L][0][0]$

求める解は$L$文字目ですべての部分列が";_+;"になっていなければいけないので、$j=0,k=0$のときの組み合わせの数になります。

例えば最初の文字が"_"であった場合は、絶対に条件は満たせない(答えは0)のですが、この漸化式で計算すると初期値の$dp[0][0][0]=1$が1文字目の時点で消えてしまいます。$dp[1][0]0]=dp[0][0][0]\cdot 0$となり$i=1$のすべての要素が$0$なので、その後の計算はすべて$0$です。最後に"_"が来た場合も絶対に条件は満たせませんが、この場合も最後に$dp[L][0][0]$に遷移してくる漸化式が、$dp[L][0][0]=dp[L-1][0][0]\cdot 0$なので、同じく答えは$0$になります。

考察

全ての状態をどのように表すのかを考えるのは難しいですが、考え方としてはよく使われるのではないでしょうか。

問題概要

問題文はこちらを参照してください。

前編の考察を踏まえて解法を説明していきます。

解法

前編で書いたように、この問題は「0と1からなる長さLの文字列のうち、N個の文字列の連結でできる文字列の個数を求めよ。」と言い換えることができます。これを下記と同じ考え方で解いていきます。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

まずは$i$文字目で考えられるすべての状態についてです。ここで持つべき状態は、$i+1$文字目を含めて考えたときにそれが起きうるのかどうかを判定できるだけの情報がなければいけません。連結する文字列の最大長が8文字なので、$i+1$文字を含めて8文字、つまり$i$文字目までで7文字分の状態を持っておく必要があります。

さらに連結する候補の文字列の長さが異なっているので、7文字分のどこに連結点があるのかを持っておく必要があります。7文字の文字列には8か所の連結点候補があるので、8ビットの数で表すことができます。

typicalDPQ2-1

つぎに、$i+1$文字目のどのような状態に遷移できるのかですが、$i$文字目までの7文字分に1文字足して8文字分の文字列を考えます。この8文字分が、連結候補の文字列で終わることができれば、新たな連結点を右端に設定します。連結候補の文字列で終わることができなければ、右端は連結点ではない状態に遷移します。

typicalDPQ2-2

このように、$i+1$文字目に"0"または"1"を足して、それぞれ遷移が可能な$j'$と$k'$を決定します。

漸化式の定義： $$dp[i+1][j'\&mask7][k'\&mask8]+=dp[i][j][k]$$

$dp[i][j][k]$：$i$文字目までの文字列で、$i-6からi$文字目7文字分をビットとみなした数が$j$であり、その数の連結点をビットで表した数が$k$である文字列の組み合わせの数 $(0\le i\le L,\ 0\le j\lt 128,\ 0\le j'\lt 256,\ 0\le k\lt 256,\ 0\le k'\lt 512)$

$j'$：$j$から1文字足して遷移できる$j'$。つまり、$j$に"0"または"1"を足して、それをビットとみなした数。

$k'$：$j'$の連結点を表す。$j'$は$j$に1ビット足したものなので、$k$を1ビット左にシフトしたものになる。もし、$j'$と$k'$から決定される各連結点から最下位ビットまでの文字列が$N$個の文字列に含まれる場合は最下位ビットも連結点になりうる。つまり、$k'$の最下位ビットをたてる。

$mask7$：$j'$から下位7ビットを取り出すためのもの。$mask7=127$

$mask8$：$k'$から下位8ビットを取り出すためのもの。$mask8=255$

初期値：$dp[0][0][1]=1$($k=1$は文字列の先頭が連結点になることを示す)

求める解：$\displaystyle\sum_{j=0}^{127}\sum_{k=0}^{255}dp[L][j][k]$(ただし、$k\&1\ne 0$を満たす$k$)

この漸化式では$i$文字目から遷移できるすべての状態について遷移しています。最終的に答えに関係ないかどうかがこの時点では決定できないからです。つまり、$i+1$文字目で連結点が設定できない文字列でもこの先で使われる可能性があるということです。

また、この漸化式で同じ文字列になる場合を2重にカウントしないことになるのかという点も確認しないといけません。これは$j$の値が同じ場合は連結点が一番多い$k$の値のところのみへ初期値が遷移していくので、すべての状態の遷移を計算しても2重カウントは発生しません。以下2つの具体的なケースについて例を挙げてみます。

typicalDPQ2-3

なぜ2重カウントされないのかをうまく言葉では表せていませんが、何とかわかっていただけるでしょうか。

この漸化式を実装すると$i,j,k,j',k'$のループが必要となりますが、$j',k'$は全値をループするわけにはいきません。まず、$j'$は$j$に"0"または"1"を追加してできるので$O(2)$です。$k'$は$N$個の文字列の中に$j'$の連結点から見た文字列が含まれるかどうかを調べるために回す必要があります。連結候補の文字列が存在するかどうかを長さとビットパターンのboolean配列(wt[8][256]など)で事前に作っておくことで、各連結点を見る$O(8)$でチェックできます。したがって、全体では$O(L\cdot 128\cdot 256\cdot 2\cdot 8)$になります。

求める解は$L$文字目が連結点になっていなければいけないはずなので、$k$の最下位ビットが立っている全ての状態を足したものになります。

考察

なぜこの方法で解けるのかは分かったつもりですが、この問題が出ても思いつけそうな気は相変わらずしません。。。

ただ、次の考え方は典型の解法として使えると思いました。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

なんとかＤＰに慣れたい。。。

問題概要

問題文はこちらを参照してください。

この問題は理解するのにとても時間がかかりました。なので、2回に分けて書くことにします。前編ではこの問題の理解に参考になるであろう問題の考察、後編で解法を書きます。

なかなか他の方の解説を読んでも理解することができなかったのですが、SRM671 Div1 Easy BearCriesの問題(の解説)を見て、やっと理解が進みました。さらに、yukicoder No.291 黒い文字列も同じような考え方の問題だと思います。タイミングよくこれらの問題に出会えてやっと解くことができました。

参考：SRM671 Div1 Easy BearCriesの解説、yukicoder No.291 黒い文字列の解説

解法

この問題は「0と1からなる長さ$L$の文字列のうち、ある条件を満たす文字列の個数を求めよ。」と言い換えることができます。条件は「$N$個の文字列の連結でできるもの」となります。

まず最初に、「0と1からなる長さ$L$の文字列の個数を求めよ。」という、何も条件がない問題を考えてみます。これは単純に$2^L$が答えですが、ＤＰを使って解くこともできます。これを漸化式で表すと次のようになります。

漸化式の定義： $$dp[i+1][0]+=dp[i][0]$$ $$dp[i+1][1]+=dp[i][0]$$ $$dp[i+1][0]+=dp[i][1]$$ $$dp[i+1][1]+=dp[i][1]$$

$dp[i][j]$：$i$文字目までの文字列で、$i$文字目が$j$である文字列の組み合わせの数 $(0\le i\le L,\ j=0,1)$

初期値：$dp[0][0]=1$

求める解：$dp[L][0]+dp[L][1]$

この配るＤＰで定義した漸化式の意味は

  • $i$文字目が"0"のとき、$i+1$文字目が"0"および"1"に遷移できる。
  • $i$文字目が"1"のとき、$i+1$文字目が"0"および"1"に遷移できる。
ということを表しています。求める解は、$L$文字目が"0"および"1"のときの組み合わせの数の和です。

つぎに、この問題に条件を追加して、「0と1からなる長さ$L$の文字列のうち、0が2つ連続しない文字列の個数を求めよ。」という問題を考えてみます。これを漸化式で表すと次のようになります。

漸化式の定義： $$dp[i+1][1]+=dp[i][0]$$ $$dp[i+1][0]+=dp[i][1]$$ $$dp[i+1][1]+=dp[i][1]$$ $$dp[i+1][0]+=dp[i][0](ただし、i=0のときだけ)$$

$dp[i][j]$：$i$文字目までの文字列で、$i$文字目が$j$である文字列の組み合わせの数 $(0\le i\le L,\ j=0,1)$

初期値：$dp[0][0]=1$

求める解：$dp[L][0]+dp[L][1]$

この漸化式の意味は

  • $i$文字目が"0"のとき、$i+1$文字目が"1"のみに遷移できる。
  • $i$文字目が"1"のとき、$i+1$文字目が"0"および"1"に遷移できる。
  • ただし、$i=0$のときは2文字連続しないので、"0"へも遷移できる。
ということを表しています。このように、現在の1文字によってつぎに遷移できる先が制限されてしまうということです。3番目の条件は初期値として$dp[1][0]=1,\ dp[1][1]=1$として$i=1$からループを回すと考えても構いません。

さらにもう一問、もうちょっと複雑な条件を追加して「0と1からなる長さ$L$の文字列のうち、0が3つ連続しない文字列の個数を求めよ。」という問題を考えてみます。これまでと同じように考えると、$i+1$文字目への遷移の際に、$i-1$文字目が"0"、$i$文字目が"0"からは$i+1$文字目が"0"へ遷移できないということを実現できれば解けそうです。つまり、$i$文字目と$i-1$文字目の2文字分の状態を保持しておく必要があります。

漸化式の定義： $$dp[i+1][j'\&mask2]+=dp[i][j](ただし、j'\ne 0 \lor i\lt 2)$$

$dp[i][j]$：$i$文字目までの文字列で、$i-1,\ i$文字目をビットとみなした数が$j$である文字列の組み合わせの数 $(0\le i\le L,\ 0\le j\le 3,\ 0\le j'\le7)$

$j$：$i-1,i$文字目が"00"のとき、これを2進数とみなして$j=0$、"01"のときは$j=1$、"10","11"のときはそれぞれ、$j=2,j=3$となる。

$j'$：$j$に1文字足して遷移できる$j'$。つまり、$j$に"0"または"1"を足して、それをビットとみなした数。

typicalDPQ

$mask2$：$j'$の下位2ビットを取り出すためのもの。$mask2=3$。

初期値：$dp[0][0]=1$

求める解：$\displaystyle\sum_{j=0}^{3}dp[L][j]$

この漸化式の意味は

  • $i-1,i$文字目が"00"のとき、$i+1$文字目が"1"のみ($i-1,i,i+1$文字目が"001")に遷移できる("000"へは遷移できない)。
  • $i-1,i$文字目が"01"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"010"および"011")に遷移できる。
  • $i-1,i$文字目が"10"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"100"および"101")に遷移できる。
  • $i-1,i$文字目が"11"のとき、$i+1$文字目が"0"および"1"($i-1,i,i+1$文字目が"110"および"111")に遷移できる。
  • ただし、$i\lt 2$のときは、3文字連続しないので"0"へも遷移できる。
ということを表しています。$i+2$文字目を考える際には$i-1$文字目の情報は必要ないため、$j'$の下位2ビットを取り出して、ＤＰを更新していきます。

これら3つ問題で共通しているのは、次の点です。

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

この考え方でQ 連結を解くことができます。つまり、この問題の条件に基づいて考えるべき状態数を決めて、どのような状態の遷移が可能かを考えるということになります。

考察

漸化式を見てもらうと、$i$に関しては$i$から$i+1$への配るＤＰなので2つの領域があれば十分です。ただ、このケースでは値は使い回せないので毎回初期化が必要になり、あまり意味はないのかもしれません。

3問目の$j'$ですが、$j$も$j'$もループを回して条件が合う時だけ実行するようにしてしまうと無駄が多くなります。$j'$は$j$に"0"または"1"を足したものではなければいけないので、$j$をもとに作るようにします。すると、$O(L\cdot2^2\cdot2)$になります。

このページのトップヘ