Codeforces #180 Div1. C. Splitting the Uniqueness

さてC。Codeforcesはほんと構築ゲーが多いな。
http://codeforces.com/contest/297/problem/C

問題

異なる整数値から構成される要素数Nの数列Sが与えられる。
ここで、以下の条件を満たす同じ要素数の数列A、Bを答えよ。

• A[i]、B[i]は非負整数
• S[i] = A[i]+B[i]
• AとBはalmost uniqueである。almost uniqueとは要素の1/3を取り除くと、整数値が異なるようになる。

解法

おそらく色々あるのだろう。
最初Editorialを見て解いたが、すぐに別のアイデアが思い浮かんだのでそちらを紹介。
まず、Sを昇順にソートしておく。

• 最初の1/3はA[i]=0、B[i]=S[i]。
• 次の1/3はA[i]=S[i]、B[i]=0。

ここまでの時点で、Aは0が1/3、あとS[N/3]～S[2N/3-1]が入っている。
Bは0が1/3、あとS[0]～S[N/3-1]が入っている。
すでにAもBも1/3を0が占めているので、残りの1/3の要素をuniqueな値で埋めていく。
Aは1～(S[N/3]-1)の範囲は使っていない。よって、これらを埋める。
BはS[i]からA[i]を引けばよいが、Bは(S[N/3]-1)までの要素しか使っていないため、最小値であるB[2N/3]=S[2N/3]-A[2N/3]>S[2N/3]-(N/3-1)>S[N/3]となる。
よって、B[i]はuniqueになる。

int N;
pair<int,int> S[100001];
int A[100001],B[100001];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	N=GETi();
	FOR(i,N) S[i]=make_pair(GETi(),i);
	sort(S,S+N);
	
	FOR(i,N) {
		if(i<=N/3) {
			A[S[i].second]=0;
			B[S[i].second]=S[i].first;
		}
		else if(i<=2*N/3) {
			B[S[i].second]=0;
			A[S[i].second]=S[i].first;
		}
		else {
			A[S[i].second]=(N-i);
			B[S[i].second]=S[i].first-(N-i);
		}
	}
	
	
	_P("YES\n");
	FOR(i,N) _P("%d ", A[i]);
	_P("\n");
	FOR(i,N) _P("%d ", B[i]);
	_P("\n");
	
	return;
}

まとめ

最初なかなかわからずEditorialを見てしまったが、１回わかると別解も思いつくもんだね。