WARush

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

SRM579 Div2 Hard "MarblePositioning"

問題

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

幾何は人気があるので幾何の問題をだすことにする。あなたはいくつかのサイズがいろいろのビー玉を持っている。あなたにはそれぞれのビー玉の半径を表すradiusが与えられる。

あなたはテーブルに一直線となるよう全てのビー玉を起きたいと思っている。一直線に置くので、その直線での断面図を考えれば、ビー玉を円として、2次元の問題として捉えることができる。もちろん、ビー玉は交差する事ができないので、円として考えたときに、その円が交差する事は無い。あなたは直線状に、好きな順番でビー玉を置く事ができ、与えられたradiusの順番を保つ必要が無い事に留意せよ。

さらに、あなたは可能な限り、ビー玉の底を詰めて置きたい。正確には、ビー玉それぞれの直線と触れている点を考える。最も離れている2つの点の最小の距離を返せ。(これは、もしあなたがこの直線を左から右へと向かうことを想像しているならば、あなたの仕事は左端のビー玉と右端のビー玉の直線に触れているポイントの距離を最小化することである)

制約

2 <= ビー玉の数 <= 8
1 <= ビー玉の半径 <= 10^9


考えた事

幾何好きじゃねーよ!何がloveだよ!!

ビー玉の数が8しかないので順番を全部試しても8!=40000ほどにしかならない。置くビー玉のポイントはどうなるかだが、これは、今まで置いたビー玉全てと以下のような計算を試してみて、その最大値が置くビー玉のポイントとなる。
f:id:Ekaing:20130519123316j:plain

計算量はビー玉の順番を全部試し、n個の各ビー玉の位置を調べるのにn回計算するのでO(n! * n^2)となる。

事後

始めnext_parmutationとかいうの使ったけど、仕様がイマイチわからずバグった
{100, 100, 11, 11, 25}では

{100, 100, 11, 11, 25}
{100, 100, 11, 25, 11}
{100, 100, 25, 11, 11}

の3つしかやってくれないんだがどういうことなんだろう


ソースコード

class MarblePositioning {
public:

    int n;
    vector< int > r;
    bool use[10];
    double pos[10];
    double res;
    
    void rec( int i ){
        for( int j = 0; j < n; j++ ){
            if( use[j] ) continue;
            
            pos[j] = 0.0;
            for( int k = 0; k < n; k++ ){
                if( !use[k] ) continue;
                // jとkでどのくらい離れてなければならないか見る
                double a = r[j], b = r[k];
                double len = sqrt((a + b) * (a + b) - (a - b) * (a - b) );
                // posは最大値をとる
                pos[j] = max( pos[j], len + pos[k] );
            }

            if( i + 1 == n ){
                res = min( res, pos[j] );
            }else{
                use[j] = true;
                rec( i + 1 );
                use[j] = false;
            }
        }            
    }


    double totalWidth(vector <int> _r){
        n = _r.size();
        r = _r;
        res = 1e20;

        memset( use, false, sizeof(use) );
        rec( 0 );
        return res;
    }
};

next_permutationを使う!

コメントで書いてくださったように、next_permutation()は昇順の状態から降順の状態へと移行するメソッドだったようです。(考えてみりゃ、何かしらルールを設けなきゃ、最後の順列なのか判断しようがないですね・・)と、いうわけで、最初にradiusを昇順でソートしてからnext_permutation()使えばよかったのですね。

とはいえ、それでもSystemTestFailedになっていたでしょう。なぜなら、当初はresを10^10で初期化していたからね。ビー玉が全部半径10^9で8個あると、距離は14 * 10^9 = 1.4 * 10^10になり、そしてそのようなTestは存在したのだった・・・


ソースコード

double totalWidth(vector <int> radius){
    int n = radius.size();
    double res = 1e20;

    // next_permutaionのためソート
    sort( radius.begin(), radius.end() );

    // 全ての並びで回す
    do{
        double pos[10] = {0.0};
        for( int i = 1; i < n; i++ ){
            for( int j = 0; j < i; j++ ){
                double a = radius[i], b = radius[j];
                double len = sqrt((a + b) * (a + b) - (a - b) * (a - b) );
                pos[i] = max( pos[i], pos[j] + len );
            }
        }

        res = min( res, pos[n-1] );
    }while( next_permutation( radius.begin(), radius.end() ) );

    return res;
}