Google Code Jam 2013 Round1B - pes

お酒の力を借りて本気出した(?)

A : Osmos

制約を何となくしか見てなくて、N≦10^6 と勘違いする。
DPするだけかと思いきやそれは無理そう(と思い込む)。
削除操作を途中に挟んでも無意味そう。
でかくする→マージ出来ないの削除をシミュレーションして最小値とれば良い？
small通ったのでlargeにも投げたら通った。

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

using namespace std;

int main(){
    int T; cin >> T;
    long long A; int N;
    for(int test=1;test<=T;test++){
        cin >> A >> N;
        vector<int> v;
        for(int i=0;i<N;i++){
            int t; cin >> t;
            v.push_back(t);
        }
        sort(v.begin(), v.end());
        int res = N;
        int cnt = 0;
        if(A > 1){
            for(int i=0;i<N;i++){
                res = min(res, cnt+N-i);
                while(v[i] >= A){
                    A += A-1;
                    cnt++;
                }
                A += v[i];
            }
            res = min(res, cnt);
        }
        printf("Case #%d: %d\n", test, res);
    }
}

B : Falling Diamonds

smallはDPおｋで、largeが式立てないといけない感じか…？と思いながら読んだ。
…ところ、制約を眺めたらlargeがDPで良さそうだったので、書いた。

largeを実行したらセグフォしたのでオワタと思った。
けど、上限の見積もりが適当だったため、配列を倍にしたら実行出来たので投げた。
奇跡的に通った。

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

using namespace std;

double dp[2000][2000];

double solve(int N, int X, int Y){
    int place = (abs(X)+abs(Y))/2;
    int sum = 0;
    for(int i=0;i<place;i++){
        sum += 4*i+1;
        if(sum > N) return 0; 
    }
    if(sum > N) return 0;
    if(sum + 4*place+1 <= N) return 1.0;
    for(int i=0;i<2000;i++)
        for(int j=0;j<2000;j++)
            dp[i][j] = 0;
    dp[0][0] = 1.0;
    for(int i=0;i<=2*place;i++){
        for(int j=0;j<=2*place;j++){
            if(i==2*place&&j==2*place) continue;
            if(i==2*place){
                dp[i][j+1] += dp[i][j];
            }
            else if(j==2*place){
                dp[i+1][j] += dp[i][j];
            }
            else {
                dp[i][j+1] += 0.5*dp[i][j];
                dp[i+1][j] += 0.5*dp[i][j];
            }
        }
    }
    int lest = N-sum;
    double res = 0;
    for(int i=abs(Y)+1;i<=lest;i++){
        if(i > 2*place || lest-i > 2*place) continue;
        res += dp[i][lest-i];
    }
    return res;
}

int main(){
    int T; cin >> T;
    int N, X, Y;
    for(int test=1;test<=T;test++){
        cin >> N >> X >> Y;
        printf("Case #%d: %.8lf\n", test, solve(N, X, Y));
    }
}

C : Garbled Email

辞書のサイズ見てやばそうと思った(小並感)
DPを適当に高速化しておけばsmallくらい通るんじゃね？という気持ちになる。
DPが適当すぎてsmallで2WA。
- 初回提出などINFがreturnされてたほどの体たらく

largeを考えるのが面倒になり、思い出実行して寝ることに決める。
歯みがきして戻ってきたら驚くべきことに実行が終わってた。
せっかくなので思い出サブミットして寝た。
起きたら通ってて驚いた。

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

using namespace std;

int mem[5][4001];

int main(){
    int T; cin >> T;
    vector<string> vs;
    ifstream fin("garbled_email_dictionary.txt");
    string str;
    while(fin >> str) vs.push_back(str);
    for(int test=1;test<=T;test++){
        memset(mem, -1, sizeof(mem));
        mem[4][0] = 0;
        cin >> str;
        for(int i=0;i<str.size();i++){
            for(int j=0;j<vs.size();j++){
                int first = 1000, last = -100;
                int cnt = 0;
                bool ok = true;
                if(i+vs[j].size() > str.size()) continue;
                for(int k=0;k<vs[j].size();k++){
                    if(vs[j][k] != str[i+k]){
                        cnt++;
                        if(last == -100) first = k;
                        else if(k-last < 5){ ok = false; break; }
                        last = k;
                    }
                }
                if(!ok) continue;
                for(int k=0;k<5;k++){
                    if(mem[k][i] == -1) continue;
                    if(first < 4-k) continue;
                    int nm = min(4, last != -100 ? (int)vs[j].size()-1-last : k+(int)vs[j].size());
                    int np = i+vs[j].size();
                    if(mem[nm][np] == -1) mem[nm][np] = mem[k][i] + cnt;
                    else                  mem[nm][np] = min(mem[nm][np], mem[k][i]+cnt);
                }
            }
        }
        int res = 1000000;
        for(int i=0;i<5;i++){
            if(mem[i][str.size()] == -1) continue;
            res = min(res, mem[i][str.size()]);
        }
        printf("Case #%d: %d\n", test, res);
    }
}

Rank 18 : /oo/oo/oo/ Score 100, Penalty 1:30:22

お酒飲んで思考停止してた部分がたまたま良い感じに働いた…んですかね。
何故か過去最高順位でしたが、怖いのでRound2はシラフでやると思います。