【pythonでABC185を解説】B - Smartphone Addiction

問題概要

問題ページ

問題文

高橋君のスマートフォンのバッテリー容量は \(N\) [mAh] であり、時刻 \(0.5, 1.5, 2.5, \ldots\) に、つまり時刻 \(n + 0.5\,(n\) は整数\()\) を迎える度にバッテリー残量が \(1\) [mAh] ずつ減少します。
高橋君はスマートフォンを満充電した状態で時刻 \(0\) に外出し、途中で \(M\) 回カフェを訪れ、時刻 \(T\) に帰宅します。
\(i\) 回目に訪れるカフェには時刻 \(A_i\) から時刻 \(B_i\) まで滞在します。カフェに滞在している間はスマートフォンを充電するため、バッテリー残量は減少せず、代わりに時刻 \(n + 0.5\,(n\) は整数\()\) を迎える度に \(1\) [mAh] ずつ増加します。ただし既にバッテリー残量がバッテリー容量と等しい場合、バッテリー残量は増えも減りもしません。
高橋君が途中でスマートフォンのバッテリー残量が \(0\) になることなく帰宅することができるかを判定してください。

制約

• \(1 \le N \le 10^9\)
• \(1 \le M \le 1000\)
• \(1 \le T \le 10^9\)
• \(0 \lt A_1 \lt B_1 \lt A_2 \lt B_2 \lt A_3 \lt B_3 \lt \dots \lt A_M \lt B_M \lt T\)
• 入力は全て整数

問題の考察

B問題にしては少し面倒な問題。

まずは問題文を整理してみます。

移動中かカフェにいるかの境界は、\(0.0, 1.0, 2.0, \ldots\)だけなのでその時点で移動中かカフェにいるかでバッテリーが増加するか減少するかが決定することになる。

各\(A_i,B_i\) については移動→カフェ→移動→カフェ\(\ldots\)となるので、順に処理を行えば良い。

現在のバッテリー容量を\(NN\)とすると

となる。

まず問題文を正確に把握することがB問題としてはハードルが高い上に、バッテリー上限等の制約がありコーディングも間違えやすい要素が多めの問題。

基礎力が問われる問題。

たびすけ

問題文もコーディングもB問題の中では難しですが、焦らず正確に解答すれば解けます！
各文法の使い方を復習しておきましょう！

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, m, t = list(map(int, input().rstrip('\n').split()))
    tn = n
    pt = 0
    for i in range(m):
        a, b = list(map(int, input().rstrip('\n').split()))
        tn = max(tn - (a - pt), 0)
        pt = b
        if tn == 0:
            print("No")
            exit()
        else:
            tn = min(tn + (b - a), n)
    print("Yes" if tn - (t - pt) > 0 else "No")


if __name__ == '__main__':
    solve()