ABC 371 F — Takahashi in Narrow Road

考察

指定された人の進路を空けるため、進行方向にいる人を必要な分だけ動かす。人と人の間に必要な間隔を座標から差し引くと、この押し出しを「単調列の連続区間を同じ値へそろえる操作」としてまとめられる。

人の番号を引き、必要な間隔を吸収する

人は一歩ずつ移動し、他の人がいる地点には入れないので、追い越しは起こらない。人の番号を 1 始まりとし、現在の座標を XiX_i と書く。初期位置だけでなく移動中も、整数座標に対して次が成り立つ。

Xi+1≥Xi+1X_{i+1}\geq X_i+1

指定された人を右へ動かして右隣の人とぶつかるなら、右隣は指定された人の目的位置より少なくとも一つ先へ進む必要がある。さらにその右隣も必要なら動かす。この「一つ先」という番号に応じたずれを消すため、変換後の値を Yi=Xi−iY_i=X_i-i と定める。すると制約は

Yi+1≥YiY_{i+1}\geq Y_i

という広義単調増加、すなわち等号を許す単調列になる。元の座標で間隔 1 で並ぶ人たちは、変換後には同じ値を持つ。また、人ごとに引く番号は変わらないので、YiY_i の増減量はその人の移動量と等しい。

一つの用事を「人 TT を元の座標 GG へ動かす」と書く。この用事の変換後の目標は

g=G−Tg=G-T

であり、比較するのは YTY_T と gg である。元の目標 GG と区別しておこう。

どちら側の、どこまでを動かすか

YT<gY_T<g なら右移動である。人 TT の値を gg にすると、単調性を保つには右側の人も gg 以上でなければならない。したがって、i≥Ti\geq T かつ Yi<gY_i<g の人をちょうど gg へ上げる。すでに Yi≥gY_i\geq g の人は動かす必要がない。単調列なので、変更する人は TT から始まる一つの連続区間になる。

例えば、元の座標が X=(1,2,4,7,8)X=(1,2,4,7,8) なら、Y=(0,0,1,3,3)Y=(0,0,1,3,3) である。人 T=2T=2 を G=5G=5 へ動かすと g=3g=3。変更するのは人 2・3 だけで、変換後は Y=(0,3,3,3,3)Y=(0,3,3,3,3)、元の座標では X=(1,5,6,7,8)X=(1,5,6,7,8) になる。移動量は 3+2=53+2=5。人 4・5 は最初から Yi=gY_i=g なので、そのままでよい。

YT>gY_T>g の左移動は逆で、i≤Ti\leq T かつ Yi>gY_i>g の人だけを gg へ下げる。同じ初期配置から人 T=4T=4 を G=4G=4 へ動かすなら g=0g=0 で、人 3・4 を動かす。結果は Y=(0,0,0,0,3)Y=(0,0,0,0,3)、X=(1,2,3,4,8)X=(1,2,3,4,8)、移動量は 1+3=41+3=4。人 1・2 は目標と等しく、変更しない。

YT=gY_T=g なら、その用事はすでに完了しており移動量は 0 である。このように、進行方向にあり、目標に届いていない値だけを目標へそろえる。この方針を用事ごとに繰り返してよい理由は、後の「正当性」で全用事を通して示す。

区間代入と、更新前の区間和を使う

一歩ずつの移動はもちろん、影響する人の列挙にも一回で Θ(N)\Theta(N) 人かかり得る。N,Q≤2×105N,Q\leq2\times10^5 なので、上で分かった区間を一括して処理したい。

遅延セグメント木に YY を載せ、各節点に区間長 len、和 sum、最小値 mn、最大値 mx を持たせる。結合では長さと和を足し、最小値・最大値をそれぞれ取る。値 gg を区間に代入すると、空でない節点の要約は次に変わる。

(len,sum,mn,mx)⟼(len,g len,g,g)(\mathrm{len},\mathrm{sum},\mathrm{mn},\mathrm{mx}) \longmapsto (\mathrm{len},g\,\mathrm{len},g,g)

代入を重ねたら後の代入を残す。これにより、子を一つずつ更新せず、要約と遅延作用だけで区間代入を処理できる。

