ABC026 D - 高橋君ボール1号

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def f(A, B, C, t):
    return A * t + B * math.sin(C * t * math.pi)


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, C = il()

    mi, mx = 0, 101
    while True:
        me = (mx + mi) / 2
        time = f(A, B, C, me)
        if str(time).startswith('100.0000000'): break
        if time > 100:
            mx = me
        else:
            mi = me
    print(me)


if __name__ == '__main__':
    main()

考え方

ある時間tのとき、ボールの位置が100より上回っている場合はtを少なくし、
ボールの位置が100を下回っている場合にはtを大きくする。
小数点も含んだ全ての範囲を普通に探索するのは時間が足りないため、
二分探索を用いてある時間tの探索を行なう。

二分探索 - Wikipedia

初めに、tが取りうる最小値と最大値より上回る値を用意し(mi, mx = 0, 101)、
その中央値をtとしたf(t)を計算する。
f(t)の結果が100を上回っている場合には最大値を中央値に変え(mx = me)、
下回っている場合には最小値を中央値に変える(mi = me)。

これをf(t)の結果が100と一致するまで繰り返すことによって、
ある時間tを探索することができる。

ちなみに、この問題ではf(t)の結果に少数が含まれており、
10^-6まで誤差が許容されているため、
f(t)の先頭が100.0000000と一致しているtを回答とした。