Hatena::Grouptopcoder

れんしゅうちょう。 このページをアンテナに追加 RSSフィード

 | 

2012-04-02TopCoder Open 2012 Round1A

[][]TopCoderOpen 2012 Round1A 00:39

889位180.92pt
250Accepted180.92
500WA0.0
1000Opend0.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;
}

ついでに, 1<<-1がどうなるかは割とアレらしく, i=2を気をつけるべきらしい.

また, cntが増えるのは明らかにiが素数の時なので, そもそも素因数分解までせずともよかった.

この問題に関する僕のクズさは本当に異常である...

EllysLights

問題

とりあえずxorゲーなので, 文字列からlong longにする.

2-SATかとも一瞬思ったが, xorなのでなんか違うっぽい.

蟻本に出てるunion-findのやつかと思ったが, どうすればうまく行くか, 最小に出来るか等思い付かない.

「各電球は高々2つのスイッチにしか繋がっていない」に注目して, てきとーに探索しても割と余裕で行けるのではないかと考え, 実装する.

サンプルが1つだけ合わず, 時間切れ.

条件分岐のネストを間違えていた.

終了後に直して提出するものの, Systemtest合わず.

よく見直してみると, またも1LLにするのを忘れていて, 直しても更に, TLEする.

連結成分で分解して, 各連結成分に対して, 「スイッチを1つ入れる→その他が決まる」みたいな事をやれば良いらしい.

確かにそうだし, 同じような事をどこかでやった事があるような気がする.

成長していないというか, 退化しているような気がする・・・

1Bはもうちょっといい結果が出せるように頑張ろう.

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/Mi_Sawa/20120402
リンク元
 |