【競プロ】過去問精選100問「AtCoder Beginner Contest 023 D - 射撃王」解法

2021年11月2日 2021年11月2日

TheLogicalBear

Free-PhotosによるPixabayからの画像

このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】でまとめられている100問をPythonで解いています。

問題

AtCoder Beginner Contest 023 D - 射撃王

ポイント

この問題は任意のペナルティ以下で風船を全て割れるかどうかを二分探索で確認していき、

ペナルティの最小値を求めることで解くことができます。

コード

def main():
    import sys
    import bisect
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline

    # 任意のペナルティ以下で風船を全て割れるかを確認する関数
    def is_ok(x: int):
        limits = []
        for i in range(N):
            limit = (x - list_H[i]) // list_S[i]  # 任意のペナルティ以下に抑えるために風船を割らなければならない時間
            limits.append(limit)
       
        # 時間が短い順に風船を割っていく
        limits.sort()
        for i, v in enumerate(limits):
            if i > v:
                return False

        return True

    # ペナルティを二分探索するための関数
    def binary_search(x: int, y: int):
        while abs(x - y) > 1:
            mid = (x + y) // 2
            if is_ok(mid) == 1:
                y = mid
            else:
                x = mid
        return y

    # 各風船の初期高度Hと変動高度Sを取得
    N = int(input())
    list_H = []
    list_S = []
    for _ in range(N):
        H, S = map(int, input().split(" "))
        list_H.append(H)
        list_S.append(S)

    # 二分探索でペナルティの最小値を求める
    print(binary_search(0, int(1e+14)))


if __name__ == '__main__':
    main()

この記事を書いた人

TheLogicalBear