AOJ 1133 - Water Tank - ツバサの備忘録

Water Tank | Aizu Online Judge
提出コード

そのまま実装するとかなり重くなりそうなので、なにかいい手がないかを調べます。初見で解けなかったときに、こちらのブログ( Water Tank (AOJ1133) - sigma425のブログ )に一度目を通していたため、トップダウンで解くとスッキリ行きそう、ということだけ知っていたので、そこをベースにしました(この解説を見たときは忙しく、実装できてませんでした)。
ということで、トップダウンで再帰を利用しうまく解いていく方法を考えます。
その前に、ある程度の方針を立てるため、仕切りの少ないパターンについて少し考えてみます。
f:id:emtubasa:20180804135911p:plain 上の図のような水槽について考えます。
仕切りは3つで、グレーと緑の間、緑と水色の間、水色と青の間の黒い線です。
求めたい高さのx座標が、グレーの範囲にあったとします。
この時、答えとなる高さはこの図でいうとグレー、黄、赤の3種類になります。
さて、どのようなときにこの3種類に分けられるのでしょうか。上から見ていくことにします。

(ⅰ) 赤となるパターン
高さが赤となるには、その他すべての色(グレー～橙までの6色)の部分が水で満たされていないといけません。ということは、高さを調べる時刻tのときに、赤の範囲(つまりこれは水槽全体です)にある蛇口からでる水量が、6色分の範囲の容積を上回ってる必要があります。
これは言い換えると、以下のようになります。

赤の範囲内の蛇口からでる水量で、範囲内の仕切りで最も大きい仕切りの高さに到達する

このとき、高さは
$\begin{align}\frac{赤の範囲内の蛇口からでる水量}{赤い範囲の底面積}\end{align}$
となります。高さが50を超えると水が溢れるので、それ以上にならないことにも気をつけてください。

(ⅱ)黄となるパターン
高さが黄色になるには、黄色の下の部分、すなわち緑とグレーの部分が水で満たされている必要があります。
なので、(ⅰ)と同じように、黄色の範囲内の蛇口からでる水量だけ考えようと思うところですが、少し注意が必要です。
橙の範囲から溢れてくる水が存在するからです。橙色の範囲からあふれる条件は、次のようになります。

橙の範囲の蛇口の水量が、3色(橙、青、水色)の容積を超えていた場合

このときに溢れてくる水量は、
$(橙の範囲の蛇口から出る水量)-(橙、青、水色の範囲の容積)$
となります。
これを足し合わせて、(ⅰ)と同じ考え方をすると、

黄色の範囲内の蛇口からでる水量と、橙の範囲から溢れてくる水量の和が、範囲内の仕切りで最も大きい仕切りの高さに到達する

このときに、高さが
$\begin{align}\frac{黄色の範囲内の蛇口からでる水量+橙の範囲から溢れてくる水量}{黄色の範囲の底面積}\end{align}$
となります。(ⅰ)のパターンを除外しているため、たかだか黄色の範囲の高さにしかならないことにも気をつけてください。

(ⅲ)グレーとなるパターン
上記の(ⅰ)および(ⅱ)でなければ、自動的にグレーにの高さにしかなりません。このときの高さを求めたいのですが、その前に(ⅱ)と同様、緑の範囲から溢れてくる水量を求めることにします。
緑の範囲に注ぎ込まれる水は、橙の範囲から溢れる分もあることに注意すると、
$(緑の範囲の蛇口からでる水量+橙の範囲から溢れてくる水量)-緑の範囲の容積$
となります。
ここまでくると後は(ⅱ)と同様に、 $\begin{align}\frac{グレーの範囲内の蛇口からでる水量+緑の範囲から溢れてくる水量}{グレーの範囲の底面積}\end{align}$
で高さを求めることができます。

これを、再帰を用いて一般化します。
solveという関数をつくり、引数には現在の範囲の左端と右端、そしてその範囲における高さの最大値をとります。最初の呼び出しは(0,100,50)となります。戻り値では、目的の場所の高さを返すようにします。