ABC 438 E — Heavy Buckets

考察

バケツを一つに絞ると、次の持ち主と一回の注水量は、現在の持ち主だけで決まる。同じ持ち主から始めたときの「一定回数後の持ち主」と「その間に増える水量」を対にしておけば、長い操作列をまとめて進められる。

まず、問題の一回の操作を正確に読む。人 ii が持っている各バケツに水を ii だけ入れ、その後で人 AiA_i へ渡す。注水するのは出発時の人である。また、全員の操作は同時なので、受け取った人が同じ回のうちにさらに注水・受け渡しすることはない。

複数のバケツが同じ人の手元へ集まっても、それぞれのバケツに同じ量が追加されるだけで、水を混ぜたりバケツを一つにまとめたりはしない。したがって、他のバケツの位置や水量を状態に含めず、質問されたバケツだけを追えばよい。

例えば、独自の小例 A=(2,3,2)A=(2,3,2) で、はじめ人1が持つ空のバケツ1を追う。各回の注水と、操作後の持ち主・水量は次のようになる。

回数注水持ち主累計
0まだ注がない10
1人1が1を注ぐ21
2人2が2を注ぐ33
3人3が3を注ぐ26

持ち主は 1→2→3→21\to2\to3\to2 と移り、水量は 0→1→3→60\to1\to3\to6 と増える。最初の二回で注ぐのは人1と人2であり、到着先の人2と人3ではない。この一回分のずれを、前計算の初期値にも反映する必要がある。

一つのバケツだけを追っても、質問ごとに逐一操作すると最大 10910^9 回かかる。そこで、一回分の結果を二つつなげて二回分、二回分を二つつなげて四回分、というように区間を倍にする。人を頂点、i→Aii\to A_i を辺と見ると、各頂点の行き先が一意な関数グラフになっており、同じ持ち主から始める区間の結果を何度でも使える。

人の番号を 1≤i≤N1\leq i\leq N、段数を 0≤d<300\leq d<30 とし、次の二つを保存する。

  • P[d][i]P[d][i]:人 ii がバケツを持つ状態から、2d2^d 回操作した後の持ち主。
  • Q[d][i]Q[d][i]:同じ 2d2^d 回の操作で、そのバケツに新たに入る水量。操作前から入っている水は含めない。

一回分では、人 ii が ii だけ注いで AiA_i へ渡すので、初期値は

P[0][i]=Ai,Q[0][i]=iP[0][i]=A_i,\qquad Q[0][i]=i

となる。先ほどの例なら、P[1][1]=3P[1][1]=3、Q[1][1]=1+2=3Q[1][1]=1+2=3 である。2+32+3 とすると、最初の人1の注水を落とし、二回の操作後に持つ人3の注水を先取りしてしまう。

d≥1d\geq1 の表を作るには、前半の 2d−12^{d-1} 回後の持ち主を j=P[d−1][i]j=P[d-1][i] と置く。後半は人 jj から同じ回数進むので、

P[d][i]=P[d−1][j],Q[d][i]=Q[d−1][i]+Q[d−1][j]\begin{aligned} P[d][i]&=P[d-1][j],\\ Q[d][i]&=Q[d-1][i]+Q[d-1][j] \end{aligned}

である。前半の終点を後半の出発点にし、二つの区間の追加水量を足す。d=1,2,…,29d=1,2,\ldots,29 の順に、全員について計算すればよい。

質問を「TT 回後のバケツ BB の水量」と書く。バケツ BB は最初に人 BB が持ち、水量は0なので、current=B、water=0 から始める。TT を二進数で表し、d=0,1,…,29d=0,1,\ldots,29 の順に、2d2^d の位が1なら次の更新を行う。

water += Q[d][current]
current = P[d][current]

これは擬似コードである。両方の表を更新前の current で引くため、水量を先に足し、その後で持ち主を変える。例えば T=3=1+2T=3=1+2、B=1B=1 なら、一回分で水量1・持ち主2となり、そこから二回分の Q[1][2]=2+3Q[1][2]=2+3 を足して水量6を得る。最後の water をその質問の答えとして出力し、次の質問も操作前の状態から独立に計算する。

典型の発動条件

重み付きダブリング

一意に決まる遷移を大量に繰り返し、到達先に加えて途中の加法的なコストも求めるときに使う。到達先と区間の集約値を対にして保存し、前半の到達先から後半をつなぐ。

functional graph

各頂点の出次数が1で、同じ遷移を反復するときに現れる構造である。本問では人を頂点、バケツの受け渡しを有向辺とする。行き先が一意なら、途中で経路が合流したりサイクルに入ったりしても、ダブリングの合成式をそのまま使える。

