Sports Festival [AtCoder Grand Contest 018 B]

http://agc018.contest.atcoder.jp/tasks/agc018_b

解法

http://agc018.contest.atcoder.jp/submissions/1450077

二分探索する。
check(x) := 最も多くの人が参加しているスポーツの参加人数がx人以下にできるか

check関数では貪欲法でx人以下にできるか確かめる。
以下の手続きをする

1. 全ての参加者の最も好きなスポーツの種類別で数を数える
2. その中でx人より大きいスポーツがあれば、それは選択できないので、ng配列に入れておく
3. ng配列がもし空であれば、数えられているスポーツを全て選択することでx人以下にできるのでtrue(1)を返す
4. ng配列に要素があれば、そのスポーツは選択できないので、全ての参加者から消す
5. もし消すことで、選択できるスポーツがなくなってしまった人がいれば、x人以下にはできないので、false(0)を返す
6. 1に戻る

以下の解法では、好きな順でスポーツを管理したりするのにキューを用いて実装した。

int N, M;
int A[303][303];
//---------------------------------------------------------------------------------------------------
int check(int x) {
    vector<queue<int>> vq(N);
    vector<int> used(M, 0);
    rep(y, 0, N) rep(x, 0, M) vq[y].push(A[y][x]);
 
    while(1) {
        map<int, int> m;
        rep(y, 0, N) m[vq[y].front()]++;
        vector<int> ng;
        fore(p, m) if (x < p.second) ng.push_back(p.first);
 
        if (ng.size() == 0) return 1;
 
        fore(j, ng) used[j] = 1;
 
        rep(y, 0, N) {
            while (!vq[y].empty() && used[vq[y].front()]) vq[y].pop();
            if (vq[y].empty()) return 0;
        }
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(y, 0, N) rep(x, 0, M) {
        cin >> A[y][x];
        A[y][x]--;
    }
    
    int ng = 0, ok = N;
    while (ng + 1 != ok) {
        int x = (ng + ok) / 2;
        if (check(x)) ok = x;
        else ng = x;
    }
    cout << ok << endl;
}