読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

yukicoder : No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい

yukicoder

C++PerlPython並に使いやすいtupleが欲しい。
http://yukicoder.me/problems/no/433

問題

N個のチームが大会を行った。
i番のチームはS[i]問の問題を解き、ペナルティはP[i]で、U[i]大学出身である。

以下の順でチームをK個まで選ぶとき、どのチームが選択されるか。

  • 未選抜のチーム中解いた問題数が最大のチーム
  • ↑も同着のチームが複数ある場合、今までに選抜された同じ大学のチーム数が最小のチーム
  • ↑が同着のチームが複数ある場合、そのうちペナルティが最小のチーム

解法

priority_queueで(S[x],-学内順位,-P[x])の大きい順に選択していけば良い。

int N,K;
int S[101010];
int P[101010];
int U[101010];
vector<pair<pair<int,int>,int>> E[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>S[i]>>P[i]>>U[i];
		E[U[i]].push_back({{S[i],-P[i]},i});
	}
	
	priority_queue<pair<pair<int,int>,pair<int,int>>> Q;
	FOR(i,101000) if(E[i].size()) {
		sort(ALL(E[i]));
		reverse(ALL(E[i]));
		FOR(j,E[i].size()) {
			x = E[i][j].second;
			Q.push({{S[x],-j},{-P[x],x}});
		}
	}
	
	while(K--) {
		_P("%d\n",Q.top().second.second);
		Q.pop();
	}
}

まとめ

tupleが使いやすければこんなにpairを並べないのだけど。

広告を非表示にする