GCJ 2015 Qual A. Standing Ovation

2015/04/13 (Mon) gcj 累積和

問題

https://code.google.com/codejam/contest/6224486/dashboard

ある人が会場で立ち上がって拍手し始めるのに必要な、 他の拍手している人の最低の人数のことをシャイさという。 会場にはシャイさ $i$ の人が $S_i$ 人いる。 $i=0$ の人だけがはじめから拍手していて、$i=1,2,3, \cdots$ の人たちは、 自分よりシャイさが低い人が拍手し始めるのに連動して拍手し始める。

あなたは、任意のシャイさを持つ友達をサクラとして会場に紛れ込ませることができる。 最終的に全ての人を拍手させたいとき、連れ込む必要がある人数の最小値は？

方針

連れ込む人のシャイさは $0$ にするのがいい。 前から累積和を取って行って、足りなかったらその分だけシャイさ $0$ の人がいたことにして補う。

実装

int solve(int Smax, string S);
int solve_naive(int Smax, string S);
pair<int,string> generator();
bool test(int Smax, string S);

signed main(){
    srand(time(0));
    ios_base::sync_with_stdio(0); cin.tie(0);

    int T;
    cin >> T;
    vector<pair<int,string>> input(T);
    rep(i,T){
        int Smax;
        string s;
        cin >> Smax >> s;
        input[i] = mp(Smax,s);
    }

#ifdef TEST
    vector<int> refrun;
#endif

    {
        vector<int> output(T);
        rep(i,T){
            output[i] = solve(input[i].first, input[i].second);
        }
        rep(i,T){
            cout << "Case #" << i+1 << ": " << output[i] << endl;
        }
#ifdef TEST
        refrun = output;
#endif
    }

#ifdef TEST
    {
        vector<int> output(T);
        rep(i,T){
            output[i] = solve_naive(input[i].first, input[i].second);
            assert(output[i] == refrun[i]);
        }
    }
    {
        rep(i,10000000){
            int Smax;
            string S;
            tie(Smax, S) = generator();
            assert(test(Smax, S));
        }
    }
#endif
}

int solve(int Smax, string S_){
    vector<int> S(Smax+1);
    rep(i,Smax+1) S[i] = S_[i]-'0';
    int cur = S[0];
    int ans = 0;
    for(int i=1;i<=Smax;i++){
        int invite = max(0, i-cur);
        ans += invite;
        cur += S[i] + invite;
    }
    return ans;
}

int solve_naive(int Smax, string S_){
    vector<int> S(Smax+1);
    rep(i,Smax+1) S[i] = S_[i]-'0';
    int ans = 0;
    for(int i=1;i<=Smax;i++){
        int standing = 0;
        for(int j=0; j<i;j++){
            standing += S[j];
        }
        int invite = max(0, i-standing);
        S[0] += invite;
        ans += invite;
    }
    return ans;
}

pair<int,string> generator(){
    int Smax = 10;
    string S(Smax+1,'0');
    rep(i,Smax+1) S[i] = rand()%3 + '0';
    return mp(Smax,S);
}

bool test(int Smax, string S){
    int ref = solve(Smax, S);
    int out = solve_naive(Smax, S);
    return ref == out;
}