TopCoderOpen 2019 Round4 : Easy ReProduct

Easy落としたのにMedium通してHighest更新してしまった。
https://community.topcoder.com/stat?c=problem_statement&pm=15642&rd=17659

問題

非負整数を入力とする関数f(n)は以下のように定義される。

• nが10未満の場合、f(n)は入力として与えられる配列baseに対しf(n)=base[n]となる。
• nが10以上の時、nを構成する各桁の積をmとするとf(n)=1+f(m)で再帰的に定義される。

整数Kが与えられる。
f(n)=Kとなる最小のnを求めよ。
なお、解は10^18未満であることが保障される。

解法

nが10未満の物は最初に総当たりしてしまおう。

さらに、問題の設定から2桁以上のnを考える場合以下の条件がわかる。

• nで1個でもどこかの桁に0を含む場合f(n)の値は一致するので、0を含むケースはn=10だけ試せばよい。
• nで1を含むケースは考えなくてよい。
• nを構成する数字の数が同じなら、昇順に並べればよい。

よって、2～9を2～18個昇順に並べた数を総当たりすればよい。

ll C[15];

unordered_map<ll,int> memo;
vector<int> B;

class ReProduct {
	public:
	ll hoge(ll cur) {
		if(cur<10) return B[cur];
		if(memo.count(cur)) return memo[cur];
		ll v=1,w=cur;
		while(w) {
			v*=w%10;
			w/=10;
		}
		memo[cur]=hoge(v)+1;
		return memo[cur];
	}
	
	void dfs(int cur,ll sum,ll dig,int d) {
		if(d>18) return;
		if(sum%10==0 && sum!=10) return;
		if(d>1) {
			ll v=hoge(sum)+1;
			if(v<=11) C[v]=min(C[v],dig);
		}
		for(int i=cur;i<=9;i++) dfs(i,sum*i,dig*10+i,d+1);
	}
	
	
	long long minimize(vector <int> base, int goal) {
		int i,j;
		B=base;
		FOR(i,12) C[i]=1LL<<60;
		C[1+base[0]]=min(C[1+base[0]],10LL);
		FOR(i,10) C[base[i]]=min(C[base[i]],(ll)i);
		memo.clear();
		vector<int> V;
		dfs(1,1,0,0);
		
		return C[goal];
	}
}

まとめ

本番は枝刈り頑張りすぎてn=25のケースを見落としてしまった。