Grenache's blog

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

問題概要

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

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

解法

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

  • $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
  • $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るDPで遷移している。
  • $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"が最大何個できるのかなので、DPの値としてこの値を更新するようにします。つまり、5.の状態になったらDPの値を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$のときに移っていかないので、DPの領域を再利用するか、関係ない文字のときも$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$文字目で起きうる状態へ配るDPで遷移している。
  • $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$文字目で起きうる状態へ配るDPで遷移している。
  • $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$文字目で起きうる状態へ配るDPで遷移している。
  • $i$文字目で考えるべき状態数は、問題の条件に依存する。
  • 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。

なんとかDPに慣れたい。。。

このページのトップヘ