kitayutaのTopCoderの何か

Codeforces Beta Round #81

16:59

結果

Failed 608 - - - +0/-0 Total:608 291st 1553→1675

id:rng_58の部屋から、id:kyuridenamidaとid:hogloidと共に参加した。

ところで、途中からCFにほとんどつながらないようになっていて謎だった。他のサイトにはつながっていたのに。

A Transmigration

やるだけ∧実装楽 なのだが、浮動小数点の掛け算における誤差に気づかずに死亡する。

もちろん自分が知らないのが悪いのだが、えげつない…

また、「k is a real number with exactly two digits after decimal point」という記述を読み飛ばしていなければこの問題に気づいた可能性もあるなぁと思う。

Failedしたコード

//include等省略
int main(){
    int N,M;
    double K;
    cin>>N>>M>>K;
    vector<pair<string,int> > abs;
    string in;
    double a;
    for(int i=0;i<N;i++){
        cin>>in>>a;
        if(a*K>=100) abs.push_back(make_pair(in,a*K));
    }
    int sz=abs.size();
    for(int i=0;i<M;i++){
        cin>>in;
        bool is=true;
        for(int j=0;j<sz;j++){
            if(abs[j].first==in) is=false;
        }
        if(is) abs.push_back(make_pair(in,0));
    }
    sort(ALL(abs));
    cout<<abs.size()<<endl;
    for(int i=0;i<abs.size();i++){
        cout<<abs[i].first<<" "<<abs[i].second<<endl;
    }
}

こんな感じのコードを書くと通る。

//include等省略
int main(){
    int N,M;
    double K;
    cin>>N>>M>>K;
    K+=0.000000001;     //変更点
    vector<pair<string,int> > abs;
    string in;
    double a;
    for(int i=0;i<N;i++){
        cin>>in>>a;
        if(a*K>=100) abs.push_back(make_pair(in,a*K));
    }
    int sz=abs.size();
    for(int i=0;i<M;i++){
        cin>>in;
        bool is=true;
        for(int j=0;j<sz;j++){
            if(abs[j].first==in) is=false;
        }
        if(is) abs.push_back(make_pair(in,0));
    }
    sort(ALL(abs));
    cout<<abs.size()<<endl;
    for(int i=0;i<abs.size();i++){
        cout<<abs[i].first<<" "<<abs[i].second<<endl;
    }
}

B Dark Assembly

(ダーク♂議会 とか言ってる人がいた)

やるだけだけど、実装はそれなりに大変。

「The probability that a player will be able to kill a certain group of senators is equal to A / (A + B), where A is the sum of levels of all player's characters and B is the sum of levels of all senators in this group. 」という問題文の一部を読み間違えていてそれなりに悩んだ。

vector<int> ses;
double solve(vector<int> ks,int dim,int at,int plpower,int sepower,int mi){
    if(at==ks.size()-1){
        ks[at]+=dim*10;
        double kaku=0;
        for(int i=0;i<(1<<ks.size());i++){
            int nu=0;
            for(int j=0;j<ks.size();j++){
                if((i&(1<<j))!=0) nu++;
            }
            double nowk=1;
            int power=0;
            for(int j=0;j<ks.size();j++){
                double now=ks[j];
                if(now>=100) now=100;
                if((i&(1<<j))!=0){
                    nowk*=now/100;
                }else{
                    nowk*=1-(now/100);
                    power+=ses[j];
                }
            }
            if(nu<=mi) nowk*=(double)plpower/(plpower+power);
            kaku+=nowk;
        }
        return kaku;
    }else{
        double ma=0;
        for(int i=0;i<=dim;i++){
            ks[at]+=i*10;
            ma=max(ma,solve(ks,dim-i,at+1,plpower,sepower,mi));
            ks[at]-=i*10;
        }
        return ma;
    }
}
int main(){
    int N,K,A;
    scanf("%d%d%d",&N,&K,&A);
    ses=vector<int>(N);
    vector<int> ks(N);
    double sesum=0;
    for(int i=0;i<N;i++){
        scanf("%d%d",&ses[i],&ks[i]);
        sesum+=ses[i];
    }
    printf("%.8f\n",solve(ks,K,0,A,sesum,N/2));
}

感想・反省

• まれに見る悪問セットではないか？
• でも悪問セットも取れなければいけない