いろはちゃんコンテスト Day2 H - 根室の巫女

お題箱より。

解法

Morris-Pratt法について

まず、公式解説（？）にも書いてあるMorris-Pratt法（MP）について触れておきます。私も実戦で使ったことはないのですが…ある長さ $N$ の文字列 $S$ があったときに、全ての $i=1, ..., N$ に対して以下の値を求めた数列 $B_{1}, ..., B_{N}$ を求めるアルゴリズムです。

$S$ の先頭 $i$ 文字だけからなる文字列を $s_{i}$ とする。 $i$ 未満の整数 $k$ であって、「 $s_{i}$ の先頭 $k$ 文字と末尾 $k$ 文字が一致する。」という条件を満たす $k$ の最大値を $B_{i}$ とする。

$k=i$ としてしまうと先頭 $k$ 文字と末尾 $k$ 文字は当然一致してしまうので、それ以外で最大のものを求めることに注意してください。

この数列は文字列検索を高速に行う際などに使うようです。丁寧な解説と具体的な実装は以下のブログ記事が分かりやすいです。

文字列の頭良い感じの線形アルゴリズムたち - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

※今回の「Morris-Pratt法とは何か」という説明は、上記記事に準じて書いています。Morris-Pratt法で調べると「上記の数列を活用して文字列検索を行うこと」をMorris-Pratt法と呼んでいたり、色々違ったことが書いていて私もよく分かりません…。

さて、上記の数列の定義はそのまま今回の問題で与えられる $B_{1}, ..., B_{N}$ の定義になっています。文字列から数列を求めるMP法とは逆に、この問題ではこのような数列を満たす元の文字列（数列ですが）を構成することになります。

解き方について

さて解き方ですが…公式解説（？）はよく分からないので、私が解いた（コンテスト後にTwitterで見た）解法ベースで書きたいと思います。

以降、数列 $A_{1}, ..., A_{N}$ を単に $A$ 、数列 $B_{1}, ..., B_{N}$ を単に $B$ と表記します。

最初にこの解法の大まかな流れを書いておきます。

$B$ として与えられた条件を満たすような解 $A$ が存在すると仮定し、その必要条件を用いて数列 $A$ を構成する。
構成した数列 $A$ に対してMorris-Pratt法を適用し、本当に条件を満たしているかを判定する。

必要条件を考える

まず条件を満たすような解 $A$ が存在すると仮定して、 $A$ が満たすべき必要条件を考えます。具体的には $B$ の「最大の」という条件を考えないことにすると、以下の必要条件が得られます。

$A$ の先頭 $i$ 要素だけからなる配列を $a_{i}$ とする。 $a_{i}$ の先頭 $B_{i}$ 要素と末尾 $B_{i}$ 要素は一致する。

これを元に、「同じ値である必要がある要素」をまとめていくことを考えましょう。例えば各インデックスを頂点とみなして、Union-Findを用いて以下のように辺を張れば、どの要素の値が同じ必要があるかを管理できます。

f:id:betrue12:20190525102625p:plain

ただしこの辺は合計で $\sum B_{i}$ 本あり、全て処理していると計算が間に合いません。

繋ぐべき辺を削減する

繋ぐ辺を削減しましょう。実は、「各 $i$ に対して、上記の両文字列の末尾だけを繋ぐ」という処理だけで、結果的にこれら全てのペアが同じ連結成分に属してくれることを示すことができます。その理由を説明します。

端的に言うと、「末尾以外のところは他のインデックスが繋いでくれる」というのが理由になっています。例えば1つ前のインデックス $j=i-1$ について考えると、これがちゃんとインデックス $B_{i}-1$ と連結になって欲しいです。

ここで少なくとも以下の図の赤いところについては値が一致していることから、必ず $B_{j} \ge B_{i}-1$ が成立します。

f:id:betrue12:20190525104055p:plain

これがもし $B_{j} = B_{i}-1$ だった場合は簡単で、インデックス $j$ に対して「末尾同士を繋ぐ」という処理をしたときにインデックス $B_{i}-1$ と繋がれます。

もし $B_{j} \gt B_{i}-1$ だった場合、直接繋がれることはありません。ですがこの場合、以下の図のようになっているはずです。

f:id:betrue12:20190525104911p:plain

図中の赤いところは全て一致しているので、そのインデックスを辿っていくことで必ず $B_{i}-1$ 文字目に辿り着きます。つまりこれらの辺を張っていくことで同じ連結成分に属するようにできます。

このように考えると、「各インデックスに対して一致してほしい部分数列の末尾同士を繋ぐ」という操作を全てのインデックスにすることで、末尾以外についても一致してほしいところは最終的に同じ連結成分に属してくれることが分かります。

数字を割り当てる

…というわけで、必要条件から「一致してほしいインデックス」が連結成分として求められました。これらに対して適当に数字を割り振っていきましょう。

このとき、違う連結成分なのに同じ数を割り当てることにメリットはありません。何故なら先ほどの必要条件は $B$ について「最大の」という条件を考えないようにしたものであり、より長い長さで $a_{i}$ の先頭と末尾が一致してしまうとアウトです。つまり「これ以上はなるべく一致してほしくない」わけです。それなら違う連結成分には違う数字を割り当てるほうが良いですね。

Moris-Pratt法で検証する

これで解の「候補」ができました。これまで見てきたように、作ってきた数列は必要条件を満たし、かつ十分性を最も満たしやすいように作ったものです。

これをMoris-Pratt法で検証し、得られた数列が $B$ と一致していればそれが答えです。一致しなかった場合は解がないと判定して良いです。

ACコード

Submission #5567680 - いろはちゃんコンテスト Day2

ARMERIA

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