読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 026 D - 高橋君ボール1号

abc 誤差 二分探索

問題

問題概要

省略

解法

2分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ。100より小さいなら、増加していく関数なので、右側の範囲に解をもつことになる。このような考えて、2分探索を実装すればいい。
問題に与えられている、 |f(t)−100|<=10-6は関数の値の誤差のことなので、tはもっと厳密に出さないといけないのかな? 最後を%.9fだとWAになった。

ミス

誤差はうまく扱うのが難しいなー。 tの最小値ならどう出すんだ?

コード

再帰関数

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)

double a, b, c; 
double f(double t){
    return a * t + b * sin(c * t * M_PI);
}

int main(void){
    cin >> a >> b >> c;

    double l = -1000.0, r = 1000.0;
    rep(i, 10000){//十分な回数を回す
        double mid = (l + r) / 2.0;
        // 真ん中で100より小さいなら、真ん中より右側にこたえがある
        if(f(mid) < 100.0) l = mid;
        //真ん中で100より大きいなら、中間値の定理より、左側に必ずf=100となるtが存在する
        else r = mid;
    }
    printf("%.12f\n", l);
}