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

問題

問題概要

優先順位のつけ方が与えられる。どの順番に選ばえばいいか。

解法

priority_queueで解いた。大学ごとに何人選ばれたかが優先順位をつける要因となるので、はじめの状態でそれぞれの大学が何人ずつ選ばれるかがわからないので、いきなりすべてをqueueに入れても、選ばれた数の部分を途中で変えなければならなくなり、priority_queueを使う意味がなくなってしまう。
そこでまず、やることは、同じ大学ごとにソートする。同じ大学内で優先順位をつけるには、解いた問題数、ミスの順に決まるので、それらと大学の番号をvectorに入れて、ソートする。ただ、今回は解いた問題数が多いほうが優先順位が高くて、ミスが少ないほうが高いので、ミスの回数を正の数のままいれてしまうと、ミスが多いほうが優先順位が高くなってしまうので、マイナスにしてソートすればよい。このようにしてソートすると、大学内での優先順位がつく。これらの0番目の要素は、その大学で0人選ばれた状態で選ばれるチームとなる。よって、何番目に選ばれるかがわかるので、priority_queueに追加できる。
次にpriority_queueでどのように優先順位をつけるかだが、条件より、解いた問題数、その大学が選ばれた数、ミスした回数の順で優先順位がつくので、これらの要素と、チーム番号と大学の数字をいれておけばいい。そして取り出した大学が、1つ選ばれたことになり、その大学から次の候補を入れればよい。ただし入れるときに、1つ多く、選ばれやことになるので、-1して追加している。(-1は、priority_queueを大きい順に優先順位をつけているので、小さい順に優先順位をつけたいところはマイナスにする必要があるため)
1つ使ったら追加するようなコードを本番では書いたが、メモを書いているときに気がついたが、大学ごとにソートした時点でそれぞれのチームがその大学で何番目に選ばれるかがわかるので、そこですべてpriority_queueに突っ込めるやん。

ミス

priority_queueかなーと思って考えてたらできてよかった。tupleを勘違いしていて、実装に手間取った。
題名が面白い。
類題

No.9 モンスターのレベル上げ - yukicoder

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, k;
//univ[i] := i番目の大学が <解いた問題数, -ミス, 大学の番号>
vector<tuple<int, int, int> > univ[100010];

int main(void){
    cin >>  n >> k;
    rep(i, n){
        int s, p, u;
        cin >> s >> p >> u;
        univ[u].push_back(make_tuple(s, -p, i));
    }
    rep(i, 100010){
        if(univ[i].size() != 0){
            //解いた問題数を多い順に、ミスが少ない順にソート
            sort(univ[i].begin(), univ[i].end());
            reverse(univ[i].begin(), univ[i].end());
        }
    }

    //<解いた問題数, i番目の大学が選ばれた数, -ミスした回数, チーム番号,  大学の番号>
    priority_queue<tuple<int, int, int, int, int> > pq;
    //各大学からその大学の中から1番目に選ばれるチームをpriority_queueにいれる
    rep(i, 100010){
        if(univ[i].size() != 0){
            int num, mis, idx;
            tie(num, mis, idx) = univ[i].front();
            univ[i].erase(univ[i].begin(), univ[i].begin() + 1);//使ったチームを削除
            pq.push(make_tuple(num, 0, mis, idx, i));
        }
    }

    vector<int> ans;
    while(!pq.empty()){
        int num, cnt, mis, idx, daigaku;
        tie(num, cnt, mis, idx, daigaku) = pq.top(); pq.pop();
        ans.push_back(idx);//チーム番号を入れる
        int tnum, tmis, tidx;
        if(univ[daigaku].size() != 0){
            tie(tnum, tmis, tidx) = univ[daigaku].front();
            univ[daigaku].erase(univ[daigaku].begin(), univ[daigaku].begin() + 1);
            //いま選ばれた大学の中から次に選ばれるはずのチームを補充
            pq.push(make_tuple(tnum, cnt - 1, tmis, tidx, daigaku));
        }
        if(ans.size() == k) break;
    }
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}

一気に突っ込んだver

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n, k;
//univ[i] := i番目の大学が <解いた問題数, -ミス, 大学の番号>
vector<tuple<int, int, int> > univ[100010];

int main(void){
    cin >>  n >> k;
    rep(i, n){
        int s, p, u;
        cin >> s >> p >> u;
        univ[u].push_back(make_tuple(s, -p, i));
    }
    rep(i, 100010){
        if(univ[i].size() != 0){
            //解いた問題数を多い順に、ミスが少ない順にソート
            sort(univ[i].begin(), univ[i].end());
            reverse(univ[i].begin(), univ[i].end());
        }
    }

    //<解いた問題数, i番目の大学が選ばれた数, -ミスした回数, チーム番号,  大学の番号>
    priority_queue<tuple<int, int, int, int, int> > pq;
    //各大学からその大学の中から1番目に選ばれるチームをpriority_queueにいれる
    rep(i, 100010){
        if(univ[i].size() != 0){
            // j がその大学で何番目にえばられるかを示している。
            for (int j = 0; j< univ[i].size(); ++j){
                int num, mis, idx;
                tie(num, mis, idx) = univ[i][j];
                pq.push(make_tuple(num, -j, mis, idx, i));
            }
        }
    }

    vector<int> ans;
    while(!pq.empty()){
        int num, cnt, mis, idx, daigaku;
        tie(num, cnt, mis, idx, daigaku) = pq.top(); pq.pop();
        ans.push_back(idx);//チーム番号を入れる
        int tnum, tmis, tidx;
        if(ans.size() == k) break;
    }
    rep(i, ans.size()){
        printf("%d\n", ans[i]);
    }
    return 0;
}