SRM571 Div2 Hard "MagicMoleculeEasy"
問題
マジック原子がN個ある。
それぞれのマジック原子はマジックパワーを持っている。
また、マジック原子はグラフみたいに双方向につながってたりする。
ここからマジックパワーの和が最大になるようにマジック原子をK個選んだ時の、
マジックパワーの値を返せ。
ただし、つながってペアになっているマジック原子は、
それぞれ最低でも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であればもう作れないって所がまだよく分かってない