AOJ 1360: Bringing Order to Disorder

上手いこと探索。
半分全列挙をmap DPで早くしたらオーバーキルみたいな感じになってしまった。上手いこと探索系は苦手なのでしょうがない。

#include<stdio.h>
#include<algorithm>
#include<map>
#include<string.h>
using namespace std;
char in[20];
map<int,int> dpL[8][3][71];
map<int,int> dpR[8][3][71];
long long ret=0;
long long lt[71];
long long rt[71];
int main(){
	scanf("%s",in);
	int n=strlen(in);
	int L=n/2;
	int R=n-L;
	dpL[0][0][0][1]=dpR[0][0][0][1]=1;
	for(int i=0;i<L;i++){
		for(int j=0;j<3;j++){
			for(int l=0;l<10;l++){
				int tj=j;
				if(j==0&&l<in[i]-'0')tj=1;
				else if(j==0&&l>in[i]-'0')tj=2;
				for(int k=0;k<=(10*i);k++){
					for(map<int,int>::iterator it=dpL[i][j][k].begin();it!=dpL[i][j][k].end();it++){
			//			printf("%d %d %d %d: %d %d\n",i,j,k,l,(*it).first,(*it).second);
						if(!dpL[i+1][tj][k+l].count((*it).first*(l+1)))dpL[i+1][tj][k+l][(*it).first*(l+1)]=(*it).second;
						else dpL[i+1][tj][k+l][(*it).first*(l+1)]+=(*it).second;
					}
				}
			}
		}
	}
	for(int i=0;i<R;i++){
		for(int j=0;j<3;j++){
			for(int l=0;l<10;l++){
				int tj=j;
				if(j==0&&l<in[i+L]-'0')tj=1;
				else if(j==0&&l>in[i+L]-'0')tj=2;
				for(int k=0;k<=(10*i);k++){
					for(map<int,int>::iterator it=dpR[i][j][k].begin();it!=dpR[i][j][k].end();it++){
						if(!dpR[i+1][tj][k+l].count((*it).first*(l+1)))dpR[i+1][tj][k+l][(*it).first*(l+1)]=(*it).second;
						else dpR[i+1][tj][k+l][(*it).first*(l+1)]+=(*it).second;
					}
				}
			}
		}
	}
	int S=0;
	long long T=1;
	
	for(int i=0;i<n;i++){
		S+=in[i]-'0';
		T*=in[i]-'0'+1;
	}
	for(int i=0;i<71;i++)for(int j=0;j<3;j++){
		for(map<int,int>::iterator it=dpL[L][j][i].begin();it!=dpL[L][j][i].end();it++)lt[i]+=(*it).second;
		for(map<int,int>::iterator it=dpR[R][j][i].begin();it!=dpR[R][j][i].end();it++)rt[i]+=(*it).second;
		
	}
	for(int i=0;i<71;i++)for(int j=0;j<71;j++){
		if(i+j<S){
			ret+=lt[i]*rt[j];
		//	printf("%d %d\n",lt[i],rt[j]);
		}else if(i+j==S){
			for(int k=0;k<3;k++)for(int l=0;l<3;l++){
				for(map<int,int>::iterator it1=dpL[L][k][i].begin();it1!=dpL[L][k][i].end();it1++)
				for(map<int,int>::iterator it2=dpR[R][l][j].begin();it2!=dpR[R][l][j].end();it2++){
					//printf("%d %d: %d %d %d %d\n",k,l,(*it1).first,(*it1).second,(*it2).first,(*it2).second);
					if((long long)(*it1).first*(*it2).first<T)ret+=(long long)(*it1).second*(*it2).second;
					if((long long)(*it1).first*(*it2).first==T){
						if(k==1||(k==0&&l==1))ret+=(long long)(*it1).second*(*it2).second;
					}
				}
			}
		}
	}
	printf("%lld\n",ret);
}