考察
反復して作った文字列を保存する代わりに、繰り返しの最小単位と、その何個分の長さかを保存する。同じ最小単位を持つ文字列同士だけが衝突するので、単位ごとに「使われていない最小の倍数を探す」問題へ分けられる。さらに、同じ刻みで前に調べた倍数を再び調べないよう、次の探索位置を残しておく。
反復文字列を根と指数へ分ける
問題文どおりに各人について を生成すると、文字列が長くなるうえ、同じ候補との比較を繰り返す。しかも、例えば と のように、異なる入力文字列から同じあだ名ができる。入力文字列そのものより、その繰り返し構造に注目したい。
文字列を整数回の反復として表す最短の単位を primitive root(以下、根)と呼ぶ。 の長さを 、根の長さを とする。Z 配列では、0始まりの位置 から接頭辞と一致する長さを とする。 を順に調べ、
を満たす最初の を に選ぶ。後半は長さ ずつずらして文字が一致する条件、前半は末尾まで欠けずに反復できる条件である。 は必ず成功し、この場合は Z 配列の範囲外を参照しない。得られる根と指数を
と書く。ここで は先頭 文字を表し、 となる。例えば は周期2を持つが、2は長さ5を割らず、根は文字列自身である。一方、 の根は 、指数は2となる。
非空文字列の根は一意で、整数回反復しても変わらない。したがって二つのあだ名が一致する必要十分条件は、根と総指数がともに等しいことである。異なる根の間に衝突はなく、同じ根 のグループでは、入力指数 に対して未使用の最小の正の倍数 を選べばよい。答えは総指数 そのものではなく、元の文字列の反復回数 である。
指数の上界を先に求める
配列で使用済み判定をするため、指数がどこまで増えるかを確認する。総入力長を 、根 のグループに属する入力指数の総和を
と置く。これは最終的なあだ名の指数の総和ではない。
このグループで、処理済みの入力指数の和を 、使用済み指数の最大値を とする。まだ何も使っていなければ両方0である。次の入力指数が のとき、 を超える最初の の倍数は必ず未使用なので、選ぶ最小未使用倍数 は
を満たす。 と仮定すれば、新しい最大値も となる。初期状態からの帰納法により、すべての選択指数は、その時点までの入力指数の和以下、従って 以下である。
さらに、根の長さは1以上なので、全グループの領域を足しても
となる。根ごとに に比例する配列を用意すれば、合計は線形領域で済む。
同じ刻みの探索を続きから再開する
根 ごとに、指数 を使ったかを表す真偽配列 と、刻み の次候補 を持つ。使用済み指数は増える一方なので、一度使われたと分かった倍数を次の人のために調べ直す必要はない。ただし、保存した次候補が別の刻みの処理で使われることはあるため、再開時にも使用済み判定が必要である。
先に全入力を根と指数へ正規化し、各グループの を集計する。その後の処理は次のとおりである。
- 根ごとに長さ の二つの配列を作る。使用済み配列をすべて偽にし、 に対して と初期化する。添字0は使わない。
- 人を元の入力順に処理する。根が 、指数が なら、まず とする。
- が真の間、 と進める。最初に偽となった を使用済みにする。
- と更新し、 を答えとして保存する。他の刻みのポインタは変えない。
根が で、入力指数が順に 、すなわち入力文字列が の場合を追う。表の次候補は、各行の処理後の値を刻み1・刻み2の順で示す。
3人目の探索は保存された2から始めるが、その2は2人目が使っているため3へ進む。こうして、異なる刻みの衝突を取り逃さず、同じ刻みでの探索は後戻りしなくなる。
典型の発動条件
primitive root による反復文字列の正規化
発動条件: 文字列を整数回反復した結果の等価性・衝突を扱うとき。
最短の反復単位と指数へ分けると、同じ根の中で整数だけを比較できる。端が欠けてもよい周期と、文字列全体を作る反復単位を区別し、周期が長さを割る条件を確かめる。
次候補ポインタの償却
発動条件: 同じ刻みの最小未使用値を何度も探し、使用済みの値が削除されないとき。
刻みごとの次候補を残し、一度通過した値を再訪しない。回数を評価するにはポインタの単調性だけでなく、値の上界が必要になる。独立したグループへ分けた場合は、各グループの入力に応じた上界を作ってから合算する。
問題固有の要素
あだ名そのものは大きく伸びるが、その総指数はグループ内の入力指数の和以下に抑えられる。「以前の最大値を超える最初の倍数なら必ず使える」と考えると、一回の増加幅を入力指数で抑えられる。
文字列の正規化で整数問題へ変えるだけでなく、その整数の値域も入力サイズで抑える。この二段階が、倍数探索の償却と真偽配列による使用済み判定をつなぐ。
正当性
最小の完全反復単位を選んでいるので、得られる根はさらに短い文字列の反復には分解できない。非空文字列の根の一意性と、反復しても根が変わらない性質から、異なる根のあだ名は一致しない。同じ根では総指数が等しいとき、かつそのときに限ってあだ名が一致する。
各グループ・刻み について、次候補は正の の倍数であり、それより小さい正の の倍数はすべて使用済み、という不変条件を保つ。初期値 より小さい正の倍数はない。探索中は使用済みの候補だけを飛ばすため、最初に見つかる未使用の が最小である。これを登録して次候補を にすれば、不変条件は次回も保たれる。別の刻みの処理は使用済み指数を増やすだけなので、この性質を壊さない。
考察で示した の帰納法により、各選択指数は 以下である。従って未使用倍数の探索は配列の範囲内で必ず停止する。 が最小の未使用倍数なので、 は問題文が求める最小の反復回数となる。人を入力順に処理するため、すべての答えが問題文の手順と一致する。
実装上の注意
- 最小周期には長さを割る条件も必要である。 を根 のグループに入れない。長さ1や反復に分解できない文字列では、根は文字列自身、入力指数は1となる。
- 二つの配列は根ごとに 要素確保する。全根に対して長さ の配列を作ると、領域と初期化時間の線形上界を失う。根を集計する前処理では、各人のグループ番号と入力指数を保存しておく。
- 次候補配列の添字は刻み 、格納する値は総指数 である。最後の更新値は を超えることがあるが、その値を使用済み配列へ直ちに照会しない。同じ刻みの入力が後に残っていれば、上の不変条件と指数上界から、再開値も選択値も 以下となる。格納値自体は最大 である。
- 使用済み配列と次候補は根ごとに独立させ、各人の処理では根の文字列を再検索せず、保存したグループ番号で参照する。出力は ではなく である。
復習の核
- 反復文字列の比較では、まず「最小の反復単位と総指数が同じ」という必要十分条件を探す。端が欠ける周期を、そのまま反復単位にはしない。
- 単調なポインタを償却するときは、どこまで進むかも証明する。最初の未使用倍数は、以前の最大使用値を超える最初の倍数以下である。
- 独立したグループの計算量は、グループごとの入力サイズで評価してから足す。候補の検査回数と、一検査のデータ構造の費用を分けて考える。
計算量と制約
時間
とする。Z 配列と周期候補の走査、根の切り出しは全入力で 時間である。
根の分類には、根の文字列をキー、グループ番号を値とする、辞書順比較の平衡木を使う。根 の検索・挿入では 回比較し、各比較は高々 時間かかる。、 より、文字列比較を含めても全体で 時間である。分類時に各人のグループ番号を保存し、倍数探索中の辞書検索は行わない。
根 に対して、同じ刻み のポインタは から始まり、使用済みの候補を飛ばしたときも、候補を採用したときも ずつ進む。検査する値は 以下で、同じ値を再訪しない。従って、その刻みで検査する回数は成功した検査も含めて高々 回である。出現しない刻みも含めて上から評価すると、グループ内の検査回数は
となる。各グループに同じ大域上限 を割り当てて足すのではなく、 を使って
と合算する。真偽配列の使用済み判定・登録と、配列での次候補の参照・更新は一回 。配列の確保・初期化も、グループ数が 以下なので合計 時間である。入力・出力まで合わせ、全体は最悪 時間、通常の表記では となる。 の場合も定数時間で扱える。
使用済み指数を真偽配列ではなく平衡木の集合(例えば C++ の std::set)へ置く場合は、一検査の対数時間を加え、 となる。公式解説はこの集合の費用を含めて評価している。ハッシュ集合で一検査を定数時間と評価するなら期待時間であり、ここで示した配列による最悪時間の保証とは区別する。
空間
入力文字列と Z 配列、根をキーとする辞書、各人のグループ番号・入力指数・答えを合わせて 。根ごとの二つの配列は合計 なので、全体も 領域である。完成したあだ名の文字列は生成しない。
制約との対応
2026-10-29に公式問題文・個別公式解説を再照合した。、各 は非空の英小文字列で、。時間制限は2秒、メモリ制限は1024 MiBである。
各グループの選択指数は 、次候補の保存値は であり、32 bit符号付き整数に収まる。全員が同じ文字列でも同じ刻みのポインタを引き継ぎ、根がすべて異なる場合も各根に割り当てる領域の合計は線形となる。
出典