「みんなのプロコン」本選 A - YahooYahooYahoo
お題箱より。
解法
「編集距離DP」を知ろう
まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。
- 置換: の任意の1文字を選んで、それを任意の1文字に置き換える。
- 削除: の任意の1文字を選んで、それを取り除く。
- 挿入: の任意の位置に、任意の1文字を挿入する。
この3操作は今回の問題と同じですね。これは以下のようなDPで解くことができます。
- 文字列 の前から 文字目までを文字列 の前から 文字目までに一致させるための操作回数の最小値
このDPにおいて、文字列 の文字をそのまま採用することと、上記の3操作を行うことは以下のような遷移で表現できます。
- そのまま: が に一致する時に限り、
- 置換:
- 削除:
- 挿入:
遷移は全て「より小さければ更新」です。この計算量は です。
「yahoo」のループを考えよう
さて今回の問題です。目標とする文字列は yahoo
の繰り返しで、問題文の上では の長さがどこまでも大きくなる可能性があります。さらに、 という制約から2乗オーダーのDPは間に合いそうにありません。
しかし逆に言うと、 yahoo
は何周繰り返していようと条件判定には関係ないので、周回数の情報は忘れてしまうことができます。つまり状態定義はこうです。
- 文字列 の前から 文字目までを、「
yahoo
を0周以上繰り返した後、末尾にyahoo
の途中まで 文字が中途半端に付いているような文字列」にするための操作回数の最小値
このDPの遷移は先ほどの編集距離DPとほぼ同じです。相違点は は の値しか取らず、 の次は に戻ります。これは末尾の yaho
の後に o
を付けることに対応します。
ここで少し注意すべきは「挿入」の遷移で、 と遷移するため同じ での遷移となります。この遷移はどこかで止めないと無限に回りますが、1周以上の文字列を連続で挿入することは無駄なので、それぞれの からの挿入の遷移として1~4文字の挿入だけを考えれば十分です。
このときの具体的実装として、例えば以下のような遷移が素直です。
- 遷移元の それぞれについて挿入文字数 を全部試し、 と遷移する
この他に、公式解説のように「遷移を2周回す」という手があります。これは
- ...
という遷移を順番に回していくもので、
と2周回すことで先ほどの から 文字を挿入する操作が全パターン含まれるようになります。
どちらにせよ、yahoo
の文字数5を定数とするならばこのDPは で動作し、 として答えを求めることが出来ます。
ACコード
- (位置と挿入文字数を全部試す)Submission #7095420 - 「みんなのプロコン」本選 オープンコンテスト
- (2周回す)Submission #7095422 - 「みんなのプロコン」本選 オープンコンテスト
遷移先などの候補として「ループして自分より前のインデックスに遷移することはあるが、1周は超えない」という状況になったときには、文字列や数列を2倍して遷移を考えてみるとスマートに処理できることが多いです。例えばこの問題などもそうですね。