Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-31

[][] Codeforces Beta Round #65 E. Nuclear Fusion 01:36 はてなブックマーク -  Codeforces Beta Round #65 E. Nuclear Fusion - 練習帳

問題文

 Problem - E - Codeforces

出典回結果

 Codeforces Beta Round #65

要約

 原子がいくつか与えられている。そこから核融合を繰り返し,決められた原子を作れるかどうかを判定し,作れる場合はその作り方を示せ。融合は 2 つの原子を 1 つの原子にする事のみでき,原子番号 Z の原子と原子番号 W の原子から原子番号 Z+W の原子ができる。初めに与えられる原子の個数 n は 1 以上 17 以下で,作るべき原子の個数 k は 1 以上 n 以下。問題に登場する原子の原子番号は 100 以下。

方針

 もし作るべき原子数が 1 つならば,ナップザック問題になる。しかし作る原子それぞれに通常のナップザック問題と同様の解法*1を適用すると,解のうちの一つを適当に求めることになり,例えば次のようなケースで失敗する可能性がある(原子番号で表す)。

[材料の原子]  →  [作る原子]
 1 3 6 9 30  →    4 6 39

39(Y) を作るのに 30(Zn) と 6(F) と 3(Li) を用いると 4(Be) が作れない。

 そこでそれぞれの原子を作り方のパターンを全て考え,深さ優先探索を行う。2^{17} の状態ではそれぞれの原子を用いたかをビットで記録すれば良い。さらに既に探索した状態が現れたらそこで枝刈りしている。

コード例(c++)

 周期表はここから取ってきました:The periodic table of the elements by WebElements

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <cstring>

using namespace std;

vector<int > orig;
vector<int > prod;
vector<vector<int> > comb;
int n;
int memo[1<<17];

string table[101] = {"dummy","H","He","Li","Be","B","C","N","O","F","Ne",
"Na","Mg","Al","Si","P","S","Cl","Ar",
"K","Ca","Sc","Ti","V","Cr","Mn","Fe","Co","Ni","Cu","Zn","Ga","Ge","As","Se","Br","Kr",
"Rb","Sr","Y","Zr","Nb","Mo","Tc","Ru","Rh","Pd","Ag","Cd","In","Sn","Sb","Te","I","Xe",
"Cs","Ba","La","Ce","Pr","Nd","Pm","Sm","Eu","Gd","Tb","Dy","Ho","Er","Tm","Yb","Lu","Hf","Ta","W","Re","Os","Ir","Pt","Au","Hg","Tl","Pb","Bi","Po","At","Rn",
"Fr","Ra","Ac","Th","Pa","U","Np","Pu","Am","Cm","Bk","Cf","Es","Fm"};

bool dfs(int res, vector<int > & ans){  
  if(memo[res] != -1){
    return false;
  }  
  if(res == 0 && ans.size() == prod.size()){
    return true;
  }
  int count = __builtin_popcount(res);
  vector<int > nums;
  for(int i = 0; i < n; i++){
    if((res >> i) & 1 == 1){
      nums.push_back(i);
    } 
  }
  for(size_t j = 0 ; j < comb[ans.size()].size();j++){
    if((res & comb[ans.size()][j]) == comb[ans.size()][j]){
      int next = res ^ comb[ans.size()][j]; 
      ans.push_back(comb[ans.size()][j]);
      if(dfs(next,ans)){
	memo[res] = 1;
	return true;
      }
      ans.pop_back();
    }	
  }
  memo[res] = 1;
  return false;
}

int main(){
  while(cin >> n){
    int k;cin >> k;
    memset(memo, -1, sizeof(memo));
    orig.clear();orig.resize(n);
    prod.clear();prod.resize(k);
    comb.clear();
    for(int i = 0; i < n; i++){
      string s;cin >> s;
      for(int j = 0; j < 101;j++){
	if(table[j] == s){
	  orig[i] = j;
	  break;
	}
      }
    }

    for(int i = 0; i < k ; i++){
      string s;cin >> s;
      for(int j = 0; j < 101;j++){
	if(table[j] == s){
	  prod[i] = j;
	  break;
	}
      }
    }
    sort(orig.begin(), orig.end());
    sort(prod.begin(), prod.end());

    comb.resize(k);
    for(int  i = 0; i < k; i++){
      for(int j = 0; j < (1<<n); j++){
	int total = 0;
	for(int l= 0; l < n; l++){
	  if((j >> l) & 1 == 1){
	    total += orig[l];
	  } 
	}
	if(total == prod[i]){
	  comb[i].push_back(j);
	}
      }
    }

    int before = accumulate(orig.begin(), orig.end(), 0);
    int after = accumulate(orig.begin(), orig.end(), 0);
    vector<int > ans;
    if(before == after && dfs((1<<n)-1, ans) ){
      cout << "YES" <<endl;
      for(size_t i = 0; i < ans.size(); i++){
	string s;
	for(int j = 0; j < n; j++){
	  if((ans[i] >> j) & 1 == 1){
	    s += table[orig[j]];
	    s += '+';
	  }
	}
	s.erase(s.size()-1);
	cout << s << "->" << table[prod[i]] << endl;
      }
    }else{
      cout << "NO" << endl;
    }
  next:;
    cout << endl;
  }
  return 0;
}

分析

 一応通った事は通りましたが,このコードの計算量を評価できていないです。上のコードでは各原子の作り方を前計算で列挙して変数 comb に保存し,それを深さ優先探索を行う時で利用しています。これを前計算せず,探索段階で組み合わせを列挙すると,次のケース (Test #31) で TLE を起こしました。

17 10
He He He He He He He He He He He He He He He He He
He He He He He He He He Li P

 恐らく 1 行目のそれぞれの He を 2 行目のどの He に対応させるかで組み合わせ爆発が起きたのだと思います。しかしそれは上のコードでもおきているはずで,計算量を大幅に減らせるような工夫のようには思えないです。わかる方がいましたら教えてもらえますでしょうか。