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

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

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

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

問題概要

正の整数  A, B, C が与えられます。 t 秒後のボールの位置  f(t)

 f(t) = At + B \sin(C \pi t)

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

 |f(t) - 100| \le 10^{-6} を満たせば正解とみなされます。

制約

  •  1 \le A, B, C \le 100

解へのアプローチ

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

  •  f(\alpha) \lt 100
  •  f(\beta) \gt 100

を満たすような  \alpha, \beta ( \alpha \lt \beta) があったならば、

  •  \alpha \lt x \lt \alpha
  •  f(x) = 100

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

二分探索法へ

前述のように、区間  (\alpha, \beta) の中に「 f(x) \lt 100 から  f(x) \gt 100 に変わる瞬間」があることがわかったとき、この範囲を狭めていくことができます。

具体的には  \gamma = (\alpha + \beta) / 2 としたときに、

  •  f(\gamma) \le 100 ならば、範囲を区間  (\gamma, \beta) に絞る
  •  f(\gamma) \ge 100 ならば、範囲を区間  (\alpha, \gamma) に絞る

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

初期値  \alpha, \beta を求める

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

  •  f(\alpha) \lt 100
  •  f(\beta) \gt 100

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

 f(0) = 0

ですので、たとえば  \alpha = 0 とすればよいでしょう。

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

ここで、 \sin t の値の範囲は  -1 \le \sin t \le 1 の範囲に限られることに注意しましょう。よって、 t = 200 などとすれば

 f(200) = 200A + B \sin(C \pi t) \ge 200 - 100 \ge 100 ( A \ge 1,  B \le 100 より)

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

コード

以上の考察は、次のように実装できます。なお、円周率  \pi は、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;
}