ARC227 C - Follow the Letters

考え方

この問題のポイントは、どんな指示を出そうが人の追い抜きが発生しないこと。
ということは、島 $1$ の人が島 $N$ の人に後ろから追い付けば、それは $1$ つの島に全員集合している。
よって、これが可能であるような $S$ の条件を考えてみる。

島 $N$ の人がなるべく進まない方が嬉しいので、この人が $1$ しか進まないように指示を出すことにする。
「$N$ 回の指示で島 $N$ からの人がちょうど $1$ 周したとき、他の誰かがちょうど $1$ 周」していたら不可能。
そうでない場合、$1$ 周ごとに島 $1$ からの人は $N+1$ 個以上進むので、$N-1$ 周以内に追い付く。

では、「$N$ 回の指示で島 $N$ からの人がちょうど $1$ 周したとき、他の誰かがちょうど $1$ 周」の発生条件は。
それは、その人の次の島の文字が常に $N$ からの人と同じである場合。
つまり、$S$ に周期性がある場合である。
この場合は、$1$ 周期分を同様の方法で $1$ つの島に集合させることまではできる。
しかし、ちょうど $1$ 周期差の位置にいる人同士は必ず同じマス数進むため、合流は不可能。

よって、以下のように解けばよい。

まず、文字列の最短周期を割り出す。
$1$ 文字から順に、「その文字数差の位置が全て同じ文字の組になっているか」を確認する。
初めて全て同じ文字の組になっていた文字数が周期長である。
最終的に $N$ 文字は絶対に判定を通るため、この探索は必ず終了する。
$N$ を周期長で割った商が周期の反復回数であり、それが $1$ つめに答えるべき $K$ である。

次に、合流までの操作列を作る。
これは、まず $S$ のうち $1$ 周期分だけ取り出し、$N$ の値もそれに揃える。
島 $N$ にいる人と、島 $1$ にいる人を用意する。
島 $N$ にいる人が $1$ マスずつしか進まないように指示を出し、両者の移動をシミュレーションする。
両者が同じマスに来るまで繰り返すと、$N(N-1)$ 回以内に操作が終わる。
こうしてできた文字列の長さが $2$ つめに答える値で、文字列そのものが $3$ つめに答えるもの。

計算量は $O(N^2)$ である。

具体例での動作

次の例を考える。

n: 12
s: "axabxbaxabxb"

まず、文字列の最短周期を調べる。

$l=1$ では、位置 $0$ と $1$ の文字が a と x で異なるため、周期ではない。

$l=2$ では、位置 $1$ と $3$ の文字が x と b で異なるため、周期ではない。

$l=3$ では、位置 $0$ と $3$ の文字が a と b で異なるため、周期ではない。

$l=4,5$ は $12$ の約数ではないため、候補にならない。

$l=6$ では、$6$ 文字差の位置同士が全て同じ文字になっている。

よって、最短周期は axabxb の $6$ 文字である。
周期の反復回数は $12/6=2$ なので、$K=2$ となる。

以後は $1$ 周期分だけを取り出し、次の状態で操作列を構築する。

n: 6
s: "axabxb"

0-indexed で、最前を行く人の位置を $5$、最後尾を行く人の位置を $0$ とする。

最前を行く人を $1$ マスだけ進めるように文字を選び、その文字まで最後尾の人も進める。

$4$ 回目の操作で両者が同じ位置になった。
人同士の追い抜きは発生しないため、この時点で $1$ 周期分の人が同じ島に集合している。

したがって、$K=2$、操作回数は $4$、操作列は axab となる。

注意点

特になし。

別解

特になし。