AtCoder ARC #069 : E - Frequency

F解けなかったけど、実力的に解ける問題はそこそこの時間で解ききったしこんなもんかな。
http://arc069.contest.atcoder.jp/tasks/arc069_c

問題

N要素の数列A[i]が与えられる。

ここから、以下の手順でsum(A)要素の数列Sを作る。

• 以下Aの全要素がゼロになるまで繰り返す。
  1. A中で最大の要素がA[x]であったとする(A[i]が等しい要素が複数ある場合、最小のiをxとして選択する)。その際、Sの末尾にxを加える。
  2. A中で正の値を持つ要素を1つ選択し、デクリメントする。

Sが辞書順最小となるように要素を選択した場合、S中で1～Nはそれぞれ何回登場するか。

解法

Sを辞書順最小にするためには、ステップ1でできるだけ小さな要素xを選択させたい。
そのためには、後ろにあるより大きな数値の要素からデクリメントしていくことになる。
また、逆にA[x]より手前にA[y]≧A[x]となるy＜xがあるなら、A[x]をデクリメントしていけばますますyがSに残ることになるので、xがS中に現れることはない。

となると、Sに現れるのは、A[x]より手前にA[y]≧A[x]となるy＜xがないようなxである。
そのようなxを集めて昇順に並べたものをV[i]とする。

SにV[i]が登場する回数は、A[V[i]]～A[N]がA[V[i-1]]より大きくA[V[i]]以下であるような場合である。(A[V[i]]を超える場合は、V[i+1]が登場してしまう)
この処理は、mapを使って高速に行うことができる。
f(v) := A[i]中要素がvの個数
とすると、V[i]の登場回数はとなる。
また、この処理後V[i-1]より大きな要素A[x]の値はA[V[i-1]]になるので、f(A[i-1]) += f(v)、f(v)=0としてfを更新していくとよい。

int N;
ll A[101010];
vector<int> V;
ll ret[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	map<ll,ll> M;
	FOR(i,N) cin>>A[i], M[A[i]]++;
	V.push_back(0);
	for(i=1;i<N;i++) if(A[V.back()]<A[i]) V.push_back(i);
	for(i=V.size()-2;i>=0;i--) {
		while(M.rbegin()->first>A[V[i]]) {
			auto r=*M.rbegin();
			M.erase(r.first);
			ret[V[i+1]] += (r.first-A[V[i]])*1LL*r.second;
			M[A[V[i]]]+=r.second;
		}
	}
	FORR(r,M) ret[0] += r.first*r.second;
	
	
	FOR(i,N) cout<<ret[i]<<endl;
}

まとめ

本当は図で描くとわかりやすいんだけどね。