AOJ 1161 : Verbal Arithmetic

問題リンク：Verbal Arithmetic | Aizu Online Judge

問題概要：
覆面算を解く数字の組み合わせがどのくらい存在するか？

使用した言語：C＋＋

解法：
半分全列挙した

以下は愚痴
最初は全通り試していたがかなり重かった
サイズが１の文字列はまとめたりどう考えても答えと一致する見込みがないものはカットしていたがダメだった
適当に解いた人のコードをジャッジとしてもってきたらみんな爆速で心がおれました
そこで検索して解いた人のブログで解説をみてみると。。

• >アルファベットは係数でまとめる

まぁまぁそれは

• >半分全列挙する

あ、半分全列挙
なんでその発想がでてこなかったのか
というわけで実装

コード：

#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<bitset>
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
int N;
bool leading[27];
map<char,ll> coefficient;
map<P,int> cntbox;//first -> sum,second -> bit
map<ll,set<int> > cntbex;
int ans;
int S;

ll my_pow(ll a,ll e)
{
  return !e?1:
    (e%2?a*my_pow(a,e-1):my_pow(a*a,e/2));
}

ll getSum(vector<int>& toInt,vector<char>& alpha)
{
  ll sum = 0;
  for(int i=0;i<alpha.size();i++)
    sum += toInt[i]*coefficient[alpha[i]];   
  return sum;
}

void dfs(vector<int>& toInt,vector<char>& alpha,int pos,int used,bool flag)
{

  if(pos >= toInt.size() && !flag)
    {
      ll sum = getSum(toInt,alpha);      
      cntbox[P(sum,used)]++; 
      cntbex[sum].insert(used);
      return;
    }
  else if(pos >= toInt.size() && flag)
    {
      ll sum = getSum(toInt,alpha);
     
      sum = -sum;
 
      set<int> dex = cntbex[sum];
      for(set<int>::iterator it = dex.begin();it != dex.end();it++)
	{
	  int it_bit = (*it);
	  bool ok = true;
	  for(int j=0;j<10;j++)
	    {
	      if(((it_bit >> j) & 1) && ((used >> j) & 1))
		{
		  ok = false;
		  break;
		}
	    }
	  if(ok)
	    ans += cntbox[P(sum,it_bit)]; 	    
	}
      return;
    }

  for(int i=0;i<10;i++)
    {
      if(!i && leading[alpha[pos]-'A'])
	continue;
      if((used>>i) & 1)
	continue;
      toInt[pos] = i;
      dfs(toInt,alpha,pos+1,used|(1<<i),flag);
    }

}

int main()
{
  while(cin >> N,N)
    {//半分全列挙
      ans = 0;
      coefficient.clear();
      cntbox.clear();
      cntbex.clear();
      vector<string> vec(N);
      set<char> al;
      int mex,mex2;
      mex = mex2 = 0;
      rep(i,27)leading[i] = false;
      rep(i,N)
	{
	  cin >> vec[i];
	  if(i != N-1)
	    mex = max(mex,(int)vec[i].size());
	  else
	    mex2 = max(mex2,(int)vec[i].size());
	  if(vec[i].size() != 1)
	    leading[vec[i][0]-'A'] = true;
	  if(i != N-1)
	    rep(j,vec[i].size())
	      coefficient[vec[i][j]] += my_pow(10,vec[i].size()-1-j),al.insert(vec[i][j]);  
	  else
	    rep(j,vec[i].size())
	      coefficient[vec[i][j]] -= my_pow(10,vec[i].size()-1-j),al.insert(vec[i][j]);   
	}

      if(mex2 < mex)
	{
	  cout << 0 << endl;
	  continue;
	}    

      int cn,sz;
      sz = S = al.size();
      cn = 0;
      vector<char> A,B;
      for(set<char>::iterator it = al.begin();it != al.end();it++)
	{
	  if(cn < sz/2)
	    A.push_back((*it));
	  else
	    B.push_back((*it));
	  cn++;
	}
      
      vector<int> toInt(A.size());
      dfs(toInt,A,0,0,false);
      toInt.resize(B.size());
      dfs(toInt,B,0,0,true);
      cout << ans << endl;
    }
  return 0;
}