Google Code Jam 2015 Qualification Roundに参加しました

GCJ初参加しました。

結果は A-small, A-large, B-smallで26ptsでした。なんとか予選通過できたようです。

Round1はAとBとCのどれか2つに参加できて、上位1000位に入ればRound2に進めるようです。
進めるかわかりませんが、とりあえず頑張ろうと思います。
訂正：Round1はRound2進出が決定するまでA,B,Cすべてに参加できるようです。
（ご指摘ありがとうございました）

Problem A 「Standing Ovation」

全員がスタンディングオベーションするためには最低何人の友達を呼べばよいかを求める。
何人が立っているのかをカウントしていって、立てない人が出てきたときに必要な人数を追加していくみたいな感じでシミュレートしました。

int main() {
    int T;
    cin >> T;

    vector<int> ans(T,0);
    REP(i,T) {
        int Smax;
        string si;
        cin >> Smax >> si;
        Smax++;

        int sum = si[0] - '0';
        FOR(j,1,Smax) {
            if(j > sum) {
                ans[i]+=(j-sum);
                sum += (j-sum);
            }
            sum += (si[j]-'0');
        }
    }

    REP(i,T) {
        cout << "Case #" << i+1 << ": " << ans[i] << endl;
    }
    return 0;
}

Problem B 「Infinite House of Pancakes」

※Smallしか解けない解法なので参考にならないと思います。

無限人客がいるパンケーキハウスで有限個のパンケーキを食べつくすのに最短でどのくらい時間がかかるのか求める問題。
各時間ではパンケーキを持っている客が全員１個づつパンケーキを食べるか、客のパンケーキを移動させるか選ぶことができる。（移動する場合どの客もパンケーキを食べることができない）

はじめパンケーキの個数で降順にソートして大きい方から半分に分割していたのですが、例えば9個のパンケーキがある場合、5と4に分割するよりも3,3,3に分割するほうが早いことがわかったので何等分するかも考慮して全探索しました。（無駄なことをしている気がするが）

また、パンケーキを同じ個数持っている客が複数人いる場合、その全てについて分割する必要があります。

以上の点を考慮して幅優先探索で全探索っぽいことをしました。(相変わらず名前の付け方が適当だ)

struct hoge{
    vector<int> p;
    int n;
    int sum;
    hoge():n(0),sum(0){}
    hoge(const hoge& h) {
        n = h.n;
        sum = h.sum;
        int s = h.p.size();
        p.reserve(s);
        copy(h.p.begin(),h.p.end(),back_inserter(p));
    }
    void sort_p() {
        sort(ALL(p),greater<int>());
    }
};

int main() {
    int T;
    cin >> T;
    REP(t,T) {
        int D;
        cin >> D;

        hoge sh;
        sh.p.resize(D);
        REP(i,D) {
            cin >> sh.p[i];
            sh.sum += sh.p[i];
        }
        sh.sort_p();

        queue<hoge> q;
        q.push(sh);
        int ans = INF;
        while(!q.empty()) {
            hoge h = q.front(); q.pop();

            if(h.n > ans) continue;
            if(h.sum == 0) {
                ans = min(ans, h.n);
                continue;
            }

            if(h.p[0] > 3) {
                FOR(k,2,10) {
                    if(h.p[0]/k > 0) {
                        hoge nh(h);
                        int s = h.p.size();
                        int s_ = 0;
                        REP(i,s) {
                            if(h.p[0] != h.p[i]) break;
                            int t1 = h.p[0]/k;
                            int t2 = h.p[0] - t1;
                            nh.p[i] = t1;
                            nh.p.PB(t2);
                            s_++;
                        }
                        nh.n += s_;
                        nh.sort_p();
                        q.push(nh);
                    }
                }
            }

            int s = h.p.size();
            REP(i,s) {
                if(h.p[i]>0) {
                    h.p[i]--;
                    h.sum--;
                }
            }
            h.n++;
            h.sort_p();
            q.push(h);
        }
        printf("Case #%d: %d\n",t+1,ans);
    }
    return 0;
}