だいぶ遠回りなことをしてしまった。
https://codeforces.com/contest/1081/problem/E
問題
N要素の数列A[1...N]において、偶数番目の要素のみ与えられる。
S(i) := sum(A[1...i])としたとき、S(1)~S(N)がすべて平方数となるようにできるか。
解法
色々な解法が考えられる。
S(2k) := p^2の形で表されるとき、A[2k+2]の値を使ってA[2k+1]を求めよう。
まず平方数の配列を作っておく。
S(2k+1)として(p+1)^2から順に平方数を試していき、S(2k+1)+A[2k+2]も平方数となるものを探していこう。
そうすると尺取り法の要領でO(N+max(A))程度で済む。
int N; ll A[202020]; vector<ll> M; void solve() { int i,j,k,l,r,x,y; string s; FOR(i,6000001) M.push_back(1LL*i*i); cin>>N; ll cur=0; FOR(i,N/2) { cin>>A[i*2+1]; ll nex=cur+1,R=nex; while(nex<=6000000) { while(R<5100000 && M[R]<nex*nex+A[i*2+1]) R++; if(R>5010000) return _P("No\n"); if(M[R]==nex*nex+A[i*2+1]) break; nex++; } if(nex>6000000) return _P("No\n"); A[i*2]=nex*nex-cur*cur; if(A[i*2]>10000000000000LL) return _P("No\n"); cur=R; } cout<<"Yes"<<endl; FOR(i,N) cout<<A[i]<<" "; }
まとめ
なかなか面白い問題ではあるけど、手間取りすぎたな。