読者です 読者をやめる 読者になる 読者になる

JAG Contest 2016 Domestic B - 豪邸と宅配便

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;
}