けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 144 D - Water Bottle (茶色, 400 点)

これかーーー数学ゲーじゃないかと物議を醸した問題。でも普通にいい問題だと思う!!

問題へのリンク

問題概要

底面が一辺  a cm の正方形であり、高さが  b cm であるような直方体型の水筒に、体積  x cm3 の水を入れる。

底面の正方形の一辺を軸として、この水筒を徐々に傾ける。水を溢れさせずに水筒を傾けることができる最大の角度を求めよ。

考えたこと

確かに  O(1) で解ける数学ゲーだけど、問題のシチュエーション自体はゲームプログラミングで部分的に出てきそうな雰囲気だし、教育的な問題だと思う。それに、 O(1) で殴れなくても、二分探索する解法もある。

ところで、この問題は三次元の問題だけど、本質的には二次元の問題といえる。 x はあらかじめ  a で割って、立方体の側面に関する二次元幾何の問題として解くことにする。つまり、あらかじめ

  •  x = x/a

としておく。 さて、水がこぼれるシチュエーションは大きく分けて二通りある。

f:id:drken1215:20200426184614p:plain

このうちのどちらのシチュエーションになるのかについては簡単に求めることができる。

  • 前者:  x \gt \frac{ab}{2} のとき
  • 後者:  x \le \frac{ab}{2} のとき

幾何をする

幾何をしてみると、下図のようになる。前者については

  • 白い直角三角形のところの面積は  ab - x となる
  • よって、白い直角三角形の、長さ  a の辺以外のもう一つの辺の長さは  \frac{2(ab-x)}{a} となる

という風に求められる。後者についても同様に

  • 水色の直角三角形の面積は  x である
  • よって、水色の直角三角形の、長さ  b の辺以外のもう一つの辺の長さは  \frac{2x}{b} となる

という風に求められる。

f:id:drken1215:20200426190524p:plain

この図から言えることは、

  • 前者については、 \tan \theta = \frac{\frac{2(ab-x)}{a}}{a} = \frac{2(ab-x)}{a^{2}}
  • 後者については、 \tan \theta = \frac{b}{\frac{2x}{b}} = \frac{b^{2}}{2x}

ということがわかる。よって求める角度  \theta は、

  • 前者:  \theta = {\rm atan} \frac{2(ab-x)}{a^{2}}
  • 後者:  \theta = {\rm atan} \frac{b^{2}}{2x}

となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    const double PI = acos(-1.0);
    double a, b, x;
    cin >> a >> b >> x;
    x /= a;
    cout << fixed << setprecision(10);
    if (x > a*b/2) cout << atan2((a*b-x)*2, a*a) * 180 / PI << endl;
    else cout << atan2(b*b, x*2) * 180 / PI << endl;
}

別解: 二分探索

角度を  \theta としたときの、水の面積を  f(\theta) とすると、この問題は


 f(\theta) = x という方程式を解け


という問題だと言える。このような方程式の解を求める方法として、二分探索はとても有力だ。あとは素直に、関数  f(\theta) を実装すれば OK!!!

#include <bits/stdc++.h>
using namespace std;

int main() {
    const double PI = acos(-1.0);
    double a, b, x;
    cin >> a >> b >> x;
    x /= a;
    auto f = [&](double t) {
        // 前者
        if (tan(t) <= b/a) return a*b - a*(a*tan(t))/2;
        // 後者
        else return b*(b/tan(t))/2;
    };
    double left = 0, right = PI/2;
    for (int iter = 0; iter < 100; ++iter) {
        double theta = (left + right) / 2;
        if (f(theta) >= x) left = theta;
        else right = theta;
    }
    cout << fixed << setprecision(10) << left*180/PI << endl;
}