ABC 359 E — Water Tank
考察
水を注ぐ回数が非常に多くなっても、初めて次の容器へ届く直前の形が分かれば、それまでに注いだ量を一度に求められる。この形を右から復元すると、板の高さの接尾辞最大値になる。さらに、右端を一つ伸ばしたときに同じ高さになる区間をまとめれば、すべての容器への到達時刻を線形時間で計算できる。
一杯の水が止まる位置を考える
容器の水量を左から とし、容器 と容器 の間の板の高さを とする。問題文の操作では、まず を1増やし、板を左から順に調べる。板 の左側の水量が、板の高さと右側の水量の両方を超えていれば、右へ1だけ移す。
例えば のとき、各操作が終わった時点の水量は次のようになる。
| 操作回数 | |||
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 2 | 2 | 0 | 0 |
| 3 | 2 | 1 | 0 |
| 4 | 2 | 1 | 1 |
3回目には追加した一杯が最初の板を越え、4回目には二つの板を続けて越える。操作が終わった時点だけを見ると、毎回どれか一つの容器の水量だけが1増えている。この性質を一般の高さでも説明したい。
そこで、板を越える条件を満たしていないことを、不等式で表す。初期状態と各操作後には、すべての板について次の不変条件が成り立つ。
この状態へ一杯を追加したとする。ある板で等号が成り立っていれば、左側に届いた一杯によって左側の水量が右辺を1だけ超えるので、その一杯は右へ進み、左側の水量は元に戻る。一方、不等号が厳密なら、整数なので1増えても右辺以下に収まり、その容器に一杯が残る。そこより右は変化せず、もともと板を越える条件を満たしていないので、以後の移動も起きない。
つまり、一杯の追加は「等号の板を左から通過し、最初に となる板の左側で止まる」と言い換えられる。すべての板で等号なら、最後の容器 まで届く。
初到達の直前を右から復元する
とし、容器 に初めて水が届く操作の直前に注目する。空の容器に届いた一杯は、次の板の高さが1以上なので、その先へは進まない。水は左からしか来ないため、この時点では はすべて0である。次の一杯が容器 まで進むには、手前の板すべてで等号が必要になる。
と から 。さらに左へ戻ると となる。同じ復元を続ければ、
を得る。すなわち、各容器には、そこから板 までの最大の高さに等しい水量がたまっている。
容器間の移動では総水量は変わらず、一回の操作につき追加する量だけ1増える。容器 への初到達回数を とすると、直前の総水量に次の一杯を足せばよい。ここで と添字を付け替えると、
先ほどの では、容器2への初到達直前は である。総水量は3なので となり、表とも一致する。
接尾辞最大値の区間をまとめて更新する
長さ の接頭辞に対し、 と定義する。これが接尾辞(suffix)最大値であり、必要なのは に対する値の和である。各 について右から計算し直すと、調べる要素数の合計が となり、 時間かかる。
そこで、右端へ高さ を追加したときの変化を調べる。以前の各値は になり、新しい位置の値は となる。一方、 を右へ進めるほど最大値を取る範囲が狭くなるので、 は左から非増加に並ぶ。従って、 以下の値は末尾の連続した区間にあり、その全体が へ置き換わる。
この性質から、同じ値が続く区間を一つの組 にまとめ、単調スタックで管理する。 は接尾辞最大値、 はその値を取る位置の個数である。スタックの底から頂上へ添字の左から右に対応させ、高さは厳密に減少させる。値の総和を変数 sum に持つ。最初にスタックを空、sum を0にしてから、次の手順を の順に行う。
- 新しい高さ を処理するとき、併合後の個数 を、新しい位置の分の1で初期化する。
- 頂上の高さ が である間、その組 を取り出す。
sumから を引き、 に を加える。 - を積み、
sumに を加える。この時点のsumが接尾辞最大値の和なので、sum + 1を として出力する。
例えば まで読んだスタックは、底から である。右へ高さ3を追加すると両方の組が取り出され、新しい位置も含めた になる。元の高さ2や1は、今後右にどんな高さを追加しても最大値の候補へ戻らない。ただし、それぞれの区間の個数は総和に必要なので、新しい組へ引き継ぐ。
典型の発動条件
単調stackによる区間併合
発動条件: 右端への追加によって、単調に並ぶ値の末尾側だけが同じ値へ置き換わるとき。等しい値の連続区間を高さと個数で持てば、変更箇所を頂上から取り出せる。本問では同じ高さも で併合し、高さが厳密に減る区間列にする。
集約値の差分維持
発動条件: 圧縮した区間を更新しながら、元の列全体の和も必要なとき。削除した区間の「高さ×個数」を総和から引き、新しい区間の寄与を加える。区間の高さが不要になっても、その個数まで捨てないことが要点である。
問題固有の要素
左から順に一杯ずつ移す操作を、完了後の水量の上限と結び付けることが本問の要点である。「初めて水が届く」という瞬間には手前の板がすべて等号でつながるため、時間を追う代わりに、直前の形を右から復元できる。
別の問題へ持ち帰る視点: 反復操作の初到達時刻を求めるときは、毎回増える総量と、到達直前に満たす境界条件を探す。時刻そのもののシミュレーションを省ける可能性がある。
正当性
初期状態では全水量が0なので、すべての板について が成り立つ。この条件を満たす状態から一回操作すると、考察で示した通り、等号の板では追加された一杯だけが右へ渡り、最初の厳密な不等号の手前、または最後の容器に一杯が残る。
一杯が残る容器を とすると、操作前後で変わるのは の1増加だけである。 なら板 の不等式は右辺が増える側なので保たれる。 なら板 には操作前に厳密な不等号があり、整数の左辺を1増やしても上限を超えない。他の板の両辺は変わらない。よって不変条件は何回操作しても保たれる。
容器 への初到達直前には である。次の一杯は板1から板 までを通るので、そこではすべて等号が成立する。従って右から復元した が実際の直前の水量であり、総水量に1を足した が求める回数である。
スタックが の同値区間とその総和を正しく表すとする。右端へ を加えると、末尾にある高さ 以下の区間だけが に変わる。手順はこの区間をちょうど取り出し、新位置を含む個数で一つにまとめ、元の寄与を引いて新しい寄与を足す。残る頂上の高さは より大きいため、区間の表現・高さの厳密な減少・総和のすべてを保つ。空のスタックから始めて各接頭辞でこの更新を行うので、毎回出力する sum + 1 は に一致する。
実装上の注意
- 同じ高さも で取り出し、一つの区間にする。条件を にすると高さの厳密な減少という不変条件が崩れる。
- でも同じ手順で を積み、 を出力する。高さが増える列では複数区間を併合し、減る列では取り出さず積む。同高の列も含め、特別な分岐は要らない。
- 総和には到達直前の水量だけを持つ。出力時に1を足し、その1を次の更新へ混ぜない。
- 高さと個数の積、および総和には64 bit整数を使う。積を求める時点から64 bitで計算し、32 bitで乗算してから変換しない。
復習の核
- 到達時刻が大きいときは、まず「直前にどこまで満たされているか」を探す。一杯が等号の板を通過することから、接尾辞最大値の形を復元できる。
- 接尾辞最大値の列は左から非増加である。右端への追加で変わるのが末尾だけなら、同値区間をスタックにまとめ、各区間を一度だけ消せる。
- 候補の値を捨てられても、和を求めるにはその値が代表していた個数を引き継ぐ。
計算量と制約
時間
。各高さにつき一組を積み、その組は高々一度だけ取り出される。内側の繰り返しの総回数は 以下であり、入力と各到達回数の出力を含めて線形時間となる。
空間
。高さが厳密に減る入力ではスタックに最大 組が残る。入力や答えを配列へ保存する場合も、全体で に収まる。
制約との対応
公式制約は 、 である。各容器の到達時刻は最大で なので、一回ずつ操作を再現する方針は使えない。高さの大きさによらない の手順と64 bit整数なら処理できる。時間制限は2秒、メモリ制限は1024 MiBである。
出典
公式問題文・個別公式解説は2026-10-23に再照合した。以下の確認日時は、保存済み出典の取得時点を保持している。
- 公式問題(2026-07-24T23:59:30+09:00確認) — source-abc359-e-problem-eb51ad038f13dca0efcc5ccca6afd91ec904df066f80b2da5974f7679fe2c227
- 個別公式解説(2026-07-24T23:59:30+09:00確認) — source-abc359-editorial-10262-ea2d05f58e64259f16d8f79a4e1d1735011cd9cc6ff98609133b62b2895323f5
分類・前提・執筆情報
掲載状態: 収録済み
最終確認:
学習上の位置付け
主題の単元: 支配関係から不要な候補を単調stack・queueで削る
- 主題
- 支配関係から不要な候補を単調stack・queueで削る: 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。
- 追加で学ぶ技能
- 既習技能
執筆: abc-explanation-author1.1.1 / revision 3
学習の位置
体系上の位置: 支配関係から不要な候補を単調stack・queueで削る
- 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。
この解説で扱わないこと:
- 全候補から極値を反復取得するheap・ordered set。
学習記録
状況更新: 更新記録なし
復習設定更新: 更新記録なし
端末内の保存状態を確認しています。
要復習一覧 / 学習記録のバックアップ / 解説に戻る