ちゃっくのメモ帳

ちゃっくがメモしときたいことをメモしとくよ

技術室奥プログラミングコンテスト#2 C問題 有給休暇を解いたんだよ...

tkppc2.contest.atcoder.jp

解法

二分探索で長さL(実際のコード中では"mid")の連続した1を作るか確認していき、作れる最長の長さを出力すればいい。

ソースコード

#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF INT_MAX/3
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cout<<#x<<":"<<x<<endl
#define debug2(x,y) cout<<#x<<","<<#y":"<<x<<","<<y<<endl
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define MAXN 100001

int main(){
    int N,K;
    int H[MAXN];
    cin>>N>>K;
    rep(i,N) cin>>H[i];

    int sum[MAXN+10] = {};     // sum[i] : [0,i)の0の個数
    int cnt=0;
    for(int i=0;i<=N;i++){
        sum[i] = cnt;
        if(!H[i]) cnt++;
    }

    int ul=0,ur=N+1;
    while(ur-ul>1){
        int mid=(ul+ur)/2;      // 長さmidの1の列を作れるか
        bool f=false;
        for(int i=0;i+mid<=N;i++){
            int zero = sum[i+mid] - sum[i];    // [i,i+mid)に含まれる0の個数
            if(zero<=K){
                f=true;
                break;
            }
        }
        if(f){
            ul = mid;
        }else{
            ur = mid;
        }
    }
    cout << ul << endl;
}

感想

コンテスト中には最初は左か右からK個全ての0を1に帰ればいいかと思ったけど
011000110 (K=3)の時とかに落ちてしまう。

そのあと二分探索を書いたけどWAが出てしまい解けなかった。とても悔しい。
コンテストの後りあん氏に聞いたらWAになってた原因は提出したコードで urの初期値を ur=Nとしていたので連続した1の個数がN個の列を作れる場合に落ちてしまっていた。

教訓 : 境界を求めるような二分探索での上界は必ず答えにならないような値にする必要がある。

自明なことではあるんだけど普通に気がつけなくて悲しい(o_o)