考察
バケツを一つに絞ると、次の持ち主と一回の注水量は、現在の持ち主だけで決まる。同じ持ち主から始めたときの「一定回数後の持ち主」と「その間に増える水量」を対にしておけば、長い操作列をまとめて進められる。
まず、問題の一回の操作を正確に読む。人 が持っている各バケツに水を だけ入れ、その後で人 へ渡す。注水するのは出発時の人である。また、全員の操作は同時なので、受け取った人が同じ回のうちにさらに注水・受け渡しすることはない。
複数のバケツが同じ人の手元へ集まっても、それぞれのバケツに同じ量が追加されるだけで、水を混ぜたりバケツを一つにまとめたりはしない。したがって、他のバケツの位置や水量を状態に含めず、質問されたバケツだけを追えばよい。
例えば、独自の小例 で、はじめ人1が持つ空のバケツ1を追う。各回の注水と、操作後の持ち主・水量は次のようになる。
持ち主は と移り、水量は と増える。最初の二回で注ぐのは人1と人2であり、到着先の人2と人3ではない。この一回分のずれを、前計算の初期値にも反映する必要がある。
一つのバケツだけを追っても、質問ごとに逐一操作すると最大 回かかる。そこで、一回分の結果を二つつなげて二回分、二回分を二つつなげて四回分、というように区間を倍にする。人を頂点、 を辺と見ると、各頂点の行き先が一意な関数グラフになっており、同じ持ち主から始める区間の結果を何度でも使える。
人の番号を 、段数を とし、次の二つを保存する。
- :人 がバケツを持つ状態から、 回操作した後の持ち主。
- :同じ 回の操作で、そのバケツに新たに入る水量。操作前から入っている水は含めない。
一回分では、人 が だけ注いで へ渡すので、初期値は
となる。先ほどの例なら、、 である。 とすると、最初の人1の注水を落とし、二回の操作後に持つ人3の注水を先取りしてしまう。
の表を作るには、前半の 回後の持ち主を と置く。後半は人 から同じ回数進むので、
である。前半の終点を後半の出発点にし、二つの区間の追加水量を足す。 の順に、全員について計算すればよい。
質問を「 回後のバケツ の水量」と書く。バケツ は最初に人 が持ち、水量は0なので、current=B、water=0 から始める。 を二進数で表し、 の順に、 の位が1なら次の更新を行う。
water += Q[d][current]
current = P[d][current]
これは擬似コードである。両方の表を更新前の current で引くため、水量を先に足し、その後で持ち主を変える。例えば 、 なら、一回分で水量1・持ち主2となり、そこから二回分の を足して水量6を得る。最後の water をその質問の答えとして出力し、次の質問も操作前の状態から独立に計算する。
典型の発動条件
重み付きダブリング
一意に決まる遷移を大量に繰り返し、到達先に加えて途中の加法的なコストも求めるときに使う。到達先と区間の集約値を対にして保存し、前半の到達先から後半をつなぐ。
functional graph
各頂点の出次数が1で、同じ遷移を反復するときに現れる構造である。本問では人を頂点、バケツの受け渡しを有向辺とする。行き先が一意なら、途中で経路が合流したりサイクルに入ったりしても、ダブリングの合成式をそのまま使える。
問題固有の要素
全バケツの同時操作を、一つのバケツの独立した移動へ読み替える点が出発点になる。「持っているバケツすべてにそれぞれ注ぐ」という条件により、他のバケツが何個集まっても、そのバケツの次の持ち主と追加水量には影響しない。
別の問題へ持ち帰る視点として、反復操作で必要な情報が到達先と加法的な集約値なら、両方を同じダブリングで合成できる。さらに、区間の値が結合的に合成できるモノイド値なら、和以外の経路集約にも拡張できる。その場合も、前半から後半へという合成順を保つ。
正当性
一回の操作では出発時の人が注水してから渡すため、、 が正しい。 回の遷移は二つの 回の区間に分けられ、後半は前半の到達先から始まる。したがって、遷移先と追加水量の合成式は各段で正しい。
質問処理では、適用済みの回数を とすると、current はバケツ の 回後の持ち主、water はその時点の水量を表す。初期値 current=B、water=0 は に一致し、更新前の持ち主から区間の水量を加えて到達先へ移ると、この対応が保たれる。立っている bit の区間を順につなぐと、重複も抜けもなく合計 回を進むので、最後の water が答えになる。持ち主が途中で合流しても、各バケツへの注水は独立しているため、この議論は変わらない。
実装上の注意
- 水量を足す表と到達先の表は、どちらも更新前の持ち主で引く。先に
current を変えてから水量を足すと、別の出発点の区間を集計してしまう。
- 自己ループ でも同じ初期値と合成式を使える。その人から動かず、毎回 だけ増えるので、初期所有者 のバケツの水量は になる。
- 最大回数は なので、段は の30段が必要十分である。 では初期表だけ、 では 段目だけを使う。bit番号と操作回数を混同しない。
- 一回の注水は高々 なので、水量は 以下。水量の表と累計には C++ の
long long など64bit整数を使う。
復習の核
- 重み付き遷移では、出発時と到着時のどちらの値を加えるかを一回の操作から決める。表の初期値と質問の更新順を同じ定義にそろえる。
- 後半の集約値は、元の出発点ではなく前半の到達先から引く。
- 多数の物体が同時に動く問題では、一つの物体の挙動が他の物体に依存するかを確かめる。独立なら、全体の配置を状態に持たずに済む。
計算量と制約
時間
人数を 、質問数を 、質問の最大操作回数を とする。表の構築は 、各質問は 。全体で となる。本問では30段の前計算と、各質問につき30個の bit の確認で済む。
空間
到達先と追加水量の表に を使う。質問を一つずつ読み、答えを順に出力すれば、質問数に比例する配列は不要である。
制約との対応
公式制約は 、、、。入力はすべて整数で、時間制限は3秒、メモリ制限は1024 MiBである。各表は高々 要素で、到達先を32bit、水量を64bitの整数配列で持てば、二表のデータ部分は合わせて約72 MBとなる。
出典
2026-10-27に公式問題文・個別公式解説を再照合し、出発時の注水、一回分の初期値、区間の合成、制約との対応を確認した。