• HOME
  • 競プロ
  • ブログ
  • 問い合わせ

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

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

Edit

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

2022年1月24日

問題概要

問題ページ

[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()

プログラミング

  • TwitterTwitter
  • Share Share
  • PocketPocket
  • Hatena Hatena
  • LINE
  • URLコピー

-Edit
-ABC-Like-B

author

関連記事

no image
【pythonでABC200を解説】A - Century
no image
【pythonでABC161を解説】F - Division or Subtraction
no image
【pythonでABC216を解説】A - Signed Difficulty
no image
【pythonでABC179を解説】D - Leaping Tak
no image
【pythonでABC193を解説】D - Poker
no image
【pythonでABC211を解説】B - Cycle Hit
no image
【初心者向け】レッドローチの飼育環境の作り方

【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
  • 競プロ
  • ブログ
  • 問い合わせ

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

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