WARush

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

SRM577 Div2 Hard "EllysCoprimesDiv2"

問題

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

エリーは重複していない正の整数のセットを持っていた。
(それはintの配列 numbersとして与えられる)
彼女はそのセットをソートしたときに、
隣り合う2つの数が1より大きい約数を持たないようにするため、
そのセットにいくつかの新たな正の整数を追加する事にした。
(追加しなくてもよい)
新しい数を最小何個追加すればよいかを返せ。

制約

1 <= numbersの要素数 <= 50
1 <= numbers[i] <= 10^6


考えた事

隣り合う2つの数a, bが、
共通の素因数を持っていなければ、
a, bの間に新たに追加しなくてもいいよな。

そうでない場合は・・うーーん・・
ある数sを追加した場合、tに到達するまでに
結局何個追加することになったか・・をメモ化再帰でやってみるか。

メモすれば各数値で1回ずつ計算すればいいから、
計算量は10^6になるはず

実行

めっさ遅い・・

結果が1になったら即returnしてみよう。

実行

ちょっと理由は分からんが、めっちゃ速くなった!

事後

遅い理由はおそらく再帰が深すぎてメモリ食いまくってたんだと思う。
たしかメモリ食うとページングってのが発生しておそくなるよね?


他の人のソースコードを見てみると、
a - bで素因数が共通しないようにするためには、
最悪でも2つの数の追加で大丈夫らしい。

・・・なんでだ?


ソースコード

int memo[100010];

class EllysCoprimesDiv2 {
public:

    // 最大公約数
    int gcd( int a, int b ){
        if( a < b ) swap( a, b );
        if( a % b == 0 ) return b;
        return gcd( b, a % b );
    }

    // s - tにおいて、何個数字を追加しなければならないか
    int dfs( int s, int t ){
        if( memo[s] != -1 ) return memo[s];

        // 共通な素因数がない
        if( gcd( s, t ) == 1 ){
            return memo[s] = 0;
        }

        int res = t - s;
        for( int ns = s + 1; ns < t; ns++ ){
            if( gcd( s, ns ) != 1 ) continue;
            res = min( res, dfs( ns, t ) + 1 );
            if( res == 1 ) return memo[s] = res;
        }
        return memo[s] = res;
    }

    int getCount(vector <int> numbers){
        sort( numbers.begin(), numbers.end() );
        memset( memo, -1, sizeof(memo) );

        int res = 0;
        for( int i = 0; i < numbers.size() - 1; i++ ){
            res += dfs( numbers[i], numbers[i+1] );
        }

        return res;
    }
};