問題固有の要素

全バケツの同時操作を、一つのバケツの独立した移動へ読み替える点が出発点になる。「持っているバケツすべてにそれぞれ注ぐ」という条件により、他のバケツが何個集まっても、そのバケツの次の持ち主と追加水量には影響しない。

別の問題へ持ち帰る視点として、反復操作で必要な情報が到達先と加法的な集約値なら、両方を同じダブリングで合成できる。さらに、区間の値が結合的に合成できるモノイド値なら、和以外の経路集約にも拡張できる。その場合も、前半から後半へという合成順を保つ。

正当性

一回の操作では出発時の人が注水してから渡すため、P[0][i]=AiP[0][i]=A_i、Q[0][i]=iQ[0][i]=i が正しい。2d2^d 回の遷移は二つの 2d−12^{d-1} 回の区間に分けられ、後半は前半の到達先から始まる。したがって、遷移先と追加水量の合成式は各段で正しい。

質問処理では、適用済みの回数を ss とすると、current はバケツ BB の ss 回後の持ち主、water はその時点の水量を表す。初期値 current=B、water=0 は s=0s=0 に一致し、更新前の持ち主から区間の水量を加えて到達先へ移ると、この対応が保たれる。立っている bit の区間を順につなぐと、重複も抜けもなく合計 TT 回を進むので、最後の water が答えになる。持ち主が途中で合流しても、各バケツへの注水は独立しているため、この議論は変わらない。

実装上の注意

  • 水量を足す表と到達先の表は、どちらも更新前の持ち主で引く。先に current を変えてから水量を足すと、別の出発点の区間を集計してしまう。
  • 自己ループ Ai=iA_i=i でも同じ初期値と合成式を使える。その人から動かず、毎回 ii だけ増えるので、初期所有者 ii のバケツの水量は iTiT になる。
  • 最大回数は 109<23010^9<2^{30} なので、段は 0,…,290,\ldots,29 の30段が必要十分である。T=1T=1 では初期表だけ、T=2kT=2^k では kk 段目だけを使う。bit番号と操作回数を混同しない。
  • 一回の注水は高々 NN なので、水量は NT≤2×1014NT\leq2\times10^{14} 以下。水量の表と累計には C++ の long long など64bit整数を使う。

復習の核

  • 重み付き遷移では、出発時と到着時のどちらの値を加えるかを一回の操作から決める。表の初期値と質問の更新順を同じ定義にそろえる。
  • 後半の集約値は、元の出発点ではなく前半の到達先から引く。
  • 多数の物体が同時に動く問題では、一つの物体の挙動が他の物体に依存するかを確かめる。独立なら、全体の配置を状態に持たずに済む。

計算量と制約

時間

人数を NN、質問数を QQ、質問の最大操作回数を Tmax⁡T_{\max} とする。表の構築は O(Nlog⁡(Tmax⁡+1))O(N\log(T_{\max}+1))、各質問は O(log⁡(Tmax⁡+1))O(\log(T_{\max}+1))。全体で O((N+Q)log⁡(Tmax⁡+1))O((N+Q)\log(T_{\max}+1)) となる。本問では30段の前計算と、各質問につき30個の bit の確認で済む。

空間

到達先と追加水量の表に O(Nlog⁡(Tmax⁡+1))O(N\log(T_{\max}+1)) を使う。質問を一つずつ読み、答えを順に出力すれば、質問数に比例する配列は不要である。

制約との対応

公式制約は 2≤N≤2×1052\leq N\leq2\times10^5、1≤Q≤2×1051\leq Q\leq2\times10^5、1≤Ai,Bi≤N1\leq A_i,B_i\leq N、1≤Ti≤1091\leq T_i\leq10^9。入力はすべて整数で、時間制限は3秒、メモリ制限は1024 MiBである。各表は高々 30N≤6×10630N\leq6\times10^6 要素で、到達先を32bit、水量を64bitの整数配列で持てば、二表のデータ部分は合わせて約72 MBとなる。

出典

2026-10-27に公式問題文・個別公式解説を再照合し、出発時の注水、一回分の初期値、区間の合成、制約との対応を確認した。

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: doubling・binary lifting

主題
  • doubling・binary lifting: 一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: doubling・binary lifting

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

      学習の位置

      体系上の位置: doubling・binary lifting

      • 一意な遷移の2の冪回先を前計算し、巨大回数後の状態または区間到達を求められる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題