考察
連結するたびに文字列を展開すると、長さが指数的に増えてしまう。一方、必要なのは指定された一文字だけである。連結元と長さを保存し、その文字が左右どちらに由来するかを逆に辿る。さらに、長く続く側への移動をダブリングでまとめ、もう一方へ移る回数を抑える。
先頭だけを残し、照会位置を連結元へ戻す
上限を とする。すべての照会位置は 以下なので、各連結の直後に先頭 文字だけを残しても回答は変わらない。連結後の先頭 文字に使われるのは、連結元それぞれの先頭 文字までだからである。
以後は切り詰めた文字列を と書き、その保存長を とする。文字列そのものは保存せず、連結を表す頂点に左右の参照先と長さを持たせる。基底は 、。クエリ で作る頂点は 、左右の参照先は であり、
と計算できる。参照先は必ず小さい番号なので、入力順に計算すればよい。同じ頂点を複数箇所から参照できるため、全体は木ではなく有向非巡回グラフ(DAG)になる。
照会状態を とし、「 の 1始まりの第 文字を求める」と定める。左右の開始 offset は、先頭から何文字飛ばすかを表す 0始まりの値である。左は0、右は左の保存長となる。
現在の左右の参照先を とすると、 なら へ、そうでなければ へ移る。番号が0または1に着いたら、その番号が答えの文字である。ただし、一段ずつ戻るだけでは、片側へ一文字ずつ継ぎ足す構造で一照会に 段を辿り、全体で 時間かかる。
親に含まれる長さで heavy と light を選ぶ
深い参照を毎回辿らずに済ませたい。各頂点で、親の中に長く含まれる側への辺を heavy、もう一方を light と決め、heavy の連続だけをまとめて飛ばすことを考える。
ここで、参照先の保存長と、切り詰めた親に実際に含まれる長さは違う。親 の左右の参照先を として、含有長を
と置く。左は全部残り、右は先頭 文字だけが残る。 なら左を heavy、右を light とし、そうでなければ逆にする。同長なら左を heavy と決めておく。左が上限を占めると となり、右へ移る照会はない。
上限を小さくした独自例 で、左右の保存長が6と10なら、親の保存長は10、含有長は6と4である。右が light だが、その参照先の保存長は10のままで、半減していない。第8文字は右の第2文字へ移る。この例が示すように、飽和後の回数評価には長さに加えて照会位置も使う必要がある。
未飽和の頂点では、light 先の保存長は親の半分以下になる。飽和した頂点でも、飽和した参照先へ light で移ると位置は 以下になり、次の light 移動を終えると保存長も 以下へ下がる。この場合分けは「正当性」で証明する。結果として、一照会の light 移動は高々60回である。
heavy の到達先と累積 offset を倍増する
各頂点 の heavy 先を 、その開始 offset を とする。heavy が左なら 、右なら である。
から heavy を 回辿った到達先を 、途中の開始 offset の合計を とする。0段目は一回分なので、
となる。二つの同じ長さの移動をつなぐには、前半の到着先 から後半を始める。
両方の移動が存在するときだけ表を埋め、基底0・1から出る辺や、途中で基底に着いて歩数が足りない欄は「存在しない」とする。参照先の番号は小さいため、新頂点の表を入力順に 時間で作れる。
到達先を 、累積 offset を とすると、まとめて移動できる条件は
である。つまり、1始まりの文字位置が区間 に入るかを調べる。成立すれば と更新する。親の末尾で切り詰められる部分は、常に を満たすことから照会に現れない。
小例として 、、 とする。ここで は連結を表す。 はともに右への heavy 移動で、offset はそれぞれ1。二回分の表の到達先は 、累積 offset は2であり、 内では が第3〜4文字に当たる。第3文字を照会すると、二回分をまとめて の第1文字へ移れる。
一回の heavy 走査の後、light を一辺だけ進む
クエリ では、表を作ってから で照会を始める。段 を大きい順に一度ずつ調べ、存在する表の区間に位置が入る場合だけ移動する。途中で基底0・1に着いたら直ちに答えを返す。
heavy の経路に沿って、照会位置を含む区間は途中まで連続する。一度その区間から外れると、さらに先の heavy 先にも同じ位置は含まれない。そのため、大きい段から調べる走査で可能な heavy 移動をすべて済ませられる。走査後も基底でなければ、次の heavy 一辺は選べず、位置は light 側にある。light 先へ、その辺の offset を引いて一回移り、再び大きい段から走査する。
先ほどの の第3文字なら、二回分を飛んで の第1文字に着く。 は左右同長なので左が heavy で、その先は基底0となる。 の第2文字なら、二回分の区間には入らないが、一回分では の第1文字へ移れる。そこでは heavy の に入らないので、light の基底1へ移って終了する。
典型の発動条件
heavy-light decompositionの考え方
発動条件: 分岐を辿る照会で、一方の辺を選ぶ回数に対数上界を付けられ、残る長い連続移動をまとめたいとき。
含まれる量が小さい側を light とする。ただし、切り詰めや共有がある構造では、その量と参照先全体の大きさが一致するかを確かめる。本問では照会位置の単調性も使って回数を抑える。
binary lifting
発動条件: 各状態の次の移動先が一意で、移動中の値も合成できるとき。本問の heavy 先は頂点だけで決まり、累積 offset は加算で合成できる。
移動可能かの条件が経路上で途中まで成立するなら、大きい段から表を試して、条件を満たす最遠の到達先を探せる。
saturating length
発動条件: 暗黙文字列の先頭からの照会位置に上限があり、それより後ろの情報が、後続操作でも回答に影響しないとき。
連結では先頭の長さだけを上限で飽和できる。反転や末尾からの照会など、捨てた部分を再び参照する操作へは、そのまま適用できない。
問題固有の要素
本問では文字列の先頭だけを残すため、左の参照先は全部含まれ、右の参照先は途中で切れる。通常の木のサイズによる半減の議論をそのまま使うと、この非対称性を落としてしまう。
そこで状態を「頂点と照会位置」の対で見る。飽和したまま light を辿っても、照会位置が前半へ移ることで、次の light 移動から長さの半減へ接続できる。値を上限で丸めた後の償却解析では、丸めた値だけで減少を示せるかを確かめ、足りなければ操作が参照する位置も追う。
正当性
切り詰めと一辺の移動は照会文字を保つ
連結元の先頭 文字より後ろは、連結結果でも第 文字以降にしか現れない。したがって各連結の直後に切り詰めても、照会可能な先頭部分は元の問題と一致する。
状態 では常に を保つ。左右の含有区間は親の第1文字から第 文字までを重複なく覆うので、位置を含む側へ開始 offset を引いて移れば、同じ文字を指し続ける。右の含有長が0なら、その側は選ばれない。
飽和した長さには照会位置を組み合わせる
一辺を移動する前後を とする。開始 offset は非負なので 。保存長も、未飽和の親では左右の和、飽和した親では上限 以下なので、どちらの辺でも増えない。
light 移動について、次の三つを示す。
- 親が未飽和の場合。 なら両方の参照先が全部含まれる。light 先の保存長は小さい方の含有長そのものなので、 となる。
- 飽和した親から、飽和した light 先へ移る場合。 左の参照先の保存長が なら、含有長は左が 、右が0となり、左は heavy である。従って飽和した light 先は右に限られる。左の含有長を 、右を とすると、右が light なので 。移動後の位置は となる。保存長は減らなくても、照会位置は前半へ移る。
- 親が飽和し、位置が既に の場合。 右が light なら左の含有長は であり、右へ行くには が必要なので選べない。light へ行くなら左で、その保存長は含有長 に等しい。従って となる。
これで light 回数を数えられる。最初から未飽和なら、light のたびに保存長が半減する。飽和した状態での最初の light 移動で未飽和になった場合も、その一回を除けば同じである。
最初の light 移動後も飽和していた場合は、2より照会位置が 以下になる。その後 heavy を何回進んでも位置は増えない。次の light 移動時に親がまだ飽和していれば3、既に未飽和なら1を使い、二回目の light 移動後には保存長が 以下になる。以降は通常の半減が続く。
従って では、前者は 回以下、後者も 回以下である。途中で基底へ着けば、さらに少なくなる。
ダブリングは一辺ずつ辿る操作をまとめている
表の漸化式は、前半の到達先から後半を辿り、二つの開始 offset を足している。したがって と は、heavy を一辺ずつ 回辿った結果を表す。
各参照先の先頭部分が、移動元の連続区間として含まれる。さらに先へ辿ってもその区間から外へは出ず、末尾での切り詰めは区間の右端を短くするだけである。到達先 、累積 offset に対し、出発点内で実際に残る区間は 。現在位置は既に を満たすので、本文の が、一辺ずつ同じ heavy 経路を選べる条件になる。
経路を深く進むほど区間は狭くなるので、この条件の成立は途中まで連続する。大きい段からの走査はその最長の連続部分を選び終え、基底でなければ次に選ぶべき一辺は light となる。どの移動も照会文字を保ち、頂点番号は狭義に減るため、最終的に基底0または1へ停止し、正しい文字を返す。
実装上の注意
- 位置 は1始まり、offset は0始まりで統一する。移動判定は 。0始まりの位置へ直す実装なら、全体を にそろえる。
- 長さの加算は とする。offset も で飽和させてよい。真の累積 offset が 以上なら、先頭の1文字目でも出発点の第 文字以降になる。保存値が なら条件 を満たさず、上限超の移動が合法になることはない。offset は非負なので、合成後にこの判定が逆転することもない。
- 飽和した二値の和も最大 。区間の右端 も含めて64 bit符号付き整数に収まる。整数を正確に表せない型で を扱わない。
- 表には の段があればよい。基底には出辺を作らず、存在しない欄を合成しない。照会中に基底へ着いたら、その場で終了する。
- 左右が同じ参照先でも、親内の出現位置は別である。左の offset は0、右は左の保存長を使う。同長のときの heavy 選択を前処理と照会で統一し、右の含有長0も扱う。
復習の核
- 巨大な連結文字列では、まず文字の内容と構成を分け、指定位置を連結元へ戻すことを考える。そのままでは深さが時間になる点まで確認する。
- 切り詰めた親に含まれる量と、参照先全体の大きさを混同しない。丸めた長さが減らない遷移では、照会位置など別の単調な量を探す。
- 長い一意な移動は到達先と累積 offset の対でまとめる。位置条件で最長の移動を探すには、条件が経路の途中まで連続して成立することを証明する。
計算量と制約
時間
各頂点の長さ・左右の含有長・heavy/light の決定は 。ダブリング表は頂点ごとに 段なので、前処理の合計は 時間となる。入力を読みながら、その頂点の表を構築できる。
一照会では light 移動が 回で、その前後に行う heavy 走査一回が 時間。従って一照会は 、全 件と表の構築を合わせて 時間である。 では一段だけ持ち、定数時間で処理する。
空間
頂点に左右の参照先・保存長・heavy/light を持ち、各頂点の各段に到達先と累積 offset を保存するので、。照会は反復で処理でき、表以外の作業領域は でよい。
制約との対応
2026-10-29に公式問題文・個別公式解説を再照合した。、、 で、照会位置は生成文字列の長さ以下と保証される。時間制限は6秒、メモリ制限は1024 MiBである。
とすれば light は高々60回、ダブリング表は の19段で足りる。各欄には文字列本体ではなく、頂点番号と64 bitの offset を保存する。
出典