kmjp's blog

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

Codeforces #241 Div2 D. Population Size

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

問題

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

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

解法

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

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

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

  • -1でない数値が2つ出てくるまで順に見ていく。
    • 2つ出てくる前に終端にたどりついたら未処理のA[i]は正の数を0個か1個しか含まないので、1個の等比数列を生成可能である。
    • -1でない数値が2つ出てきた場合、その2つが含まれる等差数列を考えた際等差が整数か確認する。
    • 等差が整数にならない場合、その2つを同じ等差数列に入れることはできないので、2つ目の整数の手前までを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);
}

まとめ

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