Google Code Jam 2013 Round1A - pes

旅行中だったので、11:00-12:30を電車移動にあてて頑張ってみました。

A : Bullseye

電車に乗ってから30分くらい席が空かなかったのでnexusで問題文だけ見てた。
オーバーフローに気をつけて2分探索すれば良かろう…という印象を受ける。
脳内で組んだ式が間違ってたり誤読してたりして、不覚にも実装で詰まった。

#include <iostream>
#include <cstdio>

using namespace std;

long long valid(long long p, long long c, long long n){
    return n*(2*(p+n)-1) <= c;
}

int main(){
    int T; cin >> T;
    long long p, c;
    for(int test=1;test<=T;test++){
        cin >> p >> c;
        long long L = 1, R = 2;
        while(valid(p, c, R)) L *= 2, R *= 2;
        while(R-L>1){
            long long mid = (L+R)/2;
            if(valid(p, c, mid)) L = mid;
            else                 R = mid;
        }
        printf("Case #%d: %lld\n", test, L);
    }
}

B : Manage your Energy

問題文を読み、smallはDPでどうにでもなりそうという感想を持つ。
largeは貪欲にアレをアレしたら良さそう、というふわふわした感じ。

んで、standingsを見てlarge特攻しかない！という気持ちになってしまった。
電車内で書いたのはバグって通らなかった。

方針は、「イベント開始時に残せる最大エネルギー」と「開始後に最低でも残さないといけないエネルギーを持っておくというもの。
報酬がでかいイベントから順に、最大エネルギーと最低エネルギーの差を使い、O(n)かけて前後のイベントの値を変更していけば良いと思った。
全体でO(n^2)。下のコードは後日デバッグしたもの。

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

using namespace std;

long long solveLarge(){
    static int lower[10000], upper[10000], used[10000];
    int E, R, N; cin >> E >> R >> N;
    for(int i=0;i<N;i++){
        lower[i] = 0;
        upper[i] = E;
        used[i] = 0;
    }
    vector< pair<int, int> > vp;
    for(int i=0;i<N;i++){
        int t; cin >> t;
        vp.push_back(make_pair(-t, i));
    }
    sort(vp.begin(), vp.end());
    long long res = 0;
    for(int i=0;i<N;i++){
        int idx = vp[i].second;
        long long t = -vp[i].first;
        res += (upper[idx]-lower[idx])*t;
        used[idx] = 1;
        for(int j=1; ;j++){
            if(idx-j < 0) break;
            if(used[idx-j]) break;
            lower[idx-j] = max((long long)lower[idx-j], upper[idx]-j*(long long)R);
        }
        for(int j=1; ;j++){
            if(idx+j >= N) break;
            if(used[idx+j]) break;
            upper[idx+j] = min((long long)upper[idx+j], lower[idx]+j*(long long)R);
        }
    }
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        printf("Case #%d: %lld\n", test, solveLarge());
    }
}

C : Good Luck

問題読んで(+standings眺めて)Largeやばそう(小並感)と思った。
Smallはやりゃ通るだろ(傲慢)という感じでしたが、Bで詰まったのでやれず。
コードは当時脳内で予定してたのを書いてみたもの。Smallは通った。

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

string solveSmall(int N, int M, int K){
    int m2 = 0, m3 = 0, m5 = 0;
    for(int i=0;i<K;i++){
        int v; cin >> v;
        int t2 = 0, t3 = 0, t5 = 0;
        while(v%2==0) v /= 2, t2++;
        while(v%3==0) v /= 3, t3++;
        while(v%5==0) v /= 5, t5++;
        m2 = max(m2, t2);
        m3 = max(m3, t3);
        m5 = max(m5, t5);
    }
    if(m2==6) return "444";
    if(m2==5) return "442";
    if(m2==4){
        if(m3+m5==0) return "224";
        if(m3) return "344";
        if(m5) return "445";
    }
    if(m2==3){
        if(m3+m5==0) return "222";
        if(m3) return "234";
        if(m5) return "245";
    }
    if(m2==2){
        if(m3+m5<=1){
            if(m3) return "223";
            else   return "225";
        }
        else {
            string res = "4";
            for(int i=0;i<m3;i++) res += "3";
            for(int i=0;i<m5;i++) res += "5";
            return res;
        }
    }
    string res = "";
    for(int i=0;i<m2;i++) res += "2";
    for(int i=0;i<m3;i++) res += "3";
    for(int i=0;i<m5;i++) res += "5";
    while(res.size() < N) res += "2";
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int R, N, M, K; cin >> R >> N >> M >> K;
        printf("Case #%d:\n", test);
        for(int i=0;i<R;i++) cout << solveSmall(N, M, K) << endl;
    }
}

Rank 2144 : /oo/x-/--/ Score 24, Penalty 1:58:39

Round1Bから本気だす(予定)