単調性のある式の解を二分法で数値的に求める

(2019-10-28)

AtCoder Beginner Contest 144の D - Water Bottleをやってみた。

高橋君は、底面が1辺 a cm の正方形であり、高さが b cm であるような直方体型の水筒を持っています。(水筒の厚みは無視できます。)
この水筒の中に体積 x cm^3 の水を入れ、底面の正方形の1辺を軸として、この水筒を徐々に傾けます。
水を溢れさせずに水筒を傾けることができる最大の角度を求めてください。

水を溢れさせずに水筒を傾けることができる最大の角度を度数法で出力せよ。
出力は、ジャッジの出力との絶対誤差または相対誤差が10^6以下のとき正解と判定される。

水が溢れるパターンは次の2通りあって、水が入っている、または入ってない部分の三角柱を除いた部分の体積がxになるようなθをatanで出せる。

解説を見ると、これに加えて二分法を使って数値的に求める解法も紹介されていた。 二分法というのは解が含まれる区間の中間での値を求め、その値が解より小さいか大きいかによって二分したどちらかの区間を選ぶ操作を繰り返すことで区間の幅を狭めて解を求めるアルゴリズム。収束条件として式に単調性がある必要があるが、θに対してこぼれる限界の水の体積の式は単調減少するので用いることができる。 解説にもコードが付いていたがまずは見ずに書いてみた。

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;

double waterVolume(int a, int b, double rad)
{
    if (rad < atan(1.0 * b / a))
    {
        return a * a * b - (a * (a * tan(rad)) / 2 * a);
    }
    else
    {
        return b * (b * tan(M_PI / 2 - rad)) / 2 * a;
    }
}

int main()
{
    double a, b, x;
    cin >> a >> b >> x;
    double min = 0, max = M_PI / 2;
    while (true)
    {
        double m = (min + max) / 2;
        double vol = waterVolume(a, b, m);
        if (abs(vol - x) < pow(10, -6))
        {
            cout << setprecision(8) << m / M_PI * 180 << endl;
            return 0;
        }
        else if (vol > x)
        {
            min = m;
        }
        else
        {
            max = m;
        }
    }
}

解説のコードでは、パターンの判定でa * tan(theta) <= bを使っているのと、有限回のループでxを上回らない最大のθを探すようになっていた。