【AtCoder】ABC 185 B - Smartphone Addiction

2026-11-07

AtCoder/ABC/B問題 AtCoder/ABC/200点問題 AtCoder/灰Diff AtCoder/NoviSteps/6Q AtCoder/シミュレーション競技プログラミング

B - Smartphone Addiction

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 93 / NoviSteps: 6Q / 配点: 200 点

問題概要

高橋君のスマートフォンのバッテリー容量は $N$ [mAh] であり、 $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$
入力は全て整数

考察

時間を進めながら、スマートフォンのバッテリーの残量をシミュレーションすればよい。

最後のカフェから帰宅までの時間を忘れないようにすること。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    int N, M, T;
9.    cin >> N >> M >> T;
10. 
11.    int now = N, time = 0;
12.    while (M--)
13.    {
14.        int A, B;
15.        cin >> A >> B;
16. 
17.        now -= A - time;
18.        time = A;
19.        if (now <= 0) {
20.            cout << "No" << endl;
21.            return 0;
22.        }
23. 
24.        now = min(N, now + (B - A));
25.        time = B;
26.    }
27. 
28.    now -= T - time;
29.    time = T;
30.    if (now <= 0) {
31.        cout << "No" << endl;
32.        return 0;
33.    }
34. 
35.    cout << "Yes" << endl;
36. 
37.    return 0;
38.}