Google Code Jam Japan 2011 予選

友人たちとノープラン温泉旅行に出かけつつの参戦。
ノープランな中でわずかな時間を見つけて頑張ってみました。

A : カードシャッフル

30分の電車移動が発生したので、おもむろにノートPCを起動して問題を読んだ。

TopCoderで同じような問題見たなぁ…。
- あの時は逆順とか気づかなくて爆死した
- Div2Mediumでも逆順が想定解で出題されてて噴いた思い出

というわけで、さっくり実装したら通った
- 横から友人が実装の様子を見てたのでちょっと緊張した

C : ビット数

電車が目的地に着くにはまだ時間があったので、回答者数を見てCに挑んだ

2^n-1 + α = N に分ければ良くね？と思ったけど、自信がなかったので大人しくDP
- 下の桁から、繰り上がりの有無の2通りについてビット数の最大値を記録

これを通したあたりで電車が目的地に着いてしまったので、一旦切り上げ

B : 最高のコーヒー

温泉に入ったところで1時間ほど休憩室を借り、そこでBをオープン。
- 関係各位には深く御礼申し上げます

時間との戦い！と思ってビビってたけど、後ろから貪欲で良さそうだったので書いた
- 電車の中で書いた時よりも友人がじっくり観察してきて恐怖だった
- 解説(?)しつつ書いた結果、サンプルに対してなぜか負の値を出力して残念だった
ロクに構成を考えずに書いた結果、参照する変数が色んなとこで間違ってた
残念なバグをとったら、何とか通ったので良かった

Rank 66 : /oo/oo/oo/ Score 54, Penalty 3:04:35

外出先でCodeJamなどとやって予選落ちたら笑えると思ってたものの、
保険かけて3問とも出してみたら無事に通過できたっぽいので良かったです。
そして見られながらのプログラミングは結構焦る事が分かりました(´・ω・`)

以下，書いたコード一覧。

A : カードシャッフル

#include <iostream>
#include <cstdio>

using namespace std;

int main(){
    int TEST; cin >> TEST;
    for(int test=1;test<=TEST;test++){
        int M, C, W; cin >> M >> C >> W;
        int A[200], B[200];
        for(int i=0;i<C;i++) cin >> A[C-i-1] >> B[C-i-1];
        int res = W-1;
        for(int i=0;i<C;i++){
            if(res < B[i]) res += A[i]-1;
            else if(res < A[i]+B[i]-1) res -= B[i];
        }
        printf("Case #%d: %d\n", test, res+1);
    }
}

B : 最高のコーヒー

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>

using namespace std;

int main(){
    int TEST; cin >> TEST;
    int N; long long K;
    long long c[100], t[100], s[100];
    for(int test=1;test<=TEST;test++){
        cin >> N >> K;
        vector< pair<long long, pair<long long, long long> > > vp;
        vp.push_back(make_pair(0, make_pair(0, 0)));
        for(int i=0;i<N;i++){
            cin >> c[i] >> t[i] >> s[i];
            vp.push_back(make_pair(t[i], make_pair(c[i], s[i])));
        }
        sort(vp.begin(), vp.end());
        long long res = 0;
        for(int i=N;i>0;i--){
            long long time = vp[i].first-vp[i-1].first;
            vector< pair<long long, long long> > v;
            for(int j=i;j<=N;j++)
                v.push_back(make_pair(vp[j].second.second, j));
            sort(v.begin(), v.end(), greater< pair<long long, long long> >());
            for(int j=0;j<v.size();j++){
                int idx = v[j].second;
                long long vol = min(vp[idx].second.first, time);
                res += vol*vp[idx].second.second;
                vp[idx].second.first -= vol;
                time -= vol;
            }
        }
        printf("Case #%d: %lld\n", test, res);
    }
}

C : ビット数

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
    int TEST; cin >> TEST;
    int dp[2][100];
    for(int test=1;test<=TEST;test++){
        long long N; cin >> N;
        memset(dp, -1, sizeof(dp));
        if(N%2==0) dp[0][0] = 0, dp[1][0] = 2;
        if(N%2==1) dp[0][0] = 1, dp[1][0] = -100;
        N /= 2;
        int idx = 1;
        while(N){
            if(N%2==0){
                dp[0][idx] = dp[0][idx-1];
                dp[1][idx] = max(dp[1][idx-1]+1, dp[0][idx-1]+2);
            }
            if(N%2==1){
                dp[0][idx] = max(dp[0][idx-1]+1, dp[1][idx-1]);
                dp[1][idx] = dp[1][idx-1]+2;
            }
            idx++;
            N /= 2;
        }
        printf("Case #%d: %d\n", test, dp[0][idx-1]);
    }
}