これも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を重ねた。
むしろそれ以外がすんなり行ったのが意外。