kmjp's blog

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

Codeforces #293 Div2 E. Arthur and Questions

Dから一転、こちらは解きごたえのある問題。
http://codeforces.com/contest/518/problem/E

問題

N要素の整数列A[i]がある。
ここで、K要素の部分列を列挙したものA[0..(K-1)], A[1..K], A[2..(K+1)], ... , A[(N-K)..(N-1)]を考える。
これらの部分列の総和が、真に単調増加であるようにしたい。

A[i]は値が与えられているものと未定のものがある。
上記条件を満たすようなA[i]のうち、|A[i]|の総和が最小となるものを求めよ。

解法

A[i..(i+K-1)]の和よりA[(i+1)..(i+K)]が大きくなるためには、A[i]<A[i+K]でなければならない。
この考察を元にA[i]の値を決めていく。
A[i]とA[i+K]がともに値が確定しているなら、A[i]<A[i+K]を確認するだけで良い。

A[i]とA[i+pK]が確定しており、A[i+K], A[i+2K], ... , A[i+(p-1)K]が未確定とする。
この場合A[i], A[i+K], A[i+2K], ... , A[i+(p-1)K], A[i+pK]が単調増加でなければならない。
まず前提として、A[i+pK]-A[i]≧p-1でないとA[i+K], A[i+2K], ... , A[i+(p-1)K]を埋めることができない。

それ以外の場合、-p/2,-(p/2-1), .., 0, .., p/2が順にA[i]~A[i+(p-1)K]に埋まるようにするとA[i]が最小となる。
ただし、A[i]>-p/2-1またはA[i+pK]<p/2+1の場合は、その分A[i]~A[i+(p-1)K]にずれた値を入れればよい。

int N,K;
ll A[301000];
int vis[301000];
int ma=1020000000;

void dodo(int L,int R) {
	int num=(R-L)/K;
	if(A[R]-A[L]<num) {
		_P("Incorrect sequence\n");
		exit(0);
	}
	num--;
	if(num>=1) {
		int rl=-num/2,rr=(num-1)/2;
		if(rl<A[L]+1) rl=A[L]+1,rr=rl+(num-1);
		if(rr>A[R]-1) rr=A[R]-1,rl=rr-(num-1);
		for(int i=1;L+i*K<R;i++) A[L+i*K]=rl+i-1;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,K) A[i]=-ma;
	FOR(i,K) A[N+K+i]=ma;
	FOR(i,N) {
		cin>>s;
		if(s=="?") A[i+K]=-1<<30;
		else A[i+K]=atoi(s.c_str());
	}
	N+=2*K;
	FOR(i,N) if(vis[i]==0) {
		vis[i]=1;
		for(j=i+K;j<N;j+=K) {
			if(A[j]!=-1<<30) break;
			vis[j]=1;
		}
		if(j<N) dodo(i,j);
	}
	FOR(i,N-2*K) cout<<A[i+K]<<" ";
	cout<<endl;
}

まとめ

単に条件に合うA[i]の存在判定をするだけならともかく、|A[i]|の最小化という観点が程よく難易度を上げていて面白かった。