AtCoder ABC 026 D - 高橋君ボール1号 (試験管水色)

方程式を解くタイプの二分探索の問題ですね。

• 問題へのリンク

問題概要

正の整数 が与えられます。 秒後のボールの位置 は

で表されます。 を満たす実数 の値を十分高い精度で求めてください。

を満たせば正解とみなされます。

制約

• 

解へのアプローチ

の解を数学的に直接求めることはいかにも難しそうです。このようなとき、二分探索法が有効となることがあります。まず、

• 
• 

を満たすような () があったならば、

• 
• 

を満たすような実数 が存在することに注意しましょう (中間値の定理)。つまり、区間 の中に「 から に変わる瞬間」があるということです。そしてそのような をまさに二分探索法で求めることができます。

二分探索法へ

前述のように、区間 の中に「 から に変わる瞬間」があることがわかったとき、この範囲を狭めていくことができます。

具体的には としたときに、

• ならば、範囲を区間 に絞る
• ならば、範囲を区間 に絞る

という風にできます。どちらの場合であっても、区間の幅が になります。二分探索法をたとえば 回などやれば、区間の幅は 倍になります。

初期値 を求める

最後に、二分探索法の初期値を決めましょう。つまり

• 
• 

を満たすような を具体的に決めましょう。 の方は簡単です。

ですので、たとえば とすればよいでしょう。

次に の方です。まず が大きくなればなるほど は大きくなることに注意しましょう。したがって、十分大きな に対しては となることが推測されます。

ここで、 の値の範囲は の範囲に限られることに注意しましょう。よって、 などとすれば

　(, より)

となります。よって の値を 以上の値にすればよいでしょう。

コード

以上の考察は、次のように実装できます。なお、円周率 は、acos(-1.0) の値を用いるのが有効です。

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

// 円周率 PI
const double PI = acos(-1.0);

int main() {
    // 入力
    int A, B, C;
    cin >> A >> B >> C;

    // 関数 f
    auto func = [&](double t) -> double {
        return A * t + B * sin(C * PI * t);
    };

    // 二分探索
    double alpha = 0, beta = 200;
    for (int iter = 0; iter < 100; ++iter) {
        double gamma = (alpha + beta) / 2;
        if (func(gamma) <= 100) alpha = gamma;
        else beta = gamma;
    }

    // 小数点第 15 位まで出力 (ヘッダ <iomanip> が必要)
    cout << fixed << setprecision(15) << alpha << endl;
}