簡単ですが，なぜか詰まった覚えがあるので記事にしておくことに．
問題概要
正の整数 $ A,\, B,\, C $ と，以下の関数 $ f(t) $ が与えられる．
- $ f(t) = At + B \sin{C \pi t} $
$ t \geq 0 $ かつ $ f(t) = 100 $ であるような $ t $ を $ 1 $ つ見つけよ．
制約
- $ 1 \leq A, B, C \leq 100 $
考察
この問題文は，求める $ t $ はあるものとして書かれているが念のため確認をする． 制約から $$ -100 \leq B \sin{C \pi t} \leq 100 $$ は明らかである．一方で $ At $ は $ t $ が大きくなれば無限に大きくなる． $ f(0) = 0 $ であり $ f(t) $ は明らかに連続関数であるから，中間値の定理より必ず $ 1 $ つは解が存在する．
具体的には制約から $ f(200) \geq 100 $ であることが保証されるので，区間 $ [0,200] $ に解が存在することが分かる． 中間値の定理で存在が保証される解を $ 1 $ つ見つけるアルゴリズムとして，二分法が知られる． 二分探索と同様の手法で，解の存在範囲を狭めていくアルゴリズム (https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%B3%95)．
$ f(t) $ の計算自体は高速に行うことが出来るので，十分収束する回数二分法を回すことで正解が得られる．
個人的ポイント
- 連続関数 $ f(x) $ に対して $ f(x) = const. $ みたいな方程式の解を $ 1 $ つ求めるときは二分法．
- 最小のものとかになるとまた話は変わってくる．
- 今回は常に解が存在したが，しない場合があるような制約で出題されることもありそう．
- しっかりと存在しない条件を確認する．
