Codeforces #186 Div2. E. Ilya and Two Numbers

Eはさすがにかなり難しい。
http://codeforces.com/contest/313/problem/E

問題

数Mに対して、0～(M-1)からなるN要素の数列が2つ与えられる。

2つの数列をそれぞれ並べ替え、要素同士を足してmod Mをとって得られる数列を辞書順で最大化せよ。

解法

Mを超えない範囲ではできるだけ(M-1)、(M-2)、…を多く作り、あぶれたものは足すとMを超える組み合わせしかないので、大きい順に足してmod Mをとればよい。

上記手順をもう少し細かくと以下の通り。

まず、それぞれの数列中の値の数をカウントする。
1つ目の数列の(M-1-i)の個数と2つ目の数列のiの個数を比べ、できるだけ(M-1)を作り答えの数列に加える。
2つ目の数列のiの方が多ければスタックに積む。
1つ目の数列の(M-1-i)の方が多ければスタックにある値と合わせて答えの数列に加える。
この時、スタックの値はi未満なので、和はM未満である。
スタックが空になっても1つ目の数列が余るなら、それは別の数列に入れておく。

最後に、あまりの数列とスタックの値を大きい順に合わせて答えの数列に入れる。
これらはMを超えるので、mod Mをとる。
あとは数列を降順ソートして出力する。

ll N,M;
int num[2][100001];
vector<int> res,D;
stack<int> S;

void solve() {
	int f,r,i,j,k,l, x,y,z;
	
	cin>>N>>M;
	FOR(x,N) num[0][GETi()]++;
	FOR(x,N) num[1][M-1-GETi()]++;
	
	for(i=M-1;i>=0;i--) {
		while(num[0][i] && num[1][i]) res.push_back(M-1),num[0][i]--,num[1][i]--;
		while(num[1][i]) S.push(M-1-i),num[1][i]--;
		while(num[0][i] && !S.empty()) res.push_back((i+S.top())%M),num[0][i]--,S.pop();
		while(num[0][i]) D.push_back(i),num[0][i]--;
	}
	
	FOR(i,D.size()) res.push_back((D[i]+S.top())%M),S.pop();
	sort(res.rbegin(),res.rend());
	FOR(i,N) _P("%d ",res[i]);
	_P("\n");
	return;
}

まとめ

なかなか面白い問題。