技術室奥プログラミングコンテスト#2に参加しました

ABCの3完53位でした。Cは一回WAしました。
Aは文字列の連結、Bは基本的な動的計画法だったのではしょります。C問題だけメモ。

tkppc2.contest.atcoder.jp

n個の0と1からなる数列があります。このうちk個の0を1にかえて、できるだけ1が連続するような部分列をつくりましょう、そしてその長さを求めましょう、という感じです。

二分探索を使いました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int n, k;
    int zeronum[100001] = {};
     
    bool cangetvacation(int m)
    {
        for(int i = 1; i + m - 1 < n + 1; i++){
            if(zeronum[i + m - 1] - zeronum[i - 1] <= k) return true;
        }
        return false;
    }
     
    int main()
    {
        
        cin >> n >> k;
        for(int i = 1; i < n + 1; i++){
            int h;
            cin >> h;
            zeronum[i] = zeronum[i - 1];
            if(h == 0) zeronum[i]++;
        }
        int left = 1, right = 100000;
        while(right - left > 1){
            int mid = (left + right) / 2;
            if(cangetvacation(mid)) left = mid;
            else right = mid;
        }
        cout << left << endl;
        return 0;
    }

zeronum[i]には1番目からi番目までで含まれる0の数を表しています。
zeronumが求め終わったら二分探索を行います。
cangetvacation関数は、m個連続する部分列があるかを調べます。この結果を二分探索に利用しています。

nもkも10^5なので間に合うか心配でしたが意外とすっと通ったので良かったです。
最初cangetvacation関数でzeronum[i + m - 1] - zeronum[i - 1]をzeronum[i + m] - zeronum[i]にしてたのでWAしました。注意しないとですね。