ABC 359 E — Water Tank

考察

水を注ぐ回数が非常に多くなっても、初めて次の容器へ届く直前の形が分かれば、それまでに注いだ量を一度に求められる。この形を右から復元すると、板の高さの接尾辞最大値になる。さらに、右端を一つ伸ばしたときに同じ高さになる区間をまとめれば、すべての容器への到達時刻を線形時間で計算できる。

一杯の水が止まる位置を考える

容器の水量を左から A0,A1,…,ANA_0,A_1,\ldots,A_N とし、容器 i−1i-1 と容器 ii の間の板の高さを HiH_i とする。問題文の操作では、まず A0A_0 を1増やし、板を左から順に調べる。板 ii の左側の水量が、板の高さと右側の水量の両方を超えていれば、右へ1だけ移す。

例えば H=(2,1)H=(2,1) のとき、各操作が終わった時点の水量は次のようになる。

操作回数A0A_0A1A_1A2A_2
0000
1100
2200
3210
4211

3回目には追加した一杯が最初の板を越え、4回目には二つの板を続けて越える。操作が終わった時点だけを見ると、毎回どれか一つの容器の水量だけが1増えている。この性質を一般の高さでも説明したい。

そこで、板を越える条件を満たしていないことを、不等式で表す。初期状態と各操作後には、すべての板について次の不変条件が成り立つ。

Ai−1≤max⁡(Hi,Ai)(1≤i≤N).A_{i-1}\leq\max(H_i,A_i)\qquad(1\leq i\leq N).

この状態へ一杯を追加したとする。ある板で等号が成り立っていれば、左側に届いた一杯によって左側の水量が右辺を1だけ超えるので、その一杯は右へ進み、左側の水量は元に戻る。一方、不等号が厳密なら、整数なので1増えても右辺以下に収まり、その容器に一杯が残る。そこより右は変化せず、もともと板を越える条件を満たしていないので、以後の移動も起きない。

つまり、一杯の追加は「等号の板を左から通過し、最初に Ai−1<max⁡(Hi,Ai)A_{i-1}<\max(H_i,A_i) となる板の左側で止まる」と言い換えられる。すべての板で等号なら、最後の容器 ANA_N まで届く。

初到達の直前を右から復元する

1≤n≤N1\leq n\leq N とし、容器 nn に初めて水が届く操作の直前に注目する。空の容器に届いた一杯は、次の板の高さが1以上なので、その先へは進まない。水は左からしか来ないため、この時点では An,…,ANA_n,\ldots,A_N はすべて0である。次の一杯が容器 nn まで進むには、手前の板すべてで等号が必要になる。

Ai−1=max⁡(Hi,Ai)(1≤i≤n).A_{i-1}=\max(H_i,A_i)\qquad(1\leq i\leq n).

An=0A_n=0 と Hn≥1H_n\geq1 から An−1=HnA_{n-1}=H_n。さらに左へ戻ると An−2=max⁡(Hn−1,Hn)A_{n-2}=\max(H_{n-1},H_n) となる。同じ復元を続ければ、

Ai=max⁡(Hi+1,…,Hn)(0≤i<n)A_i=\max(H_{i+1},\ldots,H_n)\qquad(0\leq i<n)

を得る。すなわち、各容器には、そこから板 nn までの最大の高さに等しい水量がたまっている。

容器間の移動では総水量は変わらず、一回の操作につき追加する量だけ1増える。容器 nn への初到達回数を TnT_n とすると、直前の総水量に次の一杯を足せばよい。ここで j=i+1j=i+1 と添字を付け替えると、

Tn=1+∑i=0n−1Ai=1+∑j=1nmax⁡(Hj,…,Hn).\begin{aligned} T_n&=1+\sum_{i=0}^{n-1}A_i\\ &=1+\sum_{j=1}^{n}\max(H_j,\ldots,H_n). \end{aligned}

