雨水を溜める

谷を数えようとすると、どこまでが 1 つの谷か決まらない

[0,1,0,2,1,0,1,3,2,1,2,1] に雨を降らせると 6 溜まります。この 6 をどう数えるかを考えるとき、多くの人はまず「谷を見つけて、その谷の面積を出す」方向へ進みます。

ところが谷は入れ子になります。小さなくぼみの上に、もっと大きなくぼみがかぶさっている。どこからどこまでを 1 つの谷と呼ぶかが決まらず、境目の扱いで場合分けが増えていきます。面のまま数えようとした時点で、この問題は難しくなります。

縦に 1 マスずつ数える

見方を変えて、位置 i の真上に水が何段積まれるかだけを考えます。すると、その 1 マスの水位を決めているのは 3 つの値だけになります。自分の高さと、自分より左にある壁のいちばん高いところと、自分より右にある壁のいちばん高いところです。

バケツと同じで、低いほうの壁を越えた水はこぼれます。だから水面の高さは、左右の高いほうではなく低いほうで決まります。そこから自分の高さを引いた分が、その位置に溜まる量です。全部の位置で足せば答えになります。

谷の境目という話が消えて、各位置を独立に計算できる形になりました。残るのは、左右の最大値をどう用意するかだけです。

「そこまでの最大」は、1 回なめれば作れる

位置ごとに毎回左側を全部見直すと O(n^2) に戻ってしまいます。しかし左側の最大値は、1 つ手前の結果から一手で作れます。

temps = [12, 15, 14, 18, 16]
best = []
current = temps[0]
for t in temps:
    current = max(current, t)
    best.append(current)   # その日までの最高気温

同じ要領で右端からも 1 回なめれば、両側の最大値が揃います。配列を 2 本ぶん持つのでメモリは O(n) 使いますが、時間は O(n) に収まります。

メモリまで削りたい場合は、両端から 2 つの位置を寄せていく書き方があります。低いほうの側だけは先に確定させてよい、という性質を使う手ですが、飲み込みにくいので、まずは配列を用意する形で確実に動かしてからで構いません。

境目の扱いも先に決めておきます。左側の最大値に自分自身を含めるかどうかで、答えが変わります。含めておくと、自分が周りより高いときに水位と高さが同じになり、溜まる量が素直に 0 になります。含めないと負の値が出るので、後から 0 に丸める処理が要ります。どちらでも正解には辿り着けますが、丸め忘れると [5,5,5,5] のような入力で合計がずれます。

そして空の配列です。長さ 0 で先頭の要素を読もうとすると落ちるので、いちばん最初に片付けておいてください。

やってみよう

ひな形の TODO を完成させてください。左右の最大値更新と、水位から高さを引く式を自分で書きます。入力を受け取る枠と説明つきの準備部分はそのまま使えます。

演習で使う書き方

本文の最高気温の表は、前の記録と今日の値の大きいほうを保存します。演習は左右から同じ記録を作ります。max は大きい値、min は小さい値を返します。range(n - 2, -1, -1) は右の手前から 0 までの逆順です。表の確保と両端の初期化を用意し、左右の更新式と水量の式を書きます。

1. 左右の最大値更新と、水位から高さを引く式を自分で実装する
2. 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える