【pythonでZONE2021を解説】B - Sign of Friendship

問題概要

問題ページ

[st-card-ex url="https://atcoder.jp/contests/zone2021/tasks/zone2021_b" target="_blank" rel="nofollow" label="" name="" bgcolor="" color="" readmore="問題ページへ移動する"]

ストーリー

まずは友好の印として、UFO の操縦プログラムをクラッシュさせてみよう。俺は机の上の ZONe 缶に偽装した USB から、地球最強のコンピュータウイルス「KARATE」を取り出した。
こいつを UFO に送りつけてやる。UFO がどんなシステムを使っているかは分からないが、あらゆるシステムをクラッシュさせてきた KARATE は、きっと効くはずだ。

問題文

あなたは今、高さ \(1000\) の非常に高いタワーの下にいます。タワーから距離 \(D\) 離れた位置の上空 \(H\) の高さに UFO がおり（入出力例 1 の図を参照してください）、あなたは UFO に電波を届けたいです。
タワーと UFO の間には遮蔽物が \(N\) 個あります。\(i\) 番目の遮蔽物はタワーから UFO の方向に向かって距離 \(d_i\) の場所に位置していて、高さは \(h_i\) です。
あなたはタワーを上って、あなたと UFO の間の直線上に遮蔽物が \(1\) つも無い状態にしたいです。上る必要のある最低の高さを求めてください。
なお、地面は凹凸のない水平面であり、タワー及び遮蔽物は地面と垂直に建っているものとします。
また、あなたと UFO の間の直線上にちょうど遮蔽物の上端があるとき、その遮蔽物には遮蔽されていないものとします。

制約

• 入力は全て整数
• \(1 ≤ N ≤ 100\)
• \(1 ≤ d_i < D ≤ 1000\)
• \(1 ≤ h_i < H ≤ 1000\)

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, d, h = list(map(int, input().rstrip('\n').split()))
    ans = 0
    for i in range(n):
        dv, hv = list(map(int, input().rstrip('\n').split()))
        t = (h - hv) / (d - dv)
        ans = max(ans, hv - (t * dv))
    print(ans)


if __name__ == '__main__':
    solve()

二分探索でも解答可能

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, d, h = list(map(int, input().rstrip('\n').split()))
    dh = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    t = h / d
    cost = True
    for dv, hv in dh:
        if dv * t < hv:
            cost = False
            break
    if cost:
        print(0)
    else:
        cor_v = 10 ** 4
        inc_v = 0
        while cor_v - inc_v > 0.000000001:
            bin_v = (cor_v + inc_v) / 2
            cost = True
            #条件を満たすcostを全検索
            t = (h - bin_v) / d
            for dv, hv in dh:
                if dv * t + bin_v < hv:
                    cost = False
                    break
            #costが制約を満たすか
            if cost:
                cor_v = bin_v
            else:
                inc_v = bin_v
        print(cor_v)


if __name__ == '__main__':
    solve()