TopCoder SRM 784 : Div1 Easy Div2 Hard ValueDivision

Hardが度胸試しなだけな気もするけど…。
https://community.topcoder.com/stat?c=problem_statement&pm=16007

問題

N要素の整数列Aが与えられる。
数列中2回以上登場する値を指定し、その値をもつ要素のうち半数(小数点以下切り下げ)の選択した要素をデクリメントできるとする。
この操作を繰り返して得られる数列のうち、辞書順最小のものを求めよ。

解法

デクリメントできるのは一見半数に思えるが、同じ値の指定を繰り返せば、結局1要素以外全部デクリメントできる。
そこで、以下の処理を繰り返そう。

• 2回以上登場する値のうち最大値を求める
• その値を持つ要素のうち、最後のもの以外をデクリメントする

各要素は高々(N-1)回しかデクリメントされないので、あんまり高速化とか考えなくてもO(N^2)で十分間に合う。

class ValueDivision {
	public:
	vector <int> getArray(vector <int> A) {
		int N=A.size();
		
		while(1) {
			map<int,int> M;
			FORR(a,A) M[a]++;
			int ma=0;
			FORR(m,M) if(m.second>1) ma=m.first;
			if(ma<=1) break;
			int cnt=M[ma];
			FORR(a,A) {
				if(a==ma) {
					a--;
					cnt--;
					if(cnt==1) break;
				}
			}
			
		}
		return A;
	}
}

まとめ

Nが10^5とか大きい場合でも解けそう。