Codeforces Round#314(Div2) D.One-Dimensional Battle Ships

一次元のbattleshipをやって、Bobがショットを撃っていった結果、Aliceが言ってることが矛盾する場所を探す問題。

最近2分探索のイメージを常に頭の中に入れていたおかげですんなり解法が浮かんだ。
何番目までBobがショットを撃ってもAliceの言ってることが矛盾しないかを二分探索する。
ある番目まで撃った時にそれを満たす配置が存在するかを判定するのは割と簡単。
ある場所nowと、now+(船の長さ)-1の場所の間で他の船と接触しないかを判定するのに累積和を使ったが、他にどんな方法があるんだろう…。

    int N, K, A; cin >> N >> K >> A;
    int M; cin >> M;
    int S[M];
    for(int i=0; i<M; i++){
        cin >> S[i]; S[i]--;
    }
    int low = 0, high = M+1;
    while(high-low > 1){
        int mid = (low+high)/2;
        bool ok = false;
        int imos[N];
        bool used[N];
        memset(used, false, sizeof(used));
        memset(imos, 0, sizeof(imos));
        for(int i=0; i<mid; i++){
            used[S[i]] = true;
            imos[S[i]] = 1;
        }
        for(int i=1; i<N; i++){
            imos[i] += imos[i-1];
        }
        int cnt = K;
        int now = 0;
        while(cnt > 0 && now+A-1 < N){
            if(used[now]){
                now++;
                continue;
            }
            if(imos[now] != imos[now+A-1]){
                now++;
                continue;
            }
            cnt--;
            now = now+A+1;
        }
        if(cnt == 0 && mid == M){
            cout << -1 << endl;
            return 0;
        }
        if(cnt == 0) ok = true;
        if(ok){
            low = mid;
        }else{
            high = mid;
        }
    }
    cout << low+1 << endl;