WARush

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

SRM571 Div2 Hard "MagicMoleculeEasy"

問題

マジック原子が個ある。
それぞれのマジック原子はマジックパワーを持っている。
また、マジック原子はグラフみたいに双方向につながってたりする。

ここからマジックパワーの和が最大になるようにマジック原子を個選んだ時の、
マジックパワーの値を返せ。
ただし、つながってペアになっているマジック原子は、
それぞれ最低でも1つは選ばれていなければならない。
また、そのような選び方が出来なければ-1を返せ。
(説明へたですみません・・)

制約

1 <= N <= 50
1 <= K <= 14

本番中一番早かった人の解法

とりあえず1つ辺を選ぶ(頂点A-B)
AとBのどっちかは使わなくちゃだめ
頂点Aを選んだ時のマジックパワー最大値を求める
頂点Bを選んだ時のマジックパワー最大値を求める
2つのうちマジックパワーが大きいほうを返す
これを再帰的にやる。

これだと深さは最大でもKだけやればよくて、
計算量はO(2^K)かな?

ソース
class MagicMoleculeEasy {
public:
    vector<int> P;
    vector<string> B;
    int N;
    int K;

    /*
     * g   残っている辺
     * k   後何個選ぶか
     * sel 選ばれた頂点のインデックス
     * 魔法力の最大値を返す
     */
    int solve( vector<pair<int,int>> g, int k, set<int> sel ){

        // 辺がなければ貪欲に大きい頂点を選んでいく
        if( g.size() == 0 ){
            // 残りの頂点からk個分頂点を選ぶ
            priority_queue<int> r;
            for( int i = 0; i < N; i++ ){
                if( sel.find(i) != sel.end() ) continue;
                    r.push( P[i] );
            }
            int res = 0;
            for( int i = 0; i < k && !r.empty(); i++ ){
                res += r.top(); r.pop();
            }
            return res;
        }
		
        // 作れなければ-1を返す
        if( g.size() >= k * N ){
            return -1;
        }

        int a = g[0].first;
        int b = g[0].second;

        // 頂点aを使う
        vector<pair<int,int>> ga;
        for( int i = 0; i < g.size(); i++ ){
            if( g[i].first == a || g[i].second == a ) continue;
            ga.push_back(g[i]);
        }
        set<int> sa(sel);
        sa.insert(a);
        int resA = solve( ga, k-1, sa );

        // 頂点aを使う
        vector<pair<int,int>> gb;
        for( int i = 0; i < g.size(); i++ ){
            if( g[i].first == b || g[i].second == b ) continue;
                ga.push_back(g[i]);
            }
        set<int> sb(sel);
        sa.insert(b);
        int resB = solve( gb, k-1, sb );

        if( resA == -1 && resB == -1 ){ // どっちの頂点を使っても無理
            return -1;
        }else if( resA == -1 ){
            return resB + P[b];
        }else if( resB == -1 ){
            return resA + P[a];
        }else{
            return max( resA+P[a], resB+P[b] );
        }
    }

    int maxMagicPower(vector <int> magicPower, vector <string> magicBond, int k){
        P = magicPower;
        N = magicPower.size();
        K = k;
        B = magicBond;

        vector<pair<int,int>> g;
        for( int i = 0; i < N - 1; i++ ){
            for( int j = i + 1; j < N; j++ ){
                if( B[i][j] == 'Y' ){
                    g.push_back(make_pair(i,j));
                }
            }
        }
        return solve( g, k, set<int>() );
        
    }
};

g.size() >= k * Nであればもう作れないって所がまだよく分かってない