AtCoder版蟻本中級編

ABC026D 高橋君ボール1号

この記事で使うアルゴリズム

二分探索

はじめに

カテゴリーAtCoder版蟻本中級編では、AtCoder 版！蟻本 (中級編)でまとめられている問題をPythonで解いています。

問題

https://atcoder.jp/contests/abc026/tasks/abc026_d

方針

二分探索を用いて解くことができます。関数は単調増加ではありませんが、解の一つを求めれば良いだけなので問題ありません。

またb * math.sin(c*t*math.pi)の最小値は-bであることと、a,bの制約から、解はt=200より大きくは成り得ないことがわかります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
import math
a,b,c = map(int,input().split())
def func(t):
    return a * t + b * math.sin(c*t*math.pi)
l = 0
r = 400
for i in range(100):
    mid = (l + r) / 2
    if func(mid)>100:
        r = mid
    else:
        l = mid
print (mid,func(mid))

記事情報

  • 投稿日：2020年6月19日
  • 最終更新日：2020年6月19日