ABC 312 Ex — snukesnuke

考察

反復して作った文字列を保存する代わりに、繰り返しの最小単位と、その何個分の長さかを保存する。同じ最小単位を持つ文字列同士だけが衝突するので、単位ごとに「使われていない最小の倍数を探す」問題へ分けられる。さらに、同じ刻みで前に調べた倍数を再び調べないよう、次の探索位置を残しておく。

反復文字列を根と指数へ分ける

問題文どおりに各人について Si,Si2,Si3,…S_i,S_i^2,S_i^3,\ldots を生成すると、文字列が長くなるうえ、同じ候補との比較を繰り返す。しかも、例えば ab\texttt{ab} と abab\texttt{abab} のように、異なる入力文字列から同じあだ名ができる。入力文字列そのものより、その繰り返し構造に注目したい。

文字列を整数回の反復として表す最短の単位を primitive root(以下、根)と呼ぶ。SiS_i の長さを ℓi\ell_i、根の長さを pip_i とする。Z 配列では、0始まりの位置 pp から接頭辞と一致する長さを Zi[p]Z_i[p] とする。p=1,…,ℓip=1,\ldots,\ell_i を順に調べ、

p∣ℓi,p=ℓi または Zi[p]≥ℓi−p\begin{gathered} p\mid\ell_i,\\ p=\ell_i\ \text{または}\ Z_i[p]\geq\ell_i-p \end{gathered}

を満たす最初の pp を pip_i に選ぶ。後半は長さ pp ずつずらして文字が一致する条件、前半は末尾まで欠けずに反復できる条件である。p=ℓip=\ell_i は必ず成功し、この場合は Z 配列の範囲外を参照しない。得られる根と指数を

Ri=Si[0:pi],ni=ℓi/piR_i=S_i[0:p_i],\qquad n_i=\ell_i/p_i

と書く。ここで Si[0:pi]S_i[0:p_i] は先頭 pip_i 文字を表し、Si=RiniS_i=R_i^{n_i} となる。例えば ababa\texttt{ababa} は周期2を持つが、2は長さ5を割らず、根は文字列自身である。一方、abab\texttt{abab} の根は ab\texttt{ab}、指数は2となる。

非空文字列の根は一意で、整数回反復しても変わらない。したがって二つのあだ名が一致する必要十分条件は、根と総指数がともに等しいことである。異なる根の間に衝突はなく、同じ根 RR のグループでは、入力指数 nin_i に対して未使用の最小の正の倍数 mm を選べばよい。答えは総指数 mm そのものではなく、元の文字列の反復回数 ki=m/nik_i=m/n_i である。

指数の上界を先に求める

配列で使用済み判定をするため、指数がどこまで増えるかを確認する。総入力長を L=∑i=1NℓiL=\sum_{i=1}^N\ell_i、根 RR のグループに属する入力指数の総和を

WR=∑i:Ri=RniW_R=\sum_{i:R_i=R}n_i

と置く。これは最終的なあだ名の指数の総和ではない。

このグループで、処理済みの入力指数の和を AA、使用済み指数の最大値を MM とする。まだ何も使っていなければ両方0である。次の入力指数が nn のとき、MM を超える最初の nn の倍数は必ず未使用なので、選ぶ最小未使用倍数 mm は

m≤n(⌊M/n⌋+1)≤M+n\begin{aligned} m&\leq n\left(\left\lfloor M/n\right\rfloor+1\right)\\ &\leq M+n \end{aligned}

を満たす。M≤AM\leq A と仮定すれば、新しい最大値も max⁡(M,m)≤A+n\max(M,m)\leq A+n となる。初期状態からの帰納法により、すべての選択指数は、その時点までの入力指数の和以下、従って WRW_R 以下である。

さらに、根の長さは1以上なので、全グループの領域を足しても

∑RWR=∑ini≤∑iℓi=L\sum_R W_R=\sum_i n_i\leq\sum_i\ell_i=L

となる。根ごとに WRW_R に比例する配列を用意すれば、合計は線形領域で済む。

同じ刻みの探索を続きから再開する

根 RR ごとに、指数 mm を使ったかを表す真偽配列 usedR[m]\mathrm{used}_R[m] と、刻み nn の次候補 nextR[n]\mathrm{next}_R[n] を持つ。使用済み指数は増える一方なので、一度使われたと分かった倍数を次の人のために調べ直す必要はない。ただし、保存した次候補が別の刻みの処理で使われることはあるため、再開時にも使用済み判定が必要である。

