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]|の最小化という観点が程よく難易度を上げていて面白かった。