Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-04-28

CodeChef April Cook-Off

| 07:33

結果

AThe Grand Cook OffAC (02:24)確率
BProduct of Digits AgainWA/TLE数学?
CInternet Media TypesAC (00:44)やるだけ
DFrosting CupcakesOpened??
EA Prime ConjectureAC (00:52)やるだけ


00:45

@nico_shindanninさんのツイートで存在を知り、CodeChefに登録。


01:00 A (WA)

とりあえずAから。

期待値の問題だけど、線形性は使えないタイプ。

それぞれの事象の確率を求めることを考える。


参加者を、ブロックAとブロックBに分けて、ブロックAの優勝者とブロックBの優勝者の得点の差を求める、と置き換えて良い。

ブロックAの優勝者の得点が分かれば、それを全体から引くことでブロックBの優勝者の得点も分かる。

なので、

dp[a] := ブロックAの優勝者の得点がaになる場合の数

とかやればよさそう。

で、これはDPで求められる。

書く...サンプル合わない。


サンプルを紙に書いて確かめたところ、ブロックAの参加者の数によって、行われる試合の場合の数が異なるのを考慮に入れないといけないらしい。

手計算では、(ブロックAの参加者の数)!*(ブロックBの参加者の数)!を掛ければよさそう。(適当)


書き直す...サンプル通った。

提出...WA.

仕方がないので他の問題へ。


01:35 C, E

この辺はやるだけ。


02:00 B (WA/TLE)

BとDを見て、まだBのほうがとっつきやすそうだったのでBを考える。


基数を決めれば、それで与えられた文字列をデコードし、因数分解してそれを生み出す最小の整数を求めることはできる。

そこは書けて、サンプルもあったけど、基数の範囲を決める方法がわからず。

適当に1500までとか決め打ちで投げて、WATLEを行ったり来たりしていた。


03:00 A

もう一度再検討してみる。

直感的にはよさそう。どこが間違えてるのか...

全体の場合の数は結構大きい数になるので、誤差が出ているのかな...と思って、計算の順序とかいじってみたけど相変わらずWA.


終了直前にダメもとでdp部分をlong longからdoubleに変えたら通った!

参加者の数が最大で100人であることをすっかり忘れてlong long溢れしていた。ひどい。


結果

AC/WA/AC/Opened/AC

1 + 0 + 1 + 0 + 1 = 3 16位


残念。でも楽しかったです。


ソース

A

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int n;
double cnt[101][101];

double C(int n, int k) {
    double r = 1.0;
    rep(i, k) r = r*(n-i)/(i+1);
    return r;
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(cnt, 0, sizeof(cnt));
        cnt[0][0] = 1;
        scanf("%d", &n);
        int sum = 0;
        rep(i, n) {
            int a;
            scanf("%d", &a);
            for(int j=i; j>=0; j--) for(int k=100-a; k>=0; k--) {
                cnt[j+1][k+a] += cnt[j][k];
            }
            sum += a;
        }
        LOG(sum);
        double ans = 0;
        for(int i=1; i<n; i++) {
            rep(j, 101) ans += (double)abs(j-(sum-j))*cnt[i][j]/C(n, i);
        }
        printf("%.6f\n", ans/(n-1));
    }
    return 0;
}

C

#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int N, Q;

int main() {
    cin >> N >> Q;
    map<string, string> types;
    rep(i, N) {
        string ex, t;
        cin >> ex >> t;
        types[ex] = t;
    }
    rep(i, Q) {
        string f;
        cin >> f;
        unsigned ix = f.rfind('.');
        if(ix==string::npos) cout << "unknown" << endl;
        else {
            string ex = f.substr(ix+1);
            LOG(ex);
            if(types.find(ex)!=types.end()) cout << types[ex] << endl;
            else cout << "unknown" << endl;
        }
    }
    return 0;
}

E

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int nop[1000000];

int main() {
    vector<int> ps(1, 2);
    for(int i=3; i<1000000; i+=2) if(nop[i]==0) {
        ps.push_back(i);
        if(i<1000) for(int j=i*i; j<1000000; j+=i) nop[j]=1;
    }
    LOG(ps.size());
    rep(i, 5) LOG(ps[i]);
    for(;;) {
        int a;
        scanf("%d", &a);
        if(a==0) return 0;
        bool found = false;
        for(int i=0; ps[i]*ps[i]*ps[i]<a; i++) {
            int b = a-ps[i]*ps[i]*ps[i];
            for(int j=0; ps[j]*ps[j]<b; j++) {
                if(binary_search(ps.begin(), ps.end(), b-ps[j]*ps[j])) {
                    printf("%d %d %d\n", b-ps[j]*ps[j], ps[j], ps[i]);
                    found = true;
                    goto end;
                }
            }
        }
end:
        if(!found) printf("%d %d %d\n", 0, 0, 0);
    }
}