yukicoder : No.451 575

あまりきれいな方法ではないけども。
http://yukicoder.me/problems/no/451

問題

N+1要素の数列A[i]があったとする。
ここからN要素の数列B[i]を以下の要領で作る。
(以下数列のindexは1-originとする)

• B[i]=A[i]+A[i+1] (iが奇数)
• B[i]=A[i]-A[i+1] (iが偶数)

Bが与えられたとき、そのようなBを生成できる、正整数のみで構成されたAが存在するか。
存在するならAの例を答えよ。

解法

Aを1要素定めれば残りはすべて決まる。
そこで(0-originで)A[0]を適当に仮置きしてAの値を決めよう。

さて、A[0]を1増加させるとどうなるかを考える。
試してみると、A[0],A[3],A[4],A[7],...,A[4k],A[4k+3],...は1増加し、A[1],A[2],A[5],A[6],...,A[4k+1],A[4k+2],...は1減少する。
そこで、まずA[0],A[3],A[4],A[7],...,A[4k],A[4k+3],...の最小値を求め、それらが1以上になるようA[0]を動かす。
その後、同様にA[1],A[2],A[5],A[6],...,A[4k+1],A[4k+2],...の最小値を求め、それらが1以上になるよう再度A[0]を動かす。

こうして定めたAが正整数のみで構成されるか判定すればよい。

int N;
ll B[101010];
ll A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	A[0]=0;
	FOR(i,N) {
		cin>>B[i];
		if(i%2==0) A[i+1]=B[i]-A[i];
		else A[i+1]=A[i]-B[i];
	}
	
	ll mi=A[0];
	FOR(i,N+1) if(i%4==0 || i%4==3) mi=min(mi,A[i]);
	if(mi<1) {
		FOR(i,N+1) {
			if(i%4==0 || i%4==3) A[i]-=mi-1;
			else A[i]+=mi-1;
			
		}
	}
	mi=A[1];
	FOR(i,N+1) if(i%4==1 || i%4==2) mi=min(mi,A[i]);
	if(mi<1) {
		FOR(i,N+1) {
			if(i%4==0 || i%4==3) A[i]+=mi-1;
			else A[i]-=mi-1;
		}
	}
	FOR(i,N+1) if(A[i]<=0) return _P("-1\n");
	
	
	cout<<N+1<<endl;
	FOR(i,N+1) cout<<A[i]<<endl;
	
}

まとめ

★2.5ぐらいの感触。