kmjp's blog

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

Codeforces #394 Div2 D. Dasha and Very Difficult Problem

本番サイトの不調としょうもないWAでグダグダだと思ったけど、終わってみるとそこそこの順位。
http://codeforces.com/contest/761/problem/D

問題

N要素の整数列A[i],B[i]からC[i]=B[i]-A[i]を作る。
A[i]は入力で与えられる。またC[i]は直接値が与えられるわけではないが、N要素中何番目に大きいかが与えられる。
L≦B[i]≦Rの範囲でB[i]を適切に設定したとき、Cが条件を満たすようにできるか。
できるならその一例を示せ。

解法

C[i]の小さい順に値を決めていこう。
今C[x]の値が確定し、次に大きなC[y]の値を決めるものとする。
C[y]≧C[x]+1より、B[y]-A[y]≧C[x]+1なのでB[y]≧C[x]+A[y]+1である。

今値を小さい順に決めていくので、あとはL≦B[y]≦Rのうち条件を満たす最小値を順次B[y]に当てはめていけばよい。

int N,L,R;
int A[101010],B[101010];
pair<int,int> P[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>P[i].first, P[i].second=i;
	
	sort(P,P+N);
	int pre=-1LL<<30;
	FOR(i,N) {
		x=P[i].second;
		int need=pre+1+A[x];
		if(need>R) return _P("-1\n");
		need=max(L,need);
		B[x]=need;
		pre=B[x]-A[x];
	}
	
	FOR(i,N) _P("%d%c",B[i],(i==N-1)?'\n':' ');
	
	
}

まとめ

Div2とはいえ2000ptにしては簡単なような。