れんしゅうちょう。

■ [TopCoder][TopCoderOpen]TopCoderOpen 2012 Round1B 20:18

590位	231.54pt
250	Accepted	231.54
500	Opend	0.0
1000	WA	0.0
Hack	-

1270→1318(+48)

ギリギリ進めた.

1000が明らかに間違っているのに, 誰も撃墜しようとしてこなくて怖かった.

1問ごとにrm *.exeしていたので, 今回は実行するファイル間違えたりしなくて済んだ.

一人明らかに250間違っている人が居たのに, 見逃してしまった辺りがクズい.

今更記事書いてるあたりもクズい.

更に250しか書いてないあたりもクズい.

FoxAndKgram

問題

大体やるだけ.

二度同じ物を使おうとしたりしないように注意する.

長さの最大値が小さいので, arr[長さ]=本数みたいに持ってもいいけれど,

本数が少ないので単純に2重ループにした.

二分探索もせずに, 100から下がっていく等という怠惰さ.

後から気付いたけど, map<int, int> arrにしてarr[-1]=100;とかやっておけば, YangとYinで場合分けする必要がなくなっておいしい.

こういう, オーダー的な制約がかなり甘い問題は, 速いアルゴリズム作るとかよりも, いかに場合分けが出ない, 実装しやすい, バグらせにくい物を書くかを考えた方が良い気がした.

int n;
bool can(vector<int>& len, int k){
    vector<bool> use(n);
    int cnt = 0;
    rep(i, n){
        if(use[i]) continue;
        if(len[i] == k){
            use[i] = true;
            ++cnt;
            continue;
        }
        for(int j=i+1; j<n; ++j){
            if(!use[j] && len[i] + len[j] == k-1){
                use[i] = use[j] = true;
                ++cnt;
                break;
            }
        }
    }
    return cnt >= k;
}
inline int FoxAndKgram::maxK(vector <int> len){
    n = len.size();
    for(int i=100; i>=1; --i){
        if(can(len, i)) return i;
    }
    return 0;
}

ツイートする