kmjp's blog

競技プログラミング参加記です

Avito Cool Challenge 2018 : E. Missing Numbers

だいぶ遠回りなことをしてしまった。
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]<<" ";
	
}

まとめ

なかなか面白い問題ではあるけど、手間取りすぎたな。