問題概要

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

これも「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$になって間に合わないと思っていました。