この問題文は、問題文の指示に従いながら適切にシミュレーションを実装する問題です。

入力の時点で \(A\) がソートされているので、これを利用して時間計算量 \(O(N)\) でこの問題を解いてみましょう。

• 高橋君が最後に chokutter を始めた時間 \({\rm open}\) を管理する。
• 青木君が高橋君のデスクの後ろを通る時間 \(a\) を時系列順に処理する。
  • もし \({\rm open} < a\) であれば、高橋君は時刻 \({\rm open}\) から時刻 \(a\) まで chokutter を見ていたことになるので、答えに \(a-{\rm open}\) を加算する。その後、次に chokutter を開く時間 \({\rm open} := a+100\) と更新する。
  • そうでないとき、青木君はただ通りかかっただけで高橋君の挙動には影響しないので、何もしない。
• 最後に、もし \({\rm open} < T\) であれば、高橋君は時刻 \({\rm open}\) から時刻 \(T\) まで chokutter を見ていたことになるので、答えに \(T-{\rm open}\) を加算する。

以上で適切にシミュレーションが実装され、この問題を時間計算量 \(O(N)\) で解くことが出来ました。

実装例 (C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,t;
  cin >> n >> t;
  int res=0;
  int open=0;
  for(int i=0;i<n;i++){
    int a;
    cin >> a;
    if(open<a){
      res+=(a-open);
      open=a+100;
    }
  }
  if(open<t){ res+=(t-open); }
  cout << res << "\n";
  return 0;
}