Codeforces #268 Div1 C. Hack it!

あまり自信ないけど本番解けた。
http://codeforces.com/contest/468/problem/C

問題

f(x)は、xの各桁の和とする。
Aが与えられるので、となるl,rを答えよ。

解法

yに対してとすると、g(r)≡g(l-1)となるl,rを求める問題となる。

まず、g(r)≧Aとなるrを二分探索で求める。次にg(l-1)≧g(r)-Aとなるlを同様に二分探索で求める。
運悪くg(l-1)＞g(r)-Aとなった場合は、rをインクリメントし、また対応するlを求めていき、いずれg(l-1)==g(r)-Aとなるl,rを待つ。

Editorialには自分の解法も書いてあるけど「なんでこれで時間内にうまくいくかわからん」って書いてあるね。
Editorialにはほかにも色々な解法が書いてあって面白い。

ll A;
ll po[20];

ll num(ll v) {
	ll ret=0;
	int i;
	
	while(v) {
		for(i=18;i>=0;i--) if(v/po[i]) break;
		ll d=v/po[i];
		
		ret+=(d-1)*d/2*po[i];
		if(i>0) ret+=d*i*45*po[i-1];
		v-=po[i]*d;
		ret+=d*(v+1);
	}
	return ret;
}

ll more(ll tar) {
	ll hoge=0;
	for(int i=56;i>=0;i--) if(num(hoge+(1LL<<i))<tar) hoge += 1LL<<i;
	return hoge;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	po[0]=1;
	FOR(i,19) po[i+1]=po[i]*10;
	cin>>A;
	for(ll R=more(A);;R++) {
		ll d=num(R)-A;
		if(d<0) continue;
		ll L=more(d);
		while(num(L)<d) L++;
		if(num(L)==d) {
			_P("%lld %lld\n",L+1,R);
			return;
		}
	}
}

まとめ

自信なかったが本番正答できてよかった。