木の添字だけを 0 始まりにして、人 ii の値を葉 i−1i-1 に置く。用事ごとに t=T−1t=T-1、g=G−Tg=G-T を求め、現在の YTY_T を取得する。区間はすべて半開区間として、次のように処理する。

  • 右移動: max_right(t, 判定) で、最大値が gg 未満の間だけ右へ広げる。返った端を RR とすれば更新区間は [t,R)[t,R)。更新前の区間和を ss、長さを k=R−tk=R-t として、gk−sgk-s を答えに加えてから、この区間を gg に代入する。
  • 左移動: min_left(t+1, 判定) で、最小値が gg より大きい間だけ左へ広げる。返った端を LL とすれば更新区間は [L,t+1)[L,t+1)。更新前の和を ss、長さを k=t+1−Lk=t+1-L として、s−gks-gk を答えに加えてから、この区間を gg に代入する。
  • 同値: YT=gY_T=g なら加算も更新も行わない。

右では全員が同じ方向へ g−Yig-Y_i だけ動くので、その和は gk−sgk-s。左では Yi−gY_i-g の和になり、符号が逆になる。答えを 0 で初期化し、入力順にすべての用事を処理した後、その累積値を出力する。

木上探索は、要約の判定が真である節点全体を読み飛ばし、境界を含む節点へだけ降りる。区間を伸ばすほど最大値は下がらず、最小値は上がらないので、一度偽になった判定は真へ戻らない。区間和の取得・代入と同じく、境界も O(log⁡N)O(\log N) で求められる。

典型の発動条件

制約を吸収する座標変換

順序を保つ整数の点列で、隣接差が少なくとも一定値必要なときに考える。今回のように必要な間隔が 1 なら番号を引くことで、衝突しない条件を単調性へ置き換えられる。変換後の目標も同じ規則で作る。

単調列の区間代入

単調列の片側をしきい値まで押し上げる・押し下げるとき、変わる範囲は連続する。その境界を最小値・最大値で探し、費用を区間和から計算できるなら、区間代入を持つ遅延セグメント木が候補になる。区間和を代入後にも更新するため、要約には区間長も必要である。

問題固有の要素

一歩の移動で追い越せないことと、同じ地点に立てないことを合わせると、人の番号に応じた最低限の間隔が見える。そこを差し引けば、元の座標では一列に詰まる人たちが、変換後には同じ値の区間になる。人ごとの移動の連鎖を、更新後に満たすべき単調性から捉え直すのが着眼点である。

正当性

座標変換と区間代入・区間和による処理は個別公式解説に沿う。以下では、その操作が実現できることと、先の用事のために余分な移動をしておく必要がないことを補って示す。

一つの用事で必要な移動量の下界を達成する

用事の直前の変換列を yy、上の手順で更新した列を pp とする。右移動では、用事完了時に人 TT の値が gg になるため、右側の値はすべて gg 以上でなければならない。したがって、i≥Ti\geq T かつ yi<gy_i<g の人は、少なくとも g−yig-y_i 回動く必要がある。手順はその人たちだけをちょうど下界の分だけ動かす。実際に動かすときは、対象区間の右端の人から順に目的位置へ進めれば、次の人の進路を空けられる。

左移動でも、i≤Ti\leq T かつ yi>gy_i>g の人に yi−gy_i-g 回以上の移動が必要であり、対象区間の左端から順に動かせば下界を達成する。境界の外の値との大小関係も保たれるので、pp は有効な単調列になる。等しい値の人の下界は 0 で、動かさなくてよい。

先行する余分な移動を遅らせても損をしない

その用事だけで最小でも、後の用事で不利になる可能性は別に調べる必要がある。そこで、任意の別の計画が、この用事を終えた時点での変換列を zz とする。zz は単調で zT=gz_T=g を満たすが、他の人を先の用事のために余分に動かしていてもよい。

右移動で手順が変更した人は、yi≤pi=g≤ziy_i\leq p_i=g\leq z_i を満たす。左移動で変更した人は、zi≤pi=g≤yiz_i\leq p_i=g\leq y_i を満たす。変更しなかった人は pi=yip_i=y_i である。従ってどの人も、pip_i が yiy_i と ziz_i の間にあり、

