Codeforces #206 Div1 E. Lucky Number Representation

気の重いCF206 Div1Dを無理やり突破し、晴れ晴れとE問題に行ける。
この回はDどころかBよりE回答者が多い。
http://codeforces.com/contest/354/problem/E

問題

各桁0,4,7だけで構成される非負整数はluckyであるという。
整数Tが与えられる。Tを6個のlucky数の和で表現せよ。

解法

各桁には0,4,7を6個配置できる。
まず簡単なDPで、これら6個から生成できる和を列挙できる。
さらにこの値から、0,4,7を各桁6個まで並べて生成できる和を列挙する。

後はDFSの要領で、Tの上から3桁ずつ0,4,7の組み合わせを適用していけば良い。
0,4,7を3桁で6個ずつ使うと、最大値で1000の位が4まで繰り上がるので、DFSの際は繰り上がりの可能性を0～4まで5通り考慮すると、DFSによる探索は5^5回程度で済む。

int pat[100][6];
int pat2[5000][6];
int T;
ll N;
int val[7];

bool dfs(ll V,int d) {
	int i;
	if(d>=7) return false;
	if(V==0) {
		while(d<7) val[d++]=0;
		return true;
	}
	FOR(i,5) {
		int v=V%1000+i*1000;
		if(pat2[v][0]==-1 || V<v) continue;
		val[d]=v;
		if(dfs((V-v)/1000,d+1)) return true;
		val[d]=-1;
	}
	return false;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(pat);
	MINUS(pat2);
	FOR(j,7) FOR(k,7) if(j+k<=6) FOR(l,6) {
		if(l<k) pat[j*4+k*7][l]=7;
		else if(l<k+j) pat[j*4+k*7][l]=4;
		else pat[j*4+k*7][l]=0;
	}
	
	FOR(i,50) FOR(j,50) FOR(k,50) if(pat[i][0]>=0&&pat[j][0]>=0&&pat[k][0]>=0) {
		if(pat2[i*100+j*10+k][0]>=0) continue;
		FOR(l,6) pat2[i*100+j*10+k][l]=pat[i][l]*100+pat[j][l]*10+pat[k][l];
	}
	
	cin>>T;
	while(T--) {
		cin>>N;
		MINUS(val);
		if(!dfs(N,0)) _P("-1\n");
		else {
			FOR(l,6) {
				ll v=pat2[val[6]][l]*1000000000000000000LL;
				v+=pat2[val[5]][l]*1000000000000000LL;
				v+=pat2[val[4]][l]*1000000000000LL;
				v+=pat2[val[3]][l]*1000000000LL;
				v+=pat2[val[2]][l]*1000000LL;
				v+=pat2[val[1]][l]*1000LL;
				v+=pat2[val[0]][l];
				_P("%lld ",v);
			}
			_P("\n");
		}
	}
	
}

まとめ

いまいち狙いのわからない問題。
Dがややこしかっただけになおさら。