AtCoder ARC #057 : C - 2乗根

これもWAを繰り返した。
http://arc057.contest.atcoder.jp/tasks/arc057_c

問題

正整数Nに対し、√Nの各桁を(leading zeroと小数点を除いて)列挙したとき、上位k桁がA[1]A[2]...A[k]となるような最小のNを求めよ。

解法

Aがすべて9の場合だけ別扱いする。
そうでない場合、以下のようにする。

まず入力値をもとに以下の2値を考える。
kが最大1000なのでS,Tは1000桁になるため、多倍長整数を使ってもいいし文字列で保持しても良い。

S := A[1]A[2]...A[k]を10進数で整数と見なしたもの
T := S+1

求める解Nは、S≦√N＜TよりS^2≦N＜T^2の関係となる。
ただ、小数点の位置はどこでも良いので、(S^2)/100^a≦N＜(T^2)/100^aを満たす整数Nが存在するなら、それも候補となる。

よってそのようなaを総当たりしていこう。
S'(a) := S^2を100^aで割り、小数点以下を切り上げた値
T'(a) := T^2を100^aで割り、小数点以下を切り下げた値
S'(a)≦T'(a)ならばS'(a)が解の候補。

Aがすべて9の場合は上記方針ではうまく行かない。
本番中電卓をいじりながら以下のようにした。

• 桁数kが偶数なら、k個9を並べた整数が解(=入力と同じ)
• 桁数kが奇数なら、(k-1)個9を並べたあと81を末尾に加えた整数が解。

string incinc(string A) {
	reverse(A.begin(),A.end());
	FORR(r,A) {
		if(r=='9') r='0';
		else {
			r++;
			break;
		}
	}
	if(A.back()=='0') A += '1';
	reverse(A.begin(),A.end());
	return A;
}

string decdec(string A) {
	for(int i=A.size()-1;i>=0;i--) {
		if(A[i]--!='0') break;
		A[i]='9';
	}
	return A.substr(A[0]=='0');
}

string sq(string a) {
	int tmp[2022]={};
	reverse(ALL(a));
	int i,j;
	FOR(i,a.size()) FOR(j,a.size()) tmp[i+j] += (a[i]-'0')*(a[j]-'0');
	FOR(i,2019) {
		tmp[i+1] += tmp[i]/10;
		tmp[i]%=10;
	}
	string s;
	int fl=0;
	for(i=2019;i>=0;i--) {
		if(tmp[i]) fl=1;
		if(fl) s+='0'+tmp[i];
	}
	return s;
}

string S,T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	
	if(count(ALL(S),'9')==S.size()) {
		if(S.size()%2==0) cout<<S<<endl;
		else cout<<S.substr(1)<<"81"<<endl;
		return;
	}
	
	T=incinc(S);
	string SS=sq(S);
	string TT=sq(T);
	
	if(SS.size()!=TT.size()) SS="0"+SS;
	
	int n0=0,n1=0;
	for(i=SS.size()-1;i>=0;i--) {
		if(SS[i]=='0') n0++;
		else break;
	}
	for(i=TT.size()-1;i>=0;i--) {
		if(TT[i]=='0') n1++;
		else break;
	}
	
	for(i=1;i<=SS.size();i++) if((SS.size()-i)%2==0) {
		string SSS = SS.substr(0,i);
		string TTT = TT.substr(0,i);
		if(n0<SS.size()-i) SSS=incinc(SSS);
		if(n1>=TT.size()-i) TTT=decdec(TTT);
		
		if(SSS[0]=='0') SSS=SSS.substr(1);
		if(SSS.size()<TTT.size() || (SSS.size()==TTT.size() && SSS<=TTT)) {
			cout<<SSS<<endl;
			return;
		}
	}
	
	
	
}

まとめ

9999...の処理で手こずってWAを重ねた。
むしろそれ以外がすんなり行ったのが意外。