jag2016-domestic.contest.atcoder.jp
問題文
省略
解法(反転して表示)
時刻 a に宅配便が届くと,[a-M,a+M)の範囲に書斎には居られない. なので,[0,T)の範囲で区間に含まれていない時刻を列挙すれば良い. 境界に気をつけつつ,愚直にシミュレーションすると時間計算量 O(NM+T) で解ける.いもす法を使うと O(N+T) になるけど制約的にどうでもいい.
ソース
#include <bits/stdc++.h> using namespace std; int imos[20100]; int main(){ int N,M,T; cin >> N >> M >> T; for(int i = 0 ; i < N ; i++){ int a; cin >> a; for(int j = 0 ; j <= M ; j++) if( a - j >= 0 ) imos[a-j] = true; for(int j = 0 ; j < M ; j++) if( a + j < T ) imos[a+j] = true; } int ok = 0; for(int i = 0 ; i < T ; i++){ // cout << imos[i] << " " << i << endl;; if( !imos[i] ){ ok++; } } cout << ok << endl; }