Problem 1161 : Verbal Arithmetic

問題概要

日本語なので本文参照。（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1161&lang=jp）

ACM + IBM = ICPC
のような覆面算の答えの総数を求めよ。

• 一つのアルファベットには0〜9の一つの数字が対応する
• 異なるアルファベットには異なる数字が対応する
• 出現するアルファベットの数は10以下
• 一桁の数の場合を除いて、数の先頭の0は許されない

解法

まずはそれぞれのアルファベット毎の係数を求める。
それぞれのアルファベットに対して割り当てる数字を、深さ優先探索で順に決めていく。

全く枝刈りをしない解法では9s弱となりTLE。
正の係数には全て9を入れても足りないor負の係数に全て9を入れても大きい場合に枝刈りをすると6.5s程度で通った。

ソースコード

int n;
char in[12][9];
int m,ans,id[256];
pi co[10];
bool use[10];

void rec(int c,int s)
{
	int big=s,sml=s;
	for(int i=c;i<m;i++)
	{
		if(co[i].first<0)sml+=9*co[i].first;
		else big+=9*co[i].first;
	}
	if(sml>0||big<0)return;
	
	if(c==m)
	{
		ans++; return;
	}
	rep(i,10)if(!use[i]&&!(co[c].second&&i==0))
	{
		use[i]=1;
		rec(c+1,s+co[c].first*i);
		use[i]=0;
	}
}
int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)scanf("%s",in[i]);
		rep(i,256)id[i]=-1;
		rep(i,10)co[i]=mp(0,0),use[i]=0;
		ans=m=0;
		
		rep(i,n)
		{
			int t=i<n-1?1:-1,len=strlen(in[i]);
			for(int j=len-1;j>=0;j--)
			{
				char c=in[i][j];
				if(id[c]<0)id[c]=m++;
				co[id[c]].first+=t;
				if(j==0&&len>1)co[id[c]].second=1;
				t*=10;
			}
		}
		sort(co,co+m,greater<pi>());
		
		rec(0,0);
		printf("%d\n",ans);
	}
	return 0;
}