ABC 417 G — Binary Cat

考察

連結するたびに文字列を展開すると、長さが指数的に増えてしまう。一方、必要なのは指定された一文字だけである。連結元と長さを保存し、その文字が左右どちらに由来するかを逆に辿る。さらに、長く続く側への移動をダブリングでまとめ、もう一方へ移る回数を抑える。

先頭だけを残し、照会位置を連結元へ戻す

上限を C=1018C=10^{18} とする。すべての照会位置は CC 以下なので、各連結の直後に先頭 CC 文字だけを残しても回答は変わらない。連結後の先頭 CC 文字に使われるのは、連結元それぞれの先頭 CC 文字までだからである。

以後は切り詰めた文字列を SvS_v と書き、その保存長を ℓv\ell_v とする。文字列そのものは保存せず、連結を表す頂点に左右の参照先と長さを持たせる。基底は S0=0,S1=1S_0=\texttt{0}, S_1=\texttt{1}、ℓ0=ℓ1=1\ell_0=\ell_1=1。クエリ ii で作る頂点は v=i+1v=i+1、左右の参照先は Li,RiL_i,R_i であり、

ℓv=min⁡(C,ℓLi+ℓRi)\ell_v=\min(C,\ell_{L_i}+\ell_{R_i})

と計算できる。参照先は必ず小さい番号なので、入力順に計算すればよい。同じ頂点を複数箇所から参照できるため、全体は木ではなく有向非巡回グラフ(DAG)になる。

照会状態を (A,B)(A,B) とし、「SAS_A の 1始まりの第 BB 文字を求める」と定める。左右の開始 offset は、先頭から何文字飛ばすかを表す 0始まりの値である。左は0、右は左の保存長となる。

現在の左右の参照先を u,wu,w とすると、B≤ℓuB\leq\ell_u なら (u,B)(u,B) へ、そうでなければ (w,B−ℓu)(w,B-\ell_u) へ移る。番号が0または1に着いたら、その番号が答えの文字である。ただし、一段ずつ戻るだけでは、片側へ一文字ずつ継ぎ足す構造で一照会に Θ(Q)\Theta(Q) 段を辿り、全体で O(Q2)O(Q^2) 時間かかる。

親に含まれる長さで heavy と light を選ぶ

深い参照を毎回辿らずに済ませたい。各頂点で、親の中に長く含まれる側への辺を heavy、もう一方を light と決め、heavy の連続だけをまとめて飛ばすことを考える。

ここで、参照先の保存長と、切り詰めた親に実際に含まれる長さは違う。親 vv の左右の参照先を u,wu,w として、含有長を

av=ℓu,bv=ℓv−ava_v=\ell_u,\qquad b_v=\ell_v-a_v

と置く。左は全部残り、右は先頭 bvb_v 文字だけが残る。av≥bva_v\geq b_v なら左を heavy、右を light とし、そうでなければ逆にする。同長なら左を heavy と決めておく。左が上限を占めると bv=0b_v=0 となり、右へ移る照会はない。

上限を小さくした独自例 C=10C=10 で、左右の保存長が6と10なら、親の保存長は10、含有長は6と4である。右が light だが、その参照先の保存長は10のままで、半減していない。第8文字は右の第2文字へ移る。この例が示すように、飽和後の回数評価には長さに加えて照会位置も使う必要がある。

未飽和の頂点では、light 先の保存長は親の半分以下になる。飽和した頂点でも、飽和した参照先へ light で移ると位置は C/2C/2 以下になり、次の light 移動を終えると保存長も C/2C/2 以下へ下がる。この場合分けは「正当性」で証明する。結果として、一照会の light 移動は高々60回である。

heavy の到達先と累積 offset を倍増する

各頂点 vv の heavy 先を h(v)h(v)、その開始 offset を xvx_v とする。heavy が左なら xv=0x_v=0、右なら xv=avx_v=a_v である。

vv から heavy を 2k2^k 回辿った到達先を Uv,kU_{v,k}、途中の開始 offset の合計を Dv,kD_{v,k} とする。0段目は一回分なので、

Uv,0=h(v),Dv,0=xvU_{v,0}=h(v),\qquad D_{v,0}=x_v

となる。二つの同じ長さの移動をつなぐには、前半の到着先 m=Uv,km=U_{v,k} から後半を始める。

