TopCoder SRM 580 Div1

結果
o-- +0/-0 151.32 pts
1254 -> 1271
レートは上がったけど、実質敗北

250
n = 50なのでやるだけ。
なぜか出るところ(減るところ)でもカウントしてしまった。
提出した後に気づいた。
どうしてこんなに時間をかけてしまったんだろう。
うなぎをfishとしてしまって悲しい。

class EelAndRabbit {
    public:
        int getmax(vector <int> l, vector <int> t) {
            int ret = 0;
            int N = l.size();
            // vector<ll> head;
            // vector<ll> tail;
            vector<vector<ll> > fish(N,vector<ll>(2));
            for(int i=0;i<N;i++){
                fish[i][0] = t[i];
                fish[i][1] = t[i]+l[i];
            }

            for(int first_head=0;first_head<2;first_head++){
                for(int second_head=0;second_head<2;second_head++){
                    for(int i=0;i<N;i++){
                        ll catched = 0;
                        ll time = fish[i][first_head];
                        for(int j=0;j<N;j++){
                            if(fish[j][0] <= time and time <= fish[j][1]){
                                catched |= (1ll << j);
                            }
                        }
                        for(int j=0;j<N;j++){
                            ll ntime = fish[j][second_head];
                            ll new_catched = catched;
                            for(int k=0;k<N;k++){
                                if(fish[k][0] <= ntime and ntime <= fish[k][1]){
                                    new_catched |= (1ll << k);
                                }
                            }
                            int cnt = 0;
                            for(int j=0;j<N;j++){
                                if(new_catched & (1ll << j)){
                                    cnt++;
                                }
                            }
                            ret = max(ret,cnt);
                        }

                    }
                }
            }
            return ret;

        }
};

おわった後、書き直したのは以下

class EelAndRabbit {
    public:
        int getmax(vector <int> l, vector <int> t) {
            int ret = 0;
            int N = l.size();
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    int cnt = 0;
                    for(int k=0;k<N;k++){
                        int head=t[k],tail=t[k]+l[k];
                        if((head <= t[i] and t[i] <= tail) or
                           (head <= t[j] and t[j] <= tail)){
                            cnt++;
                        }
                    }
                    ret = max(ret,cnt);
                }
            }
            return ret;
        }
};

500
なぜか勘違いしてunion-findしてみたりした。
最小全域木を使うのかと思ったが違うみたいだ。

http://snuke.hatenablog.com/entry/2013/05/26/024648