WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM580 Div1 Easy & Div2 Medium 「EelAndRabbit」

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12575

ウサギは川でウナギを捕まえたい。現在、川の中で泳いでいる全てのウナギは同じスピードで泳いでいる。ウサギは川辺で全てのウナギが泳いでくるのを待ち構えている。

川にはポイントごとに座標が割り当てられている。この座標は下流に向かって増加していく。
初め、ウサギは原点位置にいて、全てのウナギは0以下の座標にいる。

あなたは2つのlとtというint[]が与えられる。これらは現在のウナギの状態を表している。各ウナギのスピードは1である。i番目のウナギの長さ(体長)はl[i]である。i番目のウナギの頭はt[i]秒時に座標0に達する。よって、T秒時にはi番目のウナギの頭は座標T-t[i]にあり、尻尾はT-t[i]-l[i]にある。

ウサギは自身と同じ座標に(頭から尻尾までのどこかが含まれて)いるウナギしか捕まえる事が出来ないだろう。ウサギは、2回までウナギ捕りを行う事が出来る。各時間において、彼はウナギ捕りを行うかを決め、なるべく多くのウナギを捕まえたいと思っている。(つまり、彼は捕まえる瞬間、目の前にいるウナギのみ捕まえる事ができ、そして2回チャレンジできる)

捕まえられるウナギの最大数を返せ。

制約

1 <= ウナギの数 <= 50
1 <= t[i], l[i] <= 10^9


考えた事

ウナギが移動してるんじゃなくて、ウサギが任意の位置へ移動し、
2回捕まえると考えるとよいな。
でもウナギの位置は10^9・・・どうしよう・・・


ACしてるソースコードをカンニング

ウナギの数は50なので、座標圧縮や


ソースコード

class EelAndRabbit {
public:
    
    int x1[55], x2[55]; // 圧縮後のウナギの頭と尻尾の位置

    // 座標を圧縮し、圧縮後のサイズ(ウナギの位置の最大値+1)を返す
    int compress( const vector<int>& l, const vector<int>& t){
        int n = l.size();
        vector<int> use;
        for( int i = 0; i < n; i++ ){
            for( int j = -1; j <= 1; j++ ){
                use.push_back( t[i] + j );
                use.push_back( l[i] + t[i] + j );
            }
        }

        sort( use.begin(), use.end() );
        use.erase( unique( use.begin(), use.end() ), use.end() );

        for( int i = 0; i < n; i++ ){
            x1[i] = find( use.begin(), use.end(), t[i] ) - use.begin();
            x2[i] = find( use.begin(), use.end(), l[i] + t[i] ) - use.begin();
        }

        return use.size();
    }

    int getmax(vector <int> l, vector <int> t){
        int n = l.size();
        int m = compress( l, t );

        int best = 0;
        // 1回目~
        for( int i = 0; i < m; i++ ){
            int first = 0;
            bool use[55]; memset( use, false, sizeof(use) );

            for( int k = 0; k < n; k++ ){
                if( x1[k] <= i && i <= x2[k] ){
                    use[k] = true;
                    first++;
                }
            }
            // 2回目~
            for( int j = 0; j < m; j++ ){
                int second = 0;
                for( int k = 0; k < n; k++ ){
                    if( use[k] ) continue;
                    if( x1[k] <= j && j <= x2[k] ){
                        second++;
                    }
                }
                best = max( best, first + second );
            }
        }

        return best;
    }
}

無駄無駄ァ!!!

こういうウナギが増えも減りもしないところで何匹取れるか計算するのは意味があるのだろうか?
f:id:Ekaing:20130526205116j:plain

答えは無駄無駄ァ!!!である。DIO様にボコボコにされるのである。

こういうウナギの増減がある部分をウナギ捕りポイントの候補として探索すれば、全てのパターンを網羅したことになり、これで正しい答えを得られる
f:id:Ekaing:20130526205315j:plain


無駄を省いたソースコード

class EelAndRabbit {
public:
    
    int getmax(vector <int> l, vector <int> t){
        int n = l.size();
        
        // 飛び込み候補を取得
        set<int> pos; // 飛び込み候補
        for( int i = 0; i < n; i++ ){
            pos.insert( t[i] );
            pos.insert( t[i] + l[i] );
        }

        int best = 0;
        // 1回目~
        for( set<int>::iterator one = pos.begin(); one != pos.end(); one++ ){
            int first = 0;
            bool cth[55] = {false};
            for( int i = 0; i < n; i++ ){
                if( t[i] <= *one && *one <= t[i] + l[i] ){
                    first++;
                    cth[i] = true;
                }
            }

            // 2回目~
            for( set<int>::iterator two = pos.begin(); two != pos.end(); two++ ){
                int second = 0;
                for( int i = 0; i < n; i++ ){
                    if( !cth[i] && t[i] <= *two && *two <= t[i] + l[i] ){
                        second++;
                    }
                }

                best = max( best, first + second );
            }
        }        

        return best;
    }
}