ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

「みんなのプロコン」本選 A - YahooYahooYahoo

お題箱より。

A - YahooYahooYahoo

解法

「編集距離DP」を知ろう

まずは「編集距離DP」なるものを説明します。2つの文字列  S, T の編集距離とは、文字列  S に以下の操作を好きな順序で行って文字列  T に一致させるための、操作回数の最小値です。

  • 置換: S の任意の1文字を選んで、それを任意の1文字に置き換える。
  • 削除: S の任意の1文字を選んで、それを取り除く。
  • 挿入: S の任意の位置に、任意の1文字を挿入する。

この3操作は今回の問題と同じですね。これは以下のようなDPで解くことができます。

  •  dp\lbrack i \rbrack\lbrack j \rbrack = 文字列  S の前から  i 文字目までを文字列  T の前から  j 文字目までに一致させるための操作回数の最小値

このDPにおいて、文字列  S の文字をそのまま採用することと、上記の3操作を行うことは以下のような遷移で表現できます。

  • そのまま: S\lbrack i+1\rbrack T\lbrack j+1\rbrack に一致する時に限り、 dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack
  • 置換: dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1
  • 削除: dp\lbrack i+1 \rbrack\lbrack j \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1
  • 挿入: dp\lbrack i \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1

遷移は全て「より小さければ更新」です。この計算量は  O(|S|\times |T|) です。

「yahoo」のループを考えよう

さて今回の問題です。目標とする文字列は yahoo の繰り返しで、問題文の上では  T の長さがどこまでも大きくなる可能性があります。さらに、 |S| \le 10^{5} という制約から2乗オーダーのDPは間に合いそうにありません。

しかし逆に言うと、 yahoo は何周繰り返していようと条件判定には関係ないので、周回数の情報は忘れてしまうことができます。つまり状態定義はこうです。

  •  dp\lbrack i \rbrack\lbrack j \rbrack = 文字列  S の前から  i 文字目までを、「yahoo を0周以上繰り返した後、末尾に yahoo の途中まで  j 文字が中途半端に付いているような文字列」にするための操作回数の最小値

このDPの遷移は先ほどの編集距離DPとほぼ同じです。相違点は  j 0, 1, 2, 3, 4 の値しか取らず、 4 の次は  0 に戻ります。これは末尾の yaho の後に o を付けることに対応します。

ここで少し注意すべきは「挿入」の遷移で、 dp\lbrack i \rbrack\lbrack j+1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + 1 と遷移するため同じ  i での遷移となります。この遷移はどこかで止めないと無限に回りますが、1周以上の文字列を連続で挿入することは無駄なので、それぞれの  dp\lbrack i \rbrack\lbrack j \rbrack からの挿入の遷移として1~4文字の挿入だけを考えれば十分です。

このときの具体的実装として、例えば以下のような遷移が素直です。

  • 遷移元の  dp\lbrack i \rbrack\lbrack j \rbrack それぞれについて挿入文字数  k=1, ..., 4 を全部試し、 dp\lbrack i \rbrack\lbrack (j+k)\% 5 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack j \rbrack + k と遷移する

この他に、公式解説のように「遷移を2周回す」という手があります。これは

  •  dp\lbrack i \rbrack\lbrack 1 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 0 \rbrack + 1
  •  dp\lbrack i \rbrack\lbrack 2 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 1 \rbrack + 1
  • ...
  •  dp\lbrack i \rbrack\lbrack 0 \rbrack \leftarrow dp\lbrack i \rbrack\lbrack 4 \rbrack + 1

という遷移を順番に回していくもので、

  •  0\to 1\to 2\to 3\to 4\to 0\to 1\to 2\to 3

と2周回すことで先ほどの  j = 0, 1, ..., 4 から  k=1, ..., 4 文字を挿入する操作が全パターン含まれるようになります。

どちらにせよ、yahoo の文字数5を定数とするならばこのDPは  O(|S|) で動作し、 dp\lbrack |S| \rbrack\lbrack 0 \rbrack として答えを求めることが出来ます。

ACコード

遷移先などの候補として「ループして自分より前のインデックスに遷移することはあるが、1周は超えない」という状況になったときには、文字列や数列を2倍して遷移を考えてみるとスマートに処理できることが多いです。例えばこの問題などもそうですね。