TCO2012 round.1A

結果

oo- (+0/-0) 505.34pts 442nd
1436->1481(+45)
Highest更新&&TCO Round1通過！

250

しばらく問題文を正しく読めてなかった。
最大8ターンなのでシミュレーションすればよい。

    vector <string> getWinners(vector <string> players) {
        set<string> ret;
        sort(players.begin(), players.end());

        do{
            map<string, double> m;
            for(int i=0;i<players.size();++i){
                m[players[i]] += pow(0.5, i/2+1);
            }
            
            map<string,double>::iterator it = m.begin();
            string tmps;
            double tmp = -1;
            while(it != m.end()){
                if(tmp < (*it).second){
                    tmp = (*it).second;
                    tmps = (*it).first;
                }
                ++it;
            }

            it = m.begin();
            bool isok = true;
            while(it != m.end()){
                if((*it).second == tmp && (*it).first != tmps){
                    isok = false;
                }
                ++it;
            }
            if(isok){
                ret.insert(tmps);
            }
        }while(next_permutation(players.begin(), players.end()));
        vector<string> res;

        set<string>::iterator it = ret.begin();

        while(it != ret.end()){
            res.push_back((*it));
            ++it;
        }
        return res;
    }

500

あるn(1<=n<=250)に対してa*b=k!(1<=k<=n)なる既約分数a/b(0

2: 1
3: 2
4: 2
5: 4
6: 4
7: 8
8: 8
9: 8
10: 8
11: 16
12: 16
13: 32
14: 32
15: 32
16: 32
17: 64
18: 64
19: 128
20: 128

となり素数ごとに2倍になっていることが解るので実装してみる->sample合う、
最大ケースも一応返るのでsubmit。

あとで解ったのは、互いに素⇔同じ素因数はすべて分子or分母なので
2^(素因数の個数-1)になる。

    long long getCount(int N) {
        //sieve
        bool isprime[251];
        ll table[251];
        memset(isprime, true, sizeof(isprime));

        isprime[0] = false;
        isprime[1] = false;
        for(int i=2;i<251;i++){
            if(isprime[i] == true){
                for(int j=2;i*j<251;j++){
                    isprime[i*j] = false;
                }
            }
        }
        table[0] = 0;
        table[1] = 0;
        table[2] = 1;
        ll add = 1;
        for(int i=3;i<=N;i++){
            if(isprime[i] == true){
                add *= 2;
            }
            table[i] = table[i-1]+add;
        }
        return table[N];

    }

1000

DP？グラフ？TLEする解法しか思いつかなかった。

challenge

sortしないでnext_permutationしてるのを最後に見つけたけど時間切れ。
これを落とせていれば100位ぐらい上がってたのがくやしい…
もっとchallengeにも力を入れていかなければいけない。