∑i=1N∣yi−zi∣=∑i=1N∣yi−pi∣+∑i=1N∣pi−zi∣\begin{aligned} \sum_{i=1}^{N}|y_i-z_i|&=\sum_{i=1}^{N}|y_i-p_i|\\ &\quad+\sum_{i=1}^{N}|p_i-z_i| \end{aligned}

が成り立つ。左辺は、別の計画がこの用事を終えるまでに払う移動量の下界である。

一方、右辺の最初の和で手順どおり pp へ移り、残りの和で pp から zz へ移れる。後半は、減らす値を左の人から、増やす値を右の人から順に動かせばよい。始点・終点が単調なので衝突せず、各人を寄り道なしで目的位置へ運べる。人 TT は pT=zT=gp_T=z_T=g のままで、この用事を完了した状態も保てる。

こうすれば、余分な移動を先行させた別の計画を、「まず必要な押し出しだけで用事を終え、必要ならその後で zz へ追いつき、以後は別の計画を続ける」という計画へ、総費用を増やさず置き換えられる。残りの用事についても同じ議論を繰り返せるため、各用事で必要な押し出しだけを行う方針が、全用事を通した最小総移動量を与える。

実装上の注意

  • g=G−Tg=G-T には 1 始まりの人番号を使う。木用に t=T−1t=T-1 を作っても、式をうっかり G−tG-t に変えない。葉に置く初期値も Xi−iX_i-i でそろえる。
  • 右の判定は len == 0 || mx < g、左は len == 0 || mn > g。空区間には必ず真を返す。単位元の和・長さは 0、最小値・最大値はそれぞれ正・負の無限大相当とし、空区間への作用は空のままにする。
  • 右端まで影響する場合の R=NR=N、左端まで影響する場合の L=0L=0 も、同じ半開区間で扱える。探索・和の取得・代入で同じ区間を使い、費用は必ず代入前の和から求める。
  • 変換後の値は負にもなる。遅延作用の「代入なし」は、特定の座標値で兼用せず、フラグなどで区別する。区間和・長さとの積・累積移動量は符号付き 64 bit 整数で扱い、乗算前に型を広げる。

復習の核

  • 「隣との差が少なくとも 1」なら、番号を引いて単調性へ変える。目標も同じ座標系へ直す。
  • 右では目標未満の値、左では目標を超える値だけが動く。目標と等しい値が、動かす必要のない境界になる。
  • 各回の最小費用だけで全体の貪欲法を正当化しない。任意の完了状態へ、まず貪欲な状態を経由しても移動量を増やさず到達できることを確かめる。

計算量と制約

時間

O(N+Qlog⁡N)O(N+Q\log N)。初期配列からの木の構築は O(N)O(N)、一つの用事では一点取得・木上の境界探索・区間和の取得・区間代入を定数回ずつ行い、それぞれ O(log⁡N)O(\log N) かかる。

境界の候補を外側で二分探索し、各判定で木から一点の値や区間の最大値・最小値を取得する実装では、一つの判定に O(log⁡N)O(\log N) かかる。その場合の全体は O(N+Qlog⁡2N)O(N+Q\log^2 N)。max_right / min_left による木上探索と区別する。

空間

O(N)O(N)。各節点の要約と遅延代入を定数サイズで持つ。用事は一つずつ処理できる。

制約との対応

1≤N,Q≤2×1051\leq N,Q\leq2\times10^5、初期座標は 0≤X1<X2<⋯<XN≤1080\leq X_1<X_2<\dotsb<X_N\leq10^8、各用事は 1≤T≤N1\leq T\leq N、0≤G≤1080\leq G\leq10^8。すべて整数であり、時間制限は 3 秒、メモリ制限は 1024 MiB である。人の移動距離や更新区間の長さを列挙せず、用事ごとの定数回の木操作へまとめる。

移動中の元座標を初期座標・目標の範囲内に制限してはいけない。例えば人 NN を座標 0 へ動かすと、その左の人は負の座標へ動く場合がある。変換列と符号付き整数でそのまま扱える。N=1N=1 でも同じ手順になり、各用事の費用はその一人の現在位置と目標の差の絶対値となる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Takahashi in Narrow Road の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間更新を要約へ作用させる

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 遅延評価する区間作用

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

      学習の位置

      体系上の位置: 区間更新を要約へ作用させる

      • 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

      先に読む単元:

      • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

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

      • 過去の版の保存・rollback・構造共有。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題