問題概要
問題文はこちらを参照してください。
「AtCoder Typical DP Contest Q 連結」を考えているときに参考になった問題です。この問題の解説で書いているのと同じような解法が使えます。
解法
「Q 連結」の解説で書いたように、この問題を下記と同じ考え方で解いていきます。
- $i$文字目までの部分問題を使って、$i+1$文字目までの問題を解いている。
- $i$文字目で考えられるすべての状態から、$i+1$文字目で起きうる状態へ配るＤＰで遷移している。
- $i$文字目で考えるべき状態数は、問題の条件に依存する。
- 求める解は$L$文字目で条件に合う状態の値をすべて足したもの。
まずは問題を「";"と"_"からなる長さ$L$の文字列において、すべてが";_+;"の部分列に分解できる組合せの数を求めよ。」と言い換えてみます。(厳密な定義ではありませんがざっくりとしたイメージ。"_+"は1個以上の"_"が当てはまるとします。)
この条件を判定するために必要なすべての状態についてですが、1文字ずつ文字を増やしていったときに、部分列は";"だけ、";_+"、";_+;"と状態が変化をしていきます。これらの個数をカウントすることで全体の状態を管理していきます。
- ";"だけ(他の文字と組み合わさっていない)が$j$個ある状態
- ";_+"(1個以上の"_"と組み合わさった";")が$k$個ある状態
- ";_+;"(最終的な形の組み合わせ)が$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"を足す)を調べるのではなく、与えられた文字列によって状態の遷移先が決まっていきます。
$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$になります。
考察
全ての状態をどのように表すのかを考えるのは難しいですが、考え方としてはよく使われるのではないでしょうか。
コメント