文系独学プログラマーの仕訳帳

  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ
  1. HOME >
  2. Edit >

Edit

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

2022年1月24日

問題概要

問題ページ

B - Sign of Friendship
B - Sign of Friendship

問題ページへ移動する

ストーリー

まずは友好の印として、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()

プログラミング

  • TwitterTwitter
  • Share Share
  • PocketPocket
  • Hatena Hatena
  • LINE
  • コピーする

-Edit
-ABC-Like-B

author

関連記事

no image
【pythonでABC158を解説】A - Station and Bus
no image
【pythonでABC195を解説】C - Comma
no image
【pythonでABC197を解説】B - Visibility
no image
【pythonでABC170を解説】A - Five Variables
no image
【pythonでABC177を解説】C - Sum of product of pairs
no image
【pythonでABC204を解説】C - Tour
東証1部上場IT企業に勤める私が思う競プロが仕事に役に立たない理由

【pythonでZONE2021を解説】A - UFO Invasion

【pythonでZONE2021を解説】C - MAD TEAM

たびすけ

東証1部上場企業の社畜
プログラミングとブログが趣味
勉強好きの怠け者
プログラミングを独学

サイト内検索

カテゴリ

最近のつぶやき

Tweets by XXXHOLiC_xxx
  • ブログ
  • プログラミング
    • python
    • Excel
    • データベース
  • 競技プログラミング
    • AtCoder Beginner Contest
  • カナヘビ
  • 雑記
  • Edit

タグ

ABC-A (68) ABC-B (55) ABC-C (43) ABC-D (37) ABC-E (21) ABC-F (11) ABC-Like-A (1) ABC-Like-B (1) ABC-Like-C (1) ABC-Like-D (1) BitDP (2) deque (3) DP (1) heapq (1) imos法 (1) n進数 (1) Union Find (3) Zアルゴリズム (1) セグメントツリー (2) ダイクストラ法 (1) トポロジカル (1) メモ化再帰 (3) レッドローチ (1) ワーシャルフロイド (1) 二分探索 (2) 幅優先探索 (2) 深さ優先探索 (1) 素数 (1) 組み合わせ (3) 論理演算 (4)
  • HOME
  • 競プロ
  • ブログ
  • 問い合わせ

文系独学プログラマーの仕訳帳

© 2022 文系独学プログラマーの仕訳帳