【ABC408】A問題 - Timeout 考察から実装(c++)まで

AtCoderBeginnerContest408の解説＆感想です。
コンテストリンク

問題一覧

• 【ABC408】A問題 - Timeout　考察から実装(c++)まで <- イマココ
• 【ABC408】B問題 - Compression　考察から実装(c++)まで
• 【ABC408】C問題 - Not All Covered　考察から実装(c++)まで
• 【ABC408】D問題 - Flip to Gather　考察から実装(c++)まで
• 【ABC408】E問題 - Minimum OR Path　考察から実装(c++)まで
• 【ABC408】F問題 - Athletic　考察から実装(c++)まで

A問題 - Timeout

問題リンク

問題概要

単調増加な自然数列$T=(T_1,T_2,...,T_N)$が与えられる。
$T_0=0$として、$T_i + S \lt T_{i+1}$となる場所があるか判定せよ。

制約

• $ 1 \le N,S \le 100 $
• $ 1 \le T_i \le 1000 $
• $ T_i < T_{i+1} $

考察

問題文の読解がちょっと難しいけど、問題概要くらいまで簡略化したら解きやすそう。
隣り合う二つで条件を満たす場所が欲しいので、adjacent_findが使えそう。
計算量は$O(N)$

実装

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;

int main(void){
    //入力
    ll N,S;
    cin>>N>>S;
    
    vll T(N+1,0);
    for(int i=1;i<=N;i++) cin>>T[i];
    
    //Tの中で、初めてT[i] +S < T[i+1]となるインデックスを取得
    ll idx = adjacent_find(T.begin(), T.end(), [&](ll a, ll b){ return a+S < b; }) - T.begin();
    cout<<(idx==N+1?"Yes":"No")<<endl;
    return 0;
}