Uv,k+1=Um,k,Dv,k+1=Dv,k+Dm,k.\begin{aligned} U_{v,k+1}&=U_{m,k},\\ D_{v,k+1}&=D_{v,k}+D_{m,k}. \end{aligned}

両方の移動が存在するときだけ表を埋め、基底0・1から出る辺や、途中で基底に着いて歩数が足りない欄は「存在しない」とする。参照先の番号は小さいため、新頂点の表を入力順に O(log⁡Q)O(\log Q) 時間で作れる。

到達先を t=UA,kt=U_{A,k}、累積 offset を d=DA,kd=D_{A,k} とすると、まとめて移動できる条件は

d<B≤d+ℓtd<B\leq d+\ell_t

である。つまり、1始まりの文字位置が区間 [d+1,d+ℓt][d+1,d+\ell_t] に入るかを調べる。成立すれば (A,B)←(t,B−d)(A,B)\leftarrow(t,B-d) と更新する。親の末尾で切り詰められる部分は、常に B≤ℓAB\leq\ell_A を満たすことから照会に現れない。

小例として T=01T=\texttt{01}、M=1+T=101M=\texttt{1}+T=\texttt{101}、V=0+M=0101V=\texttt{0}+M=\texttt{0101} とする。ここで ++ は連結を表す。V→M→TV\to M\to T はともに右への heavy 移動で、offset はそれぞれ1。二回分の表の到達先は TT、累積 offset は2であり、VV 内では TT が第3〜4文字に当たる。第3文字を照会すると、二回分をまとめて TT の第1文字へ移れる。

一回の heavy 走査の後、light を一辺だけ進む

クエリ ii では、表を作ってから (A,B)=(i+1,Xi)(A,B)=(i+1,X_i) で照会を始める。段 k=⌊log⁡2Q⌋,…,0k=\lfloor\log_2 Q\rfloor,\ldots,0 を大きい順に一度ずつ調べ、存在する表の区間に位置が入る場合だけ移動する。途中で基底0・1に着いたら直ちに答えを返す。

heavy の経路に沿って、照会位置を含む区間は途中まで連続する。一度その区間から外れると、さらに先の heavy 先にも同じ位置は含まれない。そのため、大きい段から調べる走査で可能な heavy 移動をすべて済ませられる。走査後も基底でなければ、次の heavy 一辺は選べず、位置は light 側にある。light 先へ、その辺の offset を引いて一回移り、再び大きい段から走査する。

先ほどの VV の第3文字なら、二回分を飛んで TT の第1文字に着く。TT は左右同長なので左が heavy で、その先は基底0となる。VV の第2文字なら、二回分の区間には入らないが、一回分では MM の第1文字へ移れる。そこでは heavy の TT に入らないので、light の基底1へ移って終了する。

典型の発動条件

heavy-light decompositionの考え方

発動条件: 分岐を辿る照会で、一方の辺を選ぶ回数に対数上界を付けられ、残る長い連続移動をまとめたいとき。

含まれる量が小さい側を light とする。ただし、切り詰めや共有がある構造では、その量と参照先全体の大きさが一致するかを確かめる。本問では照会位置の単調性も使って回数を抑える。

binary lifting

発動条件: 各状態の次の移動先が一意で、移動中の値も合成できるとき。本問の heavy 先は頂点だけで決まり、累積 offset は加算で合成できる。

移動可能かの条件が経路上で途中まで成立するなら、大きい段から表を試して、条件を満たす最遠の到達先を探せる。

saturating length

発動条件: 暗黙文字列の先頭からの照会位置に上限があり、それより後ろの情報が、後続操作でも回答に影響しないとき。

連結では先頭の長さだけを上限で飽和できる。反転や末尾からの照会など、捨てた部分を再び参照する操作へは、そのまま適用できない。

問題固有の要素

本問では文字列の先頭だけを残すため、左の参照先は全部含まれ、右の参照先は途中で切れる。通常の木のサイズによる半減の議論をそのまま使うと、この非対称性を落としてしまう。

そこで状態を「頂点と照会位置」の対で見る。飽和したまま light を辿っても、照会位置が前半へ移ることで、次の light 移動から長さの半減へ接続できる。値を上限で丸めた後の償却解析では、丸めた値だけで減少を示せるかを確かめ、足りなければ操作が参照する位置も追う。

