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とか大きい場合でも解けそう。