Codeforces #295 Div1 D. Shop

これは正答者少な目だけど、自力で解けた。
http://codeforces.com/contest/521/problem/D

問題

初期状態でK個のパラメータA[i]がある。
ここでN個のアイテムがある。各アイテムは種類T[i]・対象パラメータI[i]・値B[i]の３つの要素で構成される。
アイテムは３種類あり、それぞれ以下の効果がある。

• 種類１：A[I[i]]=B[i]にする。
• 種類２：A[I[i]]+=B[i]にする。
• 種類３：A[I[i]]*=B[i]にする。

アイテムは任意の順番で利用できる。
ただし利用できるのは最大M個までである。
全パラメータの積を最大にするには、どの順でアイテムを利用すればよいか。

解法

各パラメータxに関しては、(アイテムの数を無視すれば)以下の順にアイテムを適用するのが良い。

• 種類１のうち最大のB[i]を１回だけ適用する。
• 種類２のうちB[i]が大きい順に適用する。
• 種類３のうちB[i]が大きい順に適用する。

まず種類１・２を考える。
種類２のアイテムをB[i]降順にソートし、種類１がある場合は先頭に最大の(B[i]-A[x])を追加する。
(種類１のアイテムを(B[i]-A[x])増加する種類２のアイテム、と考える)

あとはこれらのアイテムを順に適用したとき、A[i]が何倍になっていくかを考え、その倍率をpriority_queueに突っ込む。(この時倍率はdoubleで計算する)
次に、種類３に相当するものを同様にpriority_queueに突っ込む。

そして最大M個まで、倍率が高い順にpriority_queueから取り出して答える。
その際、倍率が高い順に答えてはだめで、種類１・２・３の順で答える。

int K,N,M;
vector<pair<double,int> > V[101000][3];
int A[101000],T[101000];
vector<pair<double,int> > R;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>N>>M;
	FOR(i,K) cin>>A[i];
	FOR(i,N) {
		cin>>j>>x>>y;
		T[i]=j;
		V[x-1][j-1].push_back(make_pair(y,i));
	}
	FOR(i,K) {
		vector<pair<double,int> > T;
		sort(V[i][0].begin(),V[i][0].end());
		if(V[i][0].size() && V[i][0].back().first>A[i])
			V[i][1].push_back(make_pair(V[i][0].back().first-A[i],V[i][0].back().second));
		sort(V[i][1].begin(),V[i][1].end());
		reverse(V[i][1].begin(),V[i][1].end());
		
		double cur=A[i];
		FOR(j,V[i][1].size()) {
			T.push_back(make_pair((cur+V[i][1][j].first)/cur,V[i][1][j].second));
			cur += V[i][1][j].first;
		}
		ITR(it,T) R.push_back(*it);
		ITR(it,V[i][2]) R.push_back(*it);
	}
	sort(R.begin(),R.end());
	reverse(R.begin(),R.end());
	FOR(i,R.size()) {
		if(i>=M || R[i].first<1) R.resize(i);
	}
	_P("%d\n",R.size());
	FOR(i,R.size()) if(T[R[i].second]==1) _P("%d ",R[i].second+1);
	FOR(i,R.size()) if(T[R[i].second]==2) _P("%d ",R[i].second+1);
	FOR(i,R.size()) if(T[R[i].second]==3) _P("%d ",R[i].second+1);
	_P("\n");
}

まとめ

最初倍率順にpriority_queueに突っ込むのはすぐ思いつけた。
ただ種類１・２・３の順に出力するのを間違えた。