\(S\) の周期の繰り返し回数、つまり \(S\) を \(i\) 回 cyclic shift しても \(S\) になる \(i\) の数、がこの問題の答えである。これを \(K\) とする。

答えが \(K\) 以上であることは、上記の \(i\) に対応する人達が必ず合流不可能であることから示せる。 例えば S = abcdabcdabcd ならば \(K = 3(i = 1, 5, 9)\) なのだが、最初に島 \(1, 5, 9\) にいた人たちは常に同じ距離移動するので絶対に合流不可能である。

あとは \(K\) が達成できる操作列を構築すればよい。一例として、 \(S\) を \(N\) 回繰り返せばよい。

操作列 \(S\) で人がどう動くかを考えればよく、

• 上記の周期の終わり(上の例ならば島 \(4, 8, 12\))に対応する島にいた人はちょうど一周して帰ってくる
• それ以外の島にいた人は、必ず \(N + 1\) 個以上の島を移動する
• 一般に、人が別の人を追い抜くことがない

という事実を合わせると、\(S\) を \(N\) 回繰り返せば最終的にすべての人が周期の終わりの島に集合することがわかる。

余談

• S = abababab...abaab など、\(\Omega(N^2)\) 回の操作が必要な例が存在する。
• 答えの操作列のうち最小の長さ、も \(O(26N^2)\) 時間で求めることが可能である。
• この問題のジャッジ(出力検証機)は \(O(26N + L)\) 時間で動作する。