Google Code Jam 2014 Round3 - pes

友人の結婚式でワインをたらふく飲んだため、
死にそうになりながらエンジョイ参加しました。

A : Magical, Marvelous Tour

i番目のデバイスが持つコンデンサ数をc[i]とする
要はmax(c[0]+...+c[a-1], c[a]+...+c[b], c[b+1]+...+c[N-1])を最小化する問題
aを決めれば、bは後ろ2つの値が近くなるように決めれば良くて、2分探索できる
N≦10^6なので、O(NlogN)で間に合う

#include <iostream>
#include <cstdio>

using namespace std;

int a[1000000];
long long sum[1000001];

double solveLarge(int N){
    long long get = sum[N];
    for(int i=0;i<N;i++){
        long long chooseA = sum[i];
        if(sum[i+1]-sum[i] > sum[N]-sum[i+1]){
            get = min(get, max(chooseA, sum[i+1]-sum[i]));
        } else {
            int L = i, R = N;
            while(R-L > 1){
                int mid = (L+R)/2;
                if(sum[mid+1]-sum[i] <= sum[N]-sum[mid+1]){
                    L = mid;
                } else {
                    R = mid;
                }
            }
            get = min(get, max(chooseA, max(sum[L+1]-sum[i], sum[N]-sum[L+1])));
            if(L+2 <= N){
                get = min(get, max(chooseA, max(sum[L+2]-sum[i], sum[N]-sum[L+2])));
            }
        }
    }
    return (sum[N]-get)/(double)sum[N];
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N, p, q, r, s; cin >> N >> p >> q >> r >> s;
        sum[0] = 0;
        for(int i=0;i<N;i++){
            a[i] = (i*(long long)p + q)%r + s;
            sum[i+1] = sum[i] + a[i];
        }
        printf("Case #%d: %.10lf\n", test, solveLarge(N));
    }
}

B : Last Hit

各敵についてタワーに何回攻撃させるか決めると、自分が何回攻撃すれば良いか決まる
自分の攻撃回数が少なければ余った分は後に取っておくと考えられる
逆に多ければ、取っておいた攻撃を使うことになる
どっちのターンで始まるか、攻撃の保存回数をキーにDPしてみた

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

using namespace std;

int N;
int G[100];
int H[100];
int P;
int Q;

int solveLarge(){
    int dp[2][2][2001];
    memset(dp, -1, sizeof(dp));
    dp[0][1][0] = 0;
    for(int i=0;i<N;i++){
        int cur = i%2, next = 1-cur;
        memset(dp[next], -1, sizeof(dp[next]));
        for(int j=0;j<2;j++){
            for(int k=0;k<=2000;k++){
                if(dp[cur][j][k] == -1) continue;
                {
                    int add = (H[i]+Q-1)/Q+j-1;
                    dp[next][1][k+add] = max(dp[next][1][k+add], dp[cur][j][k]);
                }
                for(int enemyAttack=0; ;enemyAttack++){
                    if(enemyAttack*Q >= H[i]) break;
                    int myAttack = (H[i]-enemyAttack*Q+P-1)/P;
                    int chance = enemyAttack + j;
                    if(myAttack > chance){
                        if(k < myAttack-chance) continue;
                        dp[next][0][k-(myAttack-chance)] = max(dp[next][0][k-(myAttack-chance)], dp[cur][j][k]+G[i]);
                    } else {
                        dp[next][0][k+chance-myAttack] = max(dp[next][0][k+chance-myAttack], dp[cur][j][k]+G[i]);
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i=0;i<2;i++){
        for(int j=0;j<=2000;j++){
            res = max(res, dp[N%2][i][j]);
        }
    }
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        cin >> P >> Q >> N;
        for(int i=0;i<N;i++) cin >> H[i] >> G[i];
        printf("Case #%d: %d\n", test, solveLarge());
    }
}

C : Crime House

smallはとりあえず全探索しておいた。
largeは0を貪欲に使うのはダメそうで悩んだ。
フローっぽさを感じたけど結局分からなかった。

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

using namespace std;

int bitCount(int t){
    int res = 0;
    for(int i=t;i;i&=i-1) res++;
    return res;
}

int solveSmall(const vector< pair<int,int> >& ev){
    vector<int> id;
    for(int i=0;i<ev.size();i++){
        if(ev[i].second != 0) id.push_back(ev[i].second);
    }
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    static int dp[2][1<<15];
    for(int i=0;i<(1<<15);i++) dp[0][i] = 1;
    for(int e=0;e<ev.size();e++){
        int cur = e%2, next = 1-cur;
        memset(dp[next], 0, sizeof(dp[next]));
        int checkID = -1;
        for(int i=0;i<id.size();i++){
            if(id[i] == ev[e].second) checkID = i;
        }
        for(int i=0;i<(1<<15);i++){
            if(!dp[cur][i]) continue;
            if(checkID == -1){
                for(int j=0;j<15;j++){
                    if(ev[e].first == 0){
                        if(!(i&(1<<j))) dp[next][i|(1<<j)] = 1;
                    } else {
                        if(i&(1<<j)) dp[next][i^(1<<j)] = 1;
                    }
                }
            } else {
                if(ev[e].first == 0){
                    if(!(i&(1<<checkID))) dp[next][i|(1<<checkID)] = 1;
                } else {
                    if(i&(1<<checkID)) dp[next][i^(1<<checkID)] = 1;
                }
            }
        }
    }
    int res = 100;
    for(int i=0;i<(1<<15);i++){
        if(dp[ev.size()%2][i]) res = min(bitCount(i), res);
    }
    return res;
}

int main(){
    int T; cin >> T;
    for(int test=1;test<=T;test++){
        int N; cin >> N;
        vector< pair<int,int> > ev(N);
        for(int i=0;i<N;i++){
            char c; int id; cin >> c >> id;
            if(c == 'E') ev[i] = make_pair(0, id);
            else         ev[i] = make_pair(1, id);
        }
        int res = solveSmall(ev);
        if(res == 100) printf("Case #%d: CRIME TIME\n", test);
        else printf("Case #%d: %d\n", test, res);
    }
}

D : Willow

読んだだけで終わった。

Rank 104: /oo/oo/o-/--/ Score 49, Penalty 2:03:07

C-large解きたかったなと思いましたが、順位的には無難な出来だったと思います。