正当性

切り詰めと一辺の移動は照会文字を保つ

連結元の先頭 CC 文字より後ろは、連結結果でも第 C+1C+1 文字以降にしか現れない。したがって各連結の直後に切り詰めても、照会可能な先頭部分は元の問題と一致する。

状態 (A,B)(A,B) では常に 1≤B≤ℓA1\leq B\leq\ell_A を保つ。左右の含有区間は親の第1文字から第 ℓA\ell_A 文字までを重複なく覆うので、位置を含む側へ開始 offset を引いて移れば、同じ文字を指し続ける。右の含有長が0なら、その側は選ばれない。

飽和した長さには照会位置を組み合わせる

一辺を移動する前後を (A,B),(A′,B′)(A,B),(A',B') とする。開始 offset は非負なので B′≤BB'\leq B。保存長も、未飽和の親では左右の和、飽和した親では上限 CC 以下なので、どちらの辺でも増えない。

light 移動について、次の三つを示す。

  1. 親が未飽和の場合。 ℓA<C\ell_A<C なら両方の参照先が全部含まれる。light 先の保存長は小さい方の含有長そのものなので、ℓA′≤ℓA/2\ell_{A'}\leq\ell_A/2 となる。
  2. 飽和した親から、飽和した light 先へ移る場合。 左の参照先の保存長が CC なら、含有長は左が CC、右が0となり、左は heavy である。従って飽和した light 先は右に限られる。左の含有長を aa、右を b=C−ab=C-a とすると、右が light なので b≤C/2b\leq C/2。移動後の位置は B′=B−a≤C−a=b≤C/2B'=B-a\leq C-a=b\leq C/2 となる。保存長は減らなくても、照会位置は前半へ移る。
  3. 親が飽和し、位置が既に B≤C/2B\leq C/2 の場合。 右が light なら左の含有長は a≥C/2a\geq C/2 であり、右へ行くには B>aB>a が必要なので選べない。light へ行くなら左で、その保存長は含有長 a≤C/2a\leq C/2 に等しい。従って ℓA′≤C/2\ell_{A'}\leq C/2 となる。

これで light 回数を数えられる。最初から未飽和なら、light のたびに保存長が半減する。飽和した状態での最初の light 移動で未飽和になった場合も、その一回を除けば同じである。

最初の light 移動後も飽和していた場合は、2より照会位置が C/2C/2 以下になる。その後 heavy を何回進んでも位置は増えない。次の light 移動時に親がまだ飽和していれば3、既に未飽和なら1を使い、二回目の light 移動後には保存長が C/2C/2 以下になる。以降は通常の半減が続く。

従って C=1018C=10^{18} では、前者は 1+⌊log⁡2(C−1)⌋=601+\lfloor\log_2(C-1)\rfloor=60 回以下、後者も 2+⌊log⁡2(C/2)⌋=602+\lfloor\log_2(C/2)\rfloor=60 回以下である。途中で基底へ着けば、さらに少なくなる。

ダブリングは一辺ずつ辿る操作をまとめている

表の漸化式は、前半の到達先から後半を辿り、二つの開始 offset を足している。したがって UA,kU_{A,k} と DA,kD_{A,k} は、heavy を一辺ずつ 2k2^k 回辿った結果を表す。

各参照先の先頭部分が、移動元の連続区間として含まれる。さらに先へ辿ってもその区間から外へは出ず、末尾での切り詰めは区間の右端を短くするだけである。到達先 tt、累積 offset dd に対し、出発点内で実際に残る区間は [d+1,min⁡(ℓA,d+ℓt)][d+1,\min(\ell_A,d+\ell_t)]。現在位置は既に B≤ℓAB\leq\ell_A を満たすので、本文の d<B≤d+ℓtd<B\leq d+\ell_t が、一辺ずつ同じ heavy 経路を選べる条件になる。

経路を深く進むほど区間は狭くなるので、この条件の成立は途中まで連続する。大きい段からの走査はその最長の連続部分を選び終え、基底でなければ次に選ぶべき一辺は light となる。どの移動も照会文字を保ち、頂点番号は狭義に減るため、最終的に基底0または1へ停止し、正しい文字を返す。

実装上の注意

  • 位置 BB は1始まり、offset dd は0始まりで統一する。移動判定は d<B≤d+ℓtd<B\leq d+\ell_t。0始まりの位置へ直す実装なら、全体を d≤B<d+ℓtd\leq B<d+\ell_t にそろえる。
  • 長さの加算は min⁡(C,ℓu+ℓw)\min(C,\ell_u+\ell_w) とする。offset も CC で飽和させてよい。真の累積 offset が CC 以上なら、先頭の1文字目でも出発点の第 C+1C+1 文字以降になる。保存値が d=Cd=C なら条件 d<Bd<B を満たさず、上限超の移動が合法になることはない。offset は非負なので、合成後にこの判定が逆転することもない。
  • 飽和した二値の和も最大 2C2C。区間の右端 d+ℓtd+\ell_t も含めて64 bit符号付き整数に収まる。整数を正確に表せない型で 101810^{18} を扱わない。
  • 表には k=0,…,⌊log⁡2Q⌋k=0,\ldots,\lfloor\log_2 Q\rfloor の段があればよい。基底には出辺を作らず、存在しない欄を合成しない。照会中に基底へ着いたら、その場で終了する。
  • 左右が同じ参照先でも、親内の出現位置は別である。左の offset は0、右は左の保存長を使う。同長のときの heavy 選択を前処理と照会で統一し、右の含有長0も扱う。

復習の核

  • 巨大な連結文字列では、まず文字の内容と構成を分け、指定位置を連結元へ戻すことを考える。そのままでは深さが時間になる点まで確認する。
  • 切り詰めた親に含まれる量と、参照先全体の大きさを混同しない。丸めた長さが減らない遷移では、照会位置など別の単調な量を探す。
  • 長い一意な移動は到達先と累積 offset の対でまとめる。位置条件で最長の移動を探すには、条件が経路の途中まで連続して成立することを証明する。

計算量と制約

時間

各頂点の長さ・左右の含有長・heavy/light の決定は O(1)O(1)。ダブリング表は頂点ごとに O(log⁡Q)O(\log Q) 段なので、前処理の合計は O(Qlog⁡Q)O(Q\log Q) 時間となる。入力を読みながら、その頂点の表を構築できる。

一照会では light 移動が O(log⁡C)O(\log C) 回で、その前後に行う heavy 走査一回が O(log⁡Q)O(\log Q) 時間。従って一照会は O(log⁡Qlog⁡C)O(\log Q\log C)、全 QQ 件と表の構築を合わせて O(Qlog⁡Qlog⁡C)O(Q\log Q\log C) 時間である。Q=1Q=1 では一段だけ持ち、定数時間で処理する。

空間

Q+2Q+2 頂点に左右の参照先・保存長・heavy/light を持ち、各頂点の各段に到達先と累積 offset を保存するので、O(Qlog⁡Q)O(Q\log Q)。照会は反復で処理でき、表以外の作業領域は O(1)O(1) でよい。

制約との対応

2026-10-29に公式問題文・個別公式解説を再照合した。1≤Q≤5×1051\leq Q\leq5\times10^5、0≤Li,Ri≤i0\leq L_i,R_i\leq i、1≤Xi≤10181\leq X_i\leq10^{18} で、照会位置は生成文字列の長さ以下と保証される。時間制限は6秒、メモリ制限は1024 MiBである。

C=1018C=10^{18} とすれば light は高々60回、ダブリング表は k=0,…,18k=0,\ldots,18 の19段で足りる。各欄には文字列本体ではなく、頂点番号と64 bitの offset を保存する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 圧縮・反復・再帰文字列へ問い合わせる

主題
追加で学ぶ技能
    なし
    既習技能
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
    • doubling・binary lifting: 一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。

    主タグ: 再帰・圧縮・入れ子文字列の走査

    補助タグ: 単調進行による償却解析 doubling・binary lifting

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

    学習の位置

    体系上の位置: 圧縮・反復・再帰文字列へ問い合わせる

    • 圧縮・反復・再帰または入れ子で定義された文字列を展開せず、block長・対応区切り・作用から照会・変換・評価できる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • doubling・binary lifting — 決定的遷移の2^k回後と累積値を合成し、巨大回数のjumpを二進分解で求める。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

    • 明示された文字列への接尾辞索引の構築。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題