【AtCoder】ABC 408 A - Timeout | 緑コーダーが解くAtCoder

atcoder.jp

配点: 150 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 35 / NoviSteps: 7Q

問題概要
制約
考察
実装例
コメント

問題概要

ある長老は、最後に肩を叩かれてから $S+0.5$ 秒以上経過すると寝てしまう。

現在長老は起きており、付き人がちょうど長老の肩を叩いた。これから付き人はちょうど $N$ 回長老の肩を叩き、 $i$ 回目の肩叩きは現在から $T_i$ 秒後に行われる。

長老が現在から $T_N$ 秒後まで連続して起きているかを判定せよ。

制約

$1 \leq N, S \leq 100$
$1 \leq T_i \leq 1000$
$T_i \lt T_{i+1}$
入力はすべて整数

考察

以下では、 $T_0 = 0$ とする。

長老は、 $T_i - T_{i-1} \lt S$ のときは、現在の $T{i-1}$ 秒後から $T_i$ 秒後まで起きている。逆に、 $T_i - T_{i-1} \gt S$ のときは途中で寝てしまう。

したがって、 $i = 1, 2, \dots, N$ について、ある $i$ で $T_i - T_{i-1} \gt S$ となれば答えはNoとなる。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

// ======================================== //

int main()
{
    int N, S;
    cin >> N >> S;
    vector<int> T(N + 1, 0);
    rep(i, 1, N + 1) cin >> T[i];

    rep(i, 1, N + 1)
    {
        if (T[i] - T[i - 1] > S)
        {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}