AtCoder Beginner Contest

【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問題にしては少し面倒な問題。

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

問題文を整理

  • 容量\(N\)のバッテリーを持っている
  • 移動中は時刻 \(0.5, 1.5, 2.5, \ldots\)に、バッテリー残量が \(1\) [mAh] ずつ減少
  • カフェでは時刻\(0.5, 1.5, 2.5, \ldots\)に、バッテリー残量が \(1\) [mAh] ずつ増加

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

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

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

各(A_i,B_i) 毎の処理

  • \(0\)から\(A_1\)までに減少するバッテリーをNから引く
    • バッテリー残量はmin(\(NN-\)減少したバッテリー\(, 0)\)
    • バッテリー残量が\(0\)ならNoを出力
  • \(A_1\)から\(B_1\)までに増加するバッテリーを\(NN\)に足す
    • バッテリー残量はmin(\(NN+\)増加したバッテリー\(, N)\)
    • バッテリー残量\(N\)を超えない
  • 各\(A_i,B_i\)で処理を繰り返す
  • \(A_m,B_m\)(最後の\(A_m,B_m\))処理後に自宅に帰る
    • バッテリー残量はmin(\(NN-(T-B_m), 0)\)
    • バッテリー残量が\(0\)ならNoを出力
  • バッテリー残量を残して自宅に帰れればYesを出力

となる。

まず問題文を正確に把握することが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()

-AtCoder Beginner Contest
-