先に全入力を根と指数へ正規化し、各グループの WRW_R を集計する。その後の処理は次のとおりである。

  1. 根ごとに長さ WR+1W_R+1 の二つの配列を作る。使用済み配列をすべて偽にし、1≤n≤WR1\leq n\leq W_R に対して nextR[n]=n\mathrm{next}_R[n]=n と初期化する。添字0は使わない。
  2. 人を元の入力順に処理する。根が RR、指数が nn なら、まず m=nextR[n]m=\mathrm{next}_R[n] とする。
  3. usedR[m]\mathrm{used}_R[m] が真の間、m←m+nm\leftarrow m+n と進める。最初に偽となった mm を使用済みにする。
  4. nextR[n]=m+n\mathrm{next}_R[n]=m+n と更新し、ki=m/nk_i=m/n を答えとして保存する。他の刻みのポインタは変えない。

根が ab\texttt{ab} で、入力指数が順に (1,2,1,2)(1,2,1,2)、すなわち入力文字列が ab,abab,ab,abab\texttt{ab},\texttt{abab},\texttt{ab},\texttt{abab} の場合を追う。表の次候補は、各行の処理後の値を刻み1・刻み2の順で示す。

入力 nn採用 mm答え kk次候補
111(2,2)(2,2)
221(2,4)(2,4)
133(4,4)(4,4)
242(4,6)(4,6)

3人目の探索は保存された2から始めるが、その2は2人目が使っているため3へ進む。こうして、異なる刻みの衝突を取り逃さず、同じ刻みでの探索は後戻りしなくなる。

典型の発動条件

primitive root による反復文字列の正規化

発動条件: 文字列を整数回反復した結果の等価性・衝突を扱うとき。

最短の反復単位と指数へ分けると、同じ根の中で整数だけを比較できる。端が欠けてもよい周期と、文字列全体を作る反復単位を区別し、周期が長さを割る条件を確かめる。

次候補ポインタの償却

発動条件: 同じ刻みの最小未使用値を何度も探し、使用済みの値が削除されないとき。

刻みごとの次候補を残し、一度通過した値を再訪しない。回数を評価するにはポインタの単調性だけでなく、値の上界が必要になる。独立したグループへ分けた場合は、各グループの入力に応じた上界を作ってから合算する。

問題固有の要素

あだ名そのものは大きく伸びるが、その総指数はグループ内の入力指数の和以下に抑えられる。「以前の最大値を超える最初の倍数なら必ず使える」と考えると、一回の増加幅を入力指数で抑えられる。

文字列の正規化で整数問題へ変えるだけでなく、その整数の値域も入力サイズで抑える。この二段階が、倍数探索の償却と真偽配列による使用済み判定をつなぐ。

正当性

最小の完全反復単位を選んでいるので、得られる根はさらに短い文字列の反復には分解できない。非空文字列の根の一意性と、反復しても根が変わらない性質から、異なる根のあだ名は一致しない。同じ根では総指数が等しいとき、かつそのときに限ってあだ名が一致する。

各グループ・刻み nn について、次候補は正の nn の倍数であり、それより小さい正の nn の倍数はすべて使用済み、という不変条件を保つ。初期値 nn より小さい正の倍数はない。探索中は使用済みの候補だけを飛ばすため、最初に見つかる未使用の mm が最小である。これを登録して次候補を m+nm+n にすれば、不変条件は次回も保たれる。別の刻みの処理は使用済み指数を増やすだけなので、この性質を壊さない。

考察で示した m≤M+nm\leq M+n の帰納法により、各選択指数は WRW_R 以下である。従って未使用倍数の探索は配列の範囲内で必ず停止する。mm が最小の未使用倍数なので、m/nm/n は問題文が求める最小の反復回数となる。人を入力順に処理するため、すべての答えが問題文の手順と一致する。

実装上の注意

  • 最小周期には長さを割る条件も必要である。ababa\texttt{ababa} を根 ab\texttt{ab} のグループに入れない。長さ1や反復に分解できない文字列では、根は文字列自身、入力指数は1となる。
  • 二つの配列は根ごとに WR+1W_R+1 要素確保する。全根に対して長さ L+1L+1 の配列を作ると、領域と初期化時間の線形上界を失う。根を集計する前処理では、各人のグループ番号と入力指数を保存しておく。
  • 次候補配列の添字は刻み nn、格納する値は総指数 m+nm+n である。最後の更新値は WRW_R を超えることがあるが、その値を使用済み配列へ直ちに照会しない。同じ刻みの入力が後に残っていれば、上の不変条件と指数上界から、再開値も選択値も WRW_R 以下となる。格納値自体は最大 2WR2W_R である。
  • 使用済み配列と次候補は根ごとに独立させ、各人の処理では根の文字列を再検索せず、保存したグループ番号で参照する。出力は mm ではなく m/nm/n である。

復習の核

  • 反復文字列の比較では、まず「最小の反復単位と総指数が同じ」という必要十分条件を探す。端が欠ける周期を、そのまま反復単位にはしない。
  • 単調なポインタを償却するときは、どこまで進むかも証明する。最初の未使用倍数は、以前の最大使用値を超える最初の倍数以下である。
  • 独立したグループの計算量は、グループごとの入力サイズで評価してから足す。候補の検査回数と、一検査のデータ構造の費用を分けて考える。

