Subscribed unsubscribe Subscribe Subscribe

Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

AtCoder Beginner Contest 026 D - 高橋君ボール1号

D - 高橋君ボール1号

時間制限 : 2sec / メモリ制限 : 256MB

問題文

高橋君は野球が得意です。高橋君は、高橋君ボール 1 号という変化球を投げることが出来ます。

このボールは、投げてから t 秒後のボールの位置を f(t) とすると、 f(t)=A×t+B×sin(C×t×π) と表すことが出来ます。

あなたは、t≧0 かつ f(t)=100 となるタイミングで、ボールを打たなければいけません。この時の t を求めたいです。

note

中間値の定理(実数直線 R の閉区間 I =[a, b]上で定義される連続な実数値関数 f が f(a) < f(b) を満たすとき、閉区間[f(a), f(b)]内の任意の点 γ に対して、γ = f(c) となる I 内の点 c が存在する。)より二分探索が使える。

要は左と右を決めてあげてその真ん中をmidとするとf(mid)が100より小さければ左をmidで更新、大きければ右をmidで更新というのを、許容誤差に収まるまで二分探索すればよい。