問題概要
問題文はこちらを参照してください。
$n=300$なので、$O(n^3)$でもＯＫと気楽に考えられるようになりたいものです。
解法
文字列の問題は何となく$rec(0,n)$という再帰関数を呼び出したら答えが求まるようなイメージがあります。
$O(n^3)$なので、$rec(i,j)$ですべての組み合わせ(ただし、$j>i$)を試しても、$O(n^2)$でまだ余裕あります。なので、1文字ずつずらして文字列を2つに分割して文字列を消せる回数の最大値を調べていきます。(これで$O(n^3)$)
$$rec(i,j)=\max\{rec(i,k)+rec(k,j):k=i+1,i+2,...,j-1\}$$これに、文字が消せる場合の処理を加えないといけません。3文字で"iwi"の時は簡単ですが、4文字以上の時は文字列の一部が消えたときの残りがどうなるのかというのも考慮しないといけません。こう考えると、全部消えてしまう場合、右に1文字残る場合、左に2文字残る場合など、いろいろ複雑な気がします。ただ、上記の再帰の式で1文字ずつずらして比較しているというのを考慮すると、実はすべて文字列が消えてしまう時だけを考慮すると、うまくいくということに気づきます。(自分で気づけたわけではないですけど)
ある文字列がすべて消えてしまう条件は以下のようになります。
- 文字列の長さが3の倍数
- 両端はいずれも'i'
- 両端の'i'と中にある'w'との間の文字列が消えてしまう
このように文字列がすべて消えてしまう(文字列の長さが3の倍数)時だけ特別な処理をすればいいと思いつけるかどうかで大きな差がつくんだなと実感しています。
(1)$j-i$が3の倍数、(2)$s[i]=s[j-1]='i'$、
(3)$s[l]='w'$の時、$rec(i+1,l)=l-i-1\ $(文字列$s$の$[i+1,l)$の間が全部消える)かつ
$rec(l+1,j-1)=j-1-l-1\ $(文字列$s$の$[l+1,j-1)$の間が全部消える)が成り立つ場合
$rec(i,j)$：文字列$s$の$[i,j)$の範囲において、消すことができる文字列の数。(一回やると分かったのですが消せる回数ではなく、消せる文字数のほうが扱いやすい。答えの時1/3する。)
$(0\le i \lt n,\ 0\le j \le n,\ i+1\le l \lt j-1,\ n:文字列$s$の長さ)$
求める解：$rec(0,n)/3$
もちろん、メモ化は必要です。(3)のところで文字列$s$の$[i,j)$の間の'w'を調べるので、結局$O(n^3)$のままです。
まずメモ化再帰で考えたのは、ボトムアップによるＤＰの場合、どこから計算するべきかがわからなかったからです。ここまで考えると、実は短い文字列から求めるとうまくいくというのがわかりました。ボトムアップのＤＰで漸化式を考えると次のようになります。
(1)$j-i$が3の倍数、(2)$s[i]=s[j-1]='i'$、
(3)$s[l]='w'$の時、$dp[i+1][l])=l-i-1\ $(文字列$s$の$[i+1,l)$の間が全部消える)かつ
$dp[l+1][j-1]=j-1-l-1\ $(文字列$s$の$[l+1,j-1)$の間が全部消える)が成り立つ場合
$dp[i][j]$：文字列$s$の$[i,j)$の範囲において、消すことができる文字列の数。
$(0\le i \lt n,\ 0\le j \le n,\ i+1\le l \lt j-1,\ n:文字列$s$の長さ)$
初期値：全て0
求める解：$dp[0][n]/3$
ループの向き：文字列の長さが2文字以下の場合は消せる文字数は0になるので、処理は不要。$j-i$が3になる$i,j$の組み合わせから、$j-i$が$n$まで増えるループを回す。
最後のループの向きのところは次のような感じです
for (int len = 3; len <= n; len++) {
for (int i = 0; i + len <= n; i++) {
int j = i + len;
dp[i][j]=......
}
}
考察
再帰の時のオーダーの計算がぱっとわからないので、最初の漸化式のように1文字ずつずらして大丈夫なのかと思って躊躇してしまいます。案外愚直に試していくのがうまくいくこと多いですよね。なんかひらめきがないとだめだと思ってしまう。。。
コメント