計算量と制約

時間

L=∑iℓiL=\sum_i\ell_i とする。Z 配列と周期候補の走査、根の切り出しは全入力で O(L)O(L) 時間である。

根の分類には、根の文字列をキー、グループ番号を値とする、辞書順比較の平衡木を使う。根 RiR_i の検索・挿入では O(log⁡(N+1))O(\log(N+1)) 回比較し、各比較は高々 O(∣Ri∣+1)O(|R_i|+1) 時間かかる。∑i∣Ri∣≤L\sum_i|R_i|\leq L、N≤LN\leq L より、文字列比較を含めても全体で O(Llog⁡(L+1))O(L\log(L+1)) 時間である。分類時に各人のグループ番号を保存し、倍数探索中の辞書検索は行わない。

根 RR に対して、同じ刻み nn のポインタは nn から始まり、使用済みの候補を飛ばしたときも、候補を採用したときも nn ずつ進む。検査する値は WRW_R 以下で、同じ値を再訪しない。従って、その刻みで検査する回数は成功した検査も含めて高々 ⌊WR/n⌋\lfloor W_R/n\rfloor 回である。出現しない刻みも含めて上から評価すると、グループ内の検査回数は

∑n=1WR⌊WRn⌋≤WR∑n=1WR1n≤WR(1+log⁡WR)\begin{aligned} \sum_{n=1}^{W_R}\left\lfloor\frac{W_R}{n}\right\rfloor &\leq W_R\sum_{n=1}^{W_R}\frac1n\\ &\leq W_R(1+\log W_R) \end{aligned}

となる。各グループに同じ大域上限 LL を割り当てて足すのではなく、∑RWR≤L\sum_R W_R\leq L を使って

∑RWR(1+log⁡WR)≤(1+log⁡L)∑RWR≤L(1+log⁡L)\begin{aligned} \sum_R W_R(1+\log W_R) &\leq (1+\log L)\sum_R W_R\\ &\leq L(1+\log L) \end{aligned}

と合算する。真偽配列の使用済み判定・登録と、配列での次候補の参照・更新は一回 O(1)O(1)。配列の確保・初期化も、グループ数が ∑RWR\sum_R W_R 以下なので合計 O(L)O(L) 時間である。入力・出力まで合わせ、全体は最悪 O(Llog⁡(L+1))O(L\log(L+1)) 時間、通常の表記では O(Llog⁡L)O(L\log L) となる。L=1L=1 の場合も定数時間で扱える。

使用済み指数を真偽配列ではなく平衡木の集合(例えば C++ の std::set)へ置く場合は、一検査の対数時間を加え、O(L(log⁡(L+1))2)O(L(\log(L+1))^2) となる。公式解説はこの集合の費用を含めて評価している。ハッシュ集合で一検査を定数時間と評価するなら期待時間であり、ここで示した配列による最悪時間の保証とは区別する。

空間

入力文字列と Z 配列、根をキーとする辞書、各人のグループ番号・入力指数・答えを合わせて O(L)O(L)。根ごとの二つの配列は合計 O(∑R(WR+1))=O(L)O(\sum_R(W_R+1))=O(L) なので、全体も O(L)O(L) 領域である。完成したあだ名の文字列は生成しない。

制約との対応

2026-10-29に公式問題文・個別公式解説を再照合した。N≥1N\geq1、各 SiS_i は非空の英小文字列で、L=∑i∣Si∣≤2×105L=\sum_i|S_i|\leq2\times10^5。時間制限は2秒、メモリ制限は1024 MiBである。

各グループの選択指数は WR≤LW_R\leq L、次候補の保存値は 2WR≤4×1052W_R\leq4\times10^5 であり、32 bit符号付き整数に収まる。全員が同じ文字列でも同じ刻みのポインタを引き継ぎ、根がすべて異なる場合も各根に割り当てる領域の合計は線形となる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

snukesnuke の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 文字列周期・primitive word

主題
  • 文字列周期・primitive word: prefix一致またはborderから最小periodを求め、文字列をprimitive rootと反復回数へ正規化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
    • Z algorithmによるprefix matching: 既知のZ-boxを再利用してZ arrayを線形時間で構成し、各位置から始まる接尾辞と文字列全体のprefixの最大一致長を、文字列連結によるprefix照合へ利用できる。

    主タグ: 文字列周期・primitive word

    補助タグ: 単調進行による償却解析 Z algorithmによるprefix matching

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 文字列周期・primitive word

    • prefix一致またはborderから最小periodを求め、文字列をprimitive rootと反復回数へ正規化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • Z algorithmによるprefix matching — 各位置からprefixと一致する最大長を既知のZ-boxから再利用し、全位置の一致長を線形時間で求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題