Google Code Jam 2015 Round 1B : A. Counter Culture

1Bは1A,1Cより難しい気がする。
https://code.google.com/codejam/contest/8224486/dashboard

問題

0から初めて以下の手順のいずれかを繰り返して数字を増やしていく。

• 1加算する。
• 数字の桁をひっくり返す。その際leading zeroは消える。

Nにするのにかかる最少手数を求めよ。

解法

NがD桁であるとする。
ひっくり返す手順を取っても桁数は増えない。

よってD桁にするにはまず(10^(D-1))-1にして1加算し、10^(D-1)にする。
(10^(D-1))-1はN未満なので、再帰的に求めることができる。

あとは10^(D-1)からNにどうやって持っていくかが問題である。
D桁を上p桁xxxxと下(D-p)桁yyyyと分け、N=xxxyyyyと表現できるとする。

その場合、xxxxを反転した回数だけ加算処理を行った後全体を反転し、(yyyy-1)回加算するとNになる。
よって各pごとにreverse(xxxx)+(yyyy-1)を計算し、その最小値を求めればよい。

map<ll,ll> M;

ll dodo(ll N) {
	if(N<10) return N;
	if(M.count(N)) return M[N];
	if(N%10==0) return M[N]=1+dodo(N-1);
	
	ll x=1;
	while(x*10<=N) x*=10;
	
	ll ret=min(N,dodo(x)+N-x);
	char ns[20];
	sprintf(ns,"%lld",N);
	string NS=ns;
	int L=NS.size();
	
	for(int i=1;i<=L;i++) {
		string pre=NS.substr(0,i);
		string post=NS.substr(i);
		reverse(pre.begin(),pre.end());
		ll tmp=atoll(pre.c_str())-1;
		if(post.size()) tmp+=atoll(post.c_str());
		ret = min(ret,dodo(x)+tmp+1);
	}
	
	return M[N]=ret;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ll N;
	cin>>N;
	
	_P("Case #%d: %lld\n",_loop,dodo(N));
}

まとめ

一見単純ながら結構解答が面倒な問題。