れんしゅうちょう。

■ [GCJ]Google Code Jam 2012 Round 1A 13:36

1350位	43pt	2:00:03
問題	Small	Large
A	32:07	WA
B	1:50:48 2WA	1:52:03
C	-	-

落ちると思っていなかったA-Largeで落ちてマジ人権無い.

A-Largeが通ってたら985位とかなんかで通過出来ていた.

以下ソースと考え方.

A

問題理解するのに超時間かかった.

Aまでの入力にはミスがあって, これからは常にミスなく入力出来るのね.

back spaceを何回押すか解れば, 式はぱっと立てられるのね.

良く見るとdp的に出来るような式なのね.

あとはdpに書き直すだけ.

void solve(){
    int a, b;
    cin >> a >> b;
    vector<double> ps;
    rep(i, a){
        double x;
        cin >> x;
        ps.pb(x);
    }
    double res = b+2;
    double prob = 1;
    rep(i, a + 1){
        int bs = a - i;
        double tmp = 2.0 * bs + b - a + 1;
        tmp += (1 - prob) * (b + 1);
        res = min(tmp, res);

        prob *= ps[i];
    }
    cout << res << endl;
}

え? これでLargeWAですよ.

おわかりの通り,

    printf("%.6f\n", res);

とかせねばならぬ.マジ人権ない.

なんでsmall通ったし.

B

こっちは問題を理解するのは結構簡単だった.

lv2のやつで行けるのがあるなら優先的に取る.

lv1のやつしか行けないなら, 行ける中で, 一気にlv2に行ける可能性が一番無いようなやつ(つまりlv2で必要なstarがでかいやつ)に行く.

貪欲でやって, 途中で行ける所が無くなればToo Badでおしまい.

void solve(){
    int n;
    cin >> n;
    N = n;
    ls.clear();
    f.clear();
    rep(i,n){
        int a,b;
        cin >> a >> b;
        ls.pb(vector<int>(2));
        f.pb(vector<bool>(2, false));
        ls[i][0] = a;
        ls[i][1] = b;
    }
    int res = 0;
    int star = 0;
    while(star != (N<<1)){
        pair<int, int> nx;
        bool flg = false;
        rep(i, N){
            rep(j, 2){
                if(!f[i][j] && ls[i][j] <= star){
                    if(flg && nx.second){
                    } else if(j){
                        nx = mp(i, j);
                        flg = true;
                    } else if(!flg){
                        nx = mp(i, j);
                        flg = true;
                    } else if(flg && !j && !nx.second && ls[i][1] >= ls[nx.first][1]){
                        nx = mp(i,j);
                        flg = true;
                    }
                }
            }
        }
        if(!flg){
            cout << "Too Bad" << endl;
            return;
        }
        int i = nx.first, j = nx.second;
        f[i][j] = true;
        if(j == 1){
            if(f[i][0]){
                star++;
            }
            else{
                f[i][0] = true;
                star += 2;
            }
        }
        else if(!f[i][1]) star++;
        ++res;
    }
    cout << res << endl;
}

Smallだけでも通そうと思ってDFS書いたら案の定遅くて1TLE,

一気にレベル2に行く所の調節をミスって, 1WA出した.

前置インクリメントと後置インクリメントがあって気持ち悪いけれど, star += 2と見た感じ対応付けたかっただけなので許して下さい.

ツイートする