Codeforces #241 Div2 D. Population Size

ちょっと苦戦したけど何とかクリア。
http://codeforces.com/contest/416/problem/D

問題

N要素の正の整数列A[i]が与えられる。
ただし、一部の要素は-1が入っている。
これは実際には任意の正の整数で置き換えられることを示す。

この整数列を、正の整数だけで構成されるいくつかの等差数列を結合した形にしたい。
最少何個の等差数列を結合した形になるか。

解法

A[i]の一部が等差数列となる場合、-1ではない整数は最低１個含めることができる。

• 1をすべてその１個と同じ値にすれば、項差0の等差数列ができる。
• 1でない整数が２個以上出てきた場合、初項と項差が求まるので、それらが両方正ならその２つを含む等差数列を構築できる。

上記の考えより、以下の通りA[i]を左から見ていく。

• -1でない数値が２つ出てくるまで順に見ていく。
  • ２つ出てくる前に終端にたどりついたら未処理のA[i]は正の数を0個か1個しか含まないので、１個の等比数列を生成可能である。
  • -1でない数値が２つ出てきた場合、その２つが含まれる等差数列を考えた際等差が整数か確認する。
  • 等差が整数にならない場合、その２つを同じ等差数列に入れることはできないので、２つ目の整数の手前までを１個の等差数列とし、-1でない数値が1個出てきた状態と考えて処理をループする。
  • 等差が整数になる場合、その等差を数列の左側に伸ばし、未処理の-1に正の整数が割り当てられるか調べる。途中で負になってしまう場合は不可。
  • 左側の-1にすべて正の整数を割り当てても矛盾しない場合、今度は逆に右側に等差数列を伸ばせるだけ伸ばしていく。

int N;
ll A[300000];

void solve() {
	int f,i,j,k,l;
	ll x,y;
	int tot=0;
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	int pre=0;
	x=0,y=-1;
	while(x<N) {
		if(A[x]!=-1) {
			if(y==-1) {
				y=x;
				x++;
			}
			else {
				tot++;
				if(abs(A[x]-A[y])%(x-y)==0) {
					ll diff=(A[x]-A[y])/(x-y);
					int ng=0;
					for(i=pre;i<y;i++) {
						ll val=A[y]+diff*(i-y);
						if(val<=0) ng++;
					}
					
					if(!ng) {
						x++;
						while(x<N) {
							y=A[x-1]+diff;
							if(y<=0) break;
							if(A[x]>0 && A[x]!=y) break;
							A[x]=y;
							x++;
						}
					}
				}
				y=-1;
				pre=x;
			}
		}
		else {
			x++;
		}
		
	}
	if(pre<N) tot++;
	_P("%d\n",tot);
}

まとめ

コードで書く方が日本語書くより簡単だな…。