Google Code Jam 2017 Round 3 : A. Googlements

うーんグラフに弱い。
https://code.google.com/codejam/contest/8304486/dashboard

問題

あるL桁の数xを考える。
xの各桁は0～Lのいずれかを取ることができる。

f(x)を以下のように定める。
f(x)の頭からi番目の桁の値は、xの各桁のうちiがいくつの桁で登場するかに一致する。

上記のような数の一種である数Gが与えられる。
fを何度か適用する過程でGを経由するような数Dは何通り考えられるか。

解法

y=f(x)とすると、元の数xが何であれ、yにおける各桁の和はL以下にしかならない。
逆にz=f^-1(x)を考えると、xの各桁について頭からi桁目に関し(i*(その桁の値))の和を取ったときLを超える場合、f(w)=zとなるwが存在しない、すなわちzは初期値でありfを1回も適用しない場合でしか登場しえない。

この事実をもとに数え上げていこう。
まず、数xのうち各桁の和がL以下のものを総当たりし、f(x)=yを求めていこう。
逆にyに対しf^-1(y)の候補が求められる(f(x)=yを満たすxは複数ある)

あとはGを初期値とし、xからf^-1(x)を順次BFSの要領で探索していく。
途中、xの各桁について頭からi桁目に関し(i*(その桁の値))の和がLを超える場合、対応するzの数は組み合わせ計算で求められる。
またf(w)=zとなるwは存在しないのでそれ以上zはBFSで探索しなくてよい。

ll p10[11];
int N;
string S;
map<string,vector<string>> pre[10];

int T;
int fact[10];

string getdecay(string A) {
	int N=A.size();
	string B(N,'0');
	FORR(c,A) if(c!='0') B[c-'1']++;
	return B;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	int ret=0;
	cin>>S;
	
	N=S.size();
	queue<string> Q;
	set<string> did;
	
	Q.push(S);
	did.insert(S);
	while(Q.size()) {
		S=Q.front();
		Q.pop();
		ret++;
		
		x=y=0;
		FOR(i,N) x+=(S[i]-'0');
		FOR(i,N) y+=(i+1)*(S[i]-'0');
		if(y<=N) {
			FORR(e,pre[N][S]) if(did.count(e)==0) {
				did.insert(e);
				Q.push(e);
			}
		}
		else {
			int tot=fact[N];
			int left=N;
			FORR(c,S) tot /= fact[c-'0'], left-=c-'0';
			if(left>=0) ret+=tot/fact[left];
		}
	}
	
	_P("Case #%d: %d\n",_loop,ret);
	
}

void dfs(string S,int D,int T) {
	if(S.size()==D) {
		string T=getdecay(S);
		if(S!=T) pre[D][T].push_back(S);
		return;
	}
	int i;
	for(i=0;T+i<=D;i++) {
		S.push_back((char)('0'+i));
		dfs(S,D,T+i);
		S.pop_back();
	}
}

void init() {
	int f,i,j,k,l,x,y;
	p10[0]=1;
	FOR(i,9) p10[i+1]=p10[i]*10;
	fact[0]=1;
	for(i=1;i<=9;i++) fact[i]=fact[i-1]*i;
	for(i=1;i<=9;i++) dfs("",i,0);
}

まとめ

まぁRound3とはいえ1問目位はね。