Google Code Jam 2021 Round 1C : B. Roaring Years

BもCも方針はすぐ立ったのに、ミスを重ねてたので出てたら危なかった。
https://codingcompetitions.withgoogle.com/codejam/round/00000000004362d7/00000000007c0f01

問題

正整数がroaringであるとは、連続する2つ以上の正整数を(文字列とみなして)連結した形で表現できるものであることを意味する。
今正整数Yが与えられる。Yより大きな最小のroaringな正整数を求めよ。

解法

Yは高々19桁なので、3つ以上の正整数を連結した整数については、先頭の整数は1,000,000以下のものだけ考えればよい。
そこで、これらは最初に全部列挙し、setに入れてしまおう。

各Yに対し、3つ以上の正整数を連結した整数のうち条件を満たす最小値は、上記setを二分探索して求めればよい。
あとは、2つの正整数を連結したケースについて考えよう。
Yの桁数が偶数で2n桁の場合、Y=U*10^n+Vのようにあらわせるなら、解の候補はU*10^n+(U+1)か(U+1)*10^n+(U+2)である。
奇数ので2n+1桁場合、解の候補は10^n+10^(floor(n/2))+1となる。
コーナーケースとして、999910000のように前半と後半で桁数が異なるケースを忘れずに。

ll Y;

int D[1010101];
ll p10[20];
set<ll> S;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>Y;
	Y++;
	ll ret=*S.lower_bound(Y);
	
	int d=0;
	ll a=Y;
	while(a) a/=10,d++;
	
	if(d==19) {
		;
	}
	else if(d%2==1) {
		ret=min(ret,p10[d]+p10[d/2]+1);
		ll a=(p10[d/2]-1)*p10[d/2+1]+p10[d/2];
		if(a>=Y) ret=min(ret,a);
	}
	else {
		ll U=Y/p10[d/2];
		ll V=Y%p10[d/2];
		
		if(U!=p10[d/2]-1) {
			if(V<=U+1) {
				ret=min(ret,U*p10[d/2]+(U+1));
			}
			else if(U!=p10[d/2]-2) {
				ret=min(ret,(U+1)*p10[d/2]+(U+2));
			}
		}
		
	}
	
	_P("Case #%d: %lld\n",_loop,ret);
}

void init() {
	int i;
	
	p10[0]=1;
	FOR(i,19) p10[i+1]=p10[i]*10;
	for(i=1;i<1010000;i++) {
		int x=i;
		while(x) {
			D[i]++;
			x/=10;
		}
	}
	for(i=1;i<1000000;i++) {
		ll a=i;
		ll cur=i+1;
		while(a<=2LL<<60) {
			if(a!=i) S.insert(a);
			assert(D[cur]);
			if((2LL<<60)/p10[D[cur]]<a) break;
			a=a*p10[D[cur]]+cur;
			cur++;
		}
	}
	
	
}

まとめ

自分もコーナーケース見落としてたんだけどね。