kohyatohの日記

CodeChef April Cook-Off : The Grand Cook Off の証明 (というか計算方法)

CodeChef | 08:17

終了後も証明ができずにうんうん唸っていたのでそのまとめ。

確率とか場合の数とか苦手...

間違ってたら指摘をお願いします。

1.定式化

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

2.全体の場合の数

n人のブロックで優勝者を決めるには、n-1試合が行われるので、

(nC2)*2 * ((n-1)C2)*2 * ... * (2C2)*2 = n! * (n-1)!

通りの場合がある。

同じように、n人のブロックで決勝進出の2人を決めるには、n! * (n-1)! / 2 通りの場合がある。(n>1)

ただし、ブロックAとブロックBに分けて考える場合、AとBが丸々逆になった場合が重なってしまうので、方便として全体を2倍してn! * (n-1)!通りとする。

3.ブロックAに参加者がk人いて、その得点の合計がa点になる場合の数

n人中k人選んで得点の合計がa点になる組み合わせの数(試合順は無視)をdp[k][a]とする。

これはDPで求められる。

この時、ブロックBには参加者がn-k人いることに注意すると、求める事象の数は、

dp[k][a] * (k! * (k-1)!) * ((n-k)! * (n-k-1)!) * (n-2)C(k-1)

= dp[k][a] * k! * (n-k)! * (n-2)!

(n-2)C(k-1)が係るのは、ブロックAとブロックBの試合順が混ざることがあるから。

ちなみに、sum(dp[k][a] for all(a)) = nCk であることに注意すると、

sum(dp[k][a] * k! * (n-k)! * (n-2)! for all(k, a))

= sum(n! * (n-2)! for all(k))

= n! * (n-1)!

となることが確かめられる。

4.ブロックAに参加者がk人いて、その得点の合計がa点になる確率

個々の事象の起こる確率は、(その事象の起こる場合の数)/(全体の場合の数)で求められる。

なので、

p(k, a)

= (dp[k][a] * k! * (n-k)! * (n-2)!) / (n! * (n-1)!)

= dp[k][a] / nCk / (n-1)

となる。

5.結論

数学難しい。

CodeChef April Cook-Off

参加記, CodeChef | 07:33

結果

A	The Grand Cook Off	AC (02:24)	確率
B	Product of Digits Again	WA/TLE	数学?
C	Internet Media Types	AC (00:44)	やるだけ
D	Frosting Cupcakes	Opened	??
E	A Prime Conjecture	AC (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までとか決め打ちで投げて、WAとTLEを行ったり来たりしていた。

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);
    }
}