先ほどの H=(2,1)H=(2,1) では、容器2への初到達直前は (A0,A1,A2)=(2,1,0)(A_0,A_1,A_2)=(2,1,0) である。総水量は3なので T2=1+2+1=4T_2=1+2+1=4 となり、表とも一致する。

接尾辞最大値の区間をまとめて更新する

長さ nn の接頭辞に対し、Sj(n)=max⁡(Hj,…,Hn)S_j^{(n)}=\max(H_j,\ldots,H_n) と定義する。これが接尾辞(suffix)最大値であり、必要なのは j=1,…,nj=1,\ldots,n に対する値の和である。各 nn について右から計算し直すと、調べる要素数の合計が 1+2+⋯+N1+2+\cdots+N となり、O(N2)O(N^2) 時間かかる。

そこで、右端へ高さ h=Hnh=H_n を追加したときの変化を調べる。以前の各値は max⁡(Sj(n−1),h)\max(S_j^{(n-1)},h) になり、新しい位置の値は Sn(n)=hS_n^{(n)}=h となる。一方、jj を右へ進めるほど最大値を取る範囲が狭くなるので、Sj(n−1)S_j^{(n-1)} は左から非増加に並ぶ。従って、hh 以下の値は末尾の連続した区間にあり、その全体が hh へ置き換わる。

この性質から、同じ値が続く区間を一つの組 (v,c)(v,c) にまとめ、単調スタックで管理する。vv は接尾辞最大値、cc はその値を取る位置の個数である。スタックの底から頂上へ添字の左から右に対応させ、高さは厳密に減少させる。値の総和を変数 sum に持つ。最初にスタックを空、sum を0にしてから、次の手順を n=1,…,Nn=1,\ldots,N の順に行う。

  1. 新しい高さ h=Hnh=H_n を処理するとき、併合後の個数 cc を、新しい位置の分の1で初期化する。
  2. 頂上の高さ vv が v≤hv\leq h である間、その組 (v,d)(v,d) を取り出す。sum から v×dv\times d を引き、cc に dd を加える。
  3. (h,c)(h,c) を積み、sum に h×ch\times c を加える。この時点の sum が接尾辞最大値の和なので、sum + 1 を TnT_n として出力する。

例えば H=(2,1)H=(2,1) まで読んだスタックは、底から (2,1),(1,1)(2,1),(1,1) である。右へ高さ3を追加すると両方の組が取り出され、新しい位置も含めた (3,3)(3,3) になる。元の高さ2や1は、今後右にどんな高さを追加しても最大値の候補へ戻らない。ただし、それぞれの区間の個数は総和に必要なので、新しい組へ引き継ぐ。

典型の発動条件

単調stackによる区間併合

発動条件: 右端への追加によって、単調に並ぶ値の末尾側だけが同じ値へ置き換わるとき。等しい値の連続区間を高さと個数で持てば、変更箇所を頂上から取り出せる。本問では同じ高さも v≤hv\leq h で併合し、高さが厳密に減る区間列にする。

集約値の差分維持

発動条件: 圧縮した区間を更新しながら、元の列全体の和も必要なとき。削除した区間の「高さ×個数」を総和から引き、新しい区間の寄与を加える。区間の高さが不要になっても、その個数まで捨てないことが要点である。

問題固有の要素

左から順に一杯ずつ移す操作を、完了後の水量の上限と結び付けることが本問の要点である。「初めて水が届く」という瞬間には手前の板がすべて等号でつながるため、時間を追う代わりに、直前の形を右から復元できる。

別の問題へ持ち帰る視点: 反復操作の初到達時刻を求めるときは、毎回増える総量と、到達直前に満たす境界条件を探す。時刻そのもののシミュレーションを省ける可能性がある。

正当性

初期状態では全水量が0なので、すべての板について Ai−1≤max⁡(Hi,Ai)A_{i-1}\leq\max(H_i,A_i) が成り立つ。この条件を満たす状態から一回操作すると、考察で示した通り、等号の板では追加された一杯だけが右へ渡り、最初の厳密な不等号の手前、または最後の容器に一杯が残る。

一杯が残る容器を kk とすると、操作前後で変わるのは AkA_k の1増加だけである。k>0k>0 なら板 kk の不等式は右辺が増える側なので保たれる。k<Nk<N なら板 k+1k+1 には操作前に厳密な不等号があり、整数の左辺を1増やしても上限を超えない。他の板の両辺は変わらない。よって不変条件は何回操作しても保たれる。

容器 nn への初到達直前には An,…,AN=0A_n,\ldots,A_N=0 である。次の一杯は板1から板 nn までを通るので、そこではすべて等号が成立する。従って右から復元した Ai=max⁡(Hi+1,…,Hn)A_i=\max(H_{i+1},\ldots,H_n) が実際の直前の水量であり、総水量に1を足した Tn=1+∑j=1nSj(n)T_n=1+\sum_{j=1}^n S_j^{(n)} が求める回数である。

スタックが S(n−1)S^{(n-1)} の同値区間とその総和を正しく表すとする。右端へ h=Hnh=H_n を加えると、末尾にある高さ hh 以下の区間だけが hh に変わる。手順はこの区間をちょうど取り出し、新位置を含む個数で一つにまとめ、元の寄与を引いて新しい寄与を足す。残る頂上の高さは hh より大きいため、区間の表現・高さの厳密な減少・総和のすべてを保つ。空のスタックから始めて各接頭辞でこの更新を行うので、毎回出力する sum + 1 は TnT_n に一致する。

実装上の注意

  • 同じ高さも v≤hv\leq h で取り出し、一つの区間にする。条件を v<hv<h にすると高さの厳密な減少という不変条件が崩れる。
  • N=1N=1 でも同じ手順で (H1,1)(H_1,1) を積み、H1+1H_1+1 を出力する。高さが増える列では複数区間を併合し、減る列では取り出さず積む。同高の列も含め、特別な分岐は要らない。
  • 総和には到達直前の水量だけを持つ。出力時に1を足し、その1を次の更新へ混ぜない。
  • 高さと個数の積、および総和には64 bit整数を使う。積を求める時点から64 bitで計算し、32 bitで乗算してから変換しない。

復習の核

  • 到達時刻が大きいときは、まず「直前にどこまで満たされているか」を探す。一杯が等号の板を通過することから、接尾辞最大値の形を復元できる。
  • 接尾辞最大値の列は左から非増加である。右端への追加で変わるのが末尾だけなら、同値区間をスタックにまとめ、各区間を一度だけ消せる。
  • 候補の値を捨てられても、和を求めるにはその値が代表していた個数を引き継ぐ。

計算量と制約

時間

O(N)O(N)。各高さにつき一組を積み、その組は高々一度だけ取り出される。内側の繰り返しの総回数は NN 以下であり、入力と各到達回数の出力を含めて線形時間となる。

空間

O(N)O(N)。高さが厳密に減る入力ではスタックに最大 NN 組が残る。入力や答えを配列へ保存する場合も、全体で O(N)O(N) に収まる。

制約との対応

公式制約は 1≤N≤2×1051\leq N\leq2\times10^5、1≤Hi≤1091\leq H_i\leq10^9 である。各容器の到達時刻は最大で N×109+1≤2×1014+1N\times10^9+1\leq2\times10^{14}+1 なので、一回ずつ操作を再現する方針は使えない。高さの大きさによらない O(N)O(N) の手順と64 bit整数なら処理できる。時間制限は2秒、メモリ制限は1024 MiBである。

出典

公式問題文・個別公式解説は2026-10-23に再照合した。以下の確認日時は、保存済み出典の取得時点を保持している。

分類・前提・執筆情報

掲載状態: 収録済み

Water Tank の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 支配関係から不要な候補を単調stack・queueで削る

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

      主タグ: 単調stack・queueによる支配候補の削除

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

      学習の位置

      体系上の位置: 支配関係から不要な候補を単調stack・queueで削る

      • 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。

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

      • 全候補から極値を反復取得するheap・ordered set。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題