れんしゅうちょう。

2012-04-02TopCoder Open 2012 Round1A

■ [TopCoder][TopCoderOpen]TopCoderOpen 2012 Round1A 00:39

889位	180.92pt
250	Accepted	180.92
500	WA	0.0
1000	Opend	0.0
Hack	-

1264→1270(+6)

10ヶ月くらいぶりのTopCoder.

自分のクズっぷりが遺憾なく発揮された結果がこれである.

EllysJuice

問題

まず思い付いたのが, 与えられた名前を出てきた回数とmapにぶちこんで, 出てきた回数で二分探索or線型探索する方法.

勝つ可能性があるかどうかは, 自分が最初に飲む→あとは回数が少ない順に飲むでOK.

C++で書くのが久々で, mapとかどうやって使うんだっけーと思っていたら, playersのサイズが8以下というのを見つけ, next_permutationと普通にシミュレーションすればいいと思い, そのように書いた.

string get(vector<string> &players){
    double a = 1, b = 1;
    map<string, double> memo;
    rep(i, players.size()){
        if(i%2 == 0){
            memo[players[i]] += a/2.0;
            a /= 2.0;
        }else{
            memo[players[i]] += b/2.0;
            b /= 2.0;
        }
    }
    double m = -1;
    string res = "fooo";
    foreach(it, memo){
        if(it->second >= m){
            m = it->second;
            res = it->first;
        }
    }
    int cnt = 0;
    foreach(it, memo){
        if(it->second == m)
            ++cnt;
    }
    if(cnt > 1) return "";
    return res;
}
inline vector <string> EllysJuice::getWinners(vector <string> players){
    vector <string> res;
    sort(players.begin(), players.end());
    do{
        string a = get(players);
        bool f = true;
        rep(i,res.size()) if(res[i] == a) f = false;
        if(f && (a != "")) res.pb(a);
    }while(next_permutation(players.begin(), players.end()));
    sort(res.begin(), res.end());
    return res;
}

getのa,bをintで取るとか色々やらかして, 割とクズい感じであったが, まぁACった.

後で考えてみれば, 1人の時はその人, 2人以上の時は2回以上飲んでいる人を返せばいいのは明らかであった....

EllysFractions

問題

問題文を読んでそのまま思い付いた方針を採った.

ab=n!になるのは, (1<<n!の素因数の種類)程度のパターン数であるから, nまでの素因数分解を適当にやってやればいいか的な方針.</ppp>

よく見るとa/b<1でなければならず, {a,b}に対して分母と分子が一意に決まるので, 1<<(n!の素因数の種類-1)が正解である.

この修正を忘れていたのだが, デバッグ実行していたのが250のままで, サンプルに全部通っていると勘違いし, 更に1LLにしなければならないのを, 大きい数字入力しても通っているので, LLにし忘れてないだろうと思ってそのまま提出してしまった.

後で通したコードはこれ.

inline long long EllysFractions::getCount(int N){
    long long res = 0;
    vector<int> d(300);
    int cnt = 0;
    for(int i=2; i<=N; ++i){
        int k = i;
        for(int j=2; k!=1; ++j){
            if(k%j == 0){
                if(!d[j]) ++cnt;
                ++d[j];
                k /= j;
                --j;
            }
        }
        if(cnt)res += 1LL<<(cnt-1);
    }
    return res;
}