AtCoder Grand Contest 018 B - Sports Festival

問題

　個のスポーツに対して人がそれぞれ1つだけに参加する。番目の人の参加優先順位がで表されるとき、実施するスポーツを適切に選択して最も多くの人が参加するスポーツの参加人数を最小化せよ。

解法

　全てのスポーツを実施する状況から考える。このとき選択されるのは各行の一番左であり、各スポーツの参加人数がわかる。ここで一番参加人数の多いものを排除するとそこに参加していた人たちは違うスポーツに移ることになる。そこで再計算すればまた各スポーツの参加人数がわかり、また多いものを排除するということを繰り返していけば求まる。これはなので間に合う。

　詳細な証明は解説PDF参照のこと。

反省

　32分44秒でAC。最初はDPで解けるんじゃないかといろいろ状態の持ち方を工夫しようとしていたが上手くいかず、なんとなく全てのスポーツを実施する状況から考えて貪欲に排除していけばいいんじゃないかと適当に実装してサンプル流してみたら合っていたので提出。そのまま通ってしまい驚いた。ちゃんと理屈を考えずにとりあえず投げてしまうひどい解き方だった。

　AGCだと700点問題でもこういう感じのことがあり得るんだなぁ。順位表で解けた人数を見ると点数のわりに多めな気はする。

コード

#include"bits/stdc++.h"
using namespace std;
using ll = long long;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> A(N, vector<ll>(M));
    for (ll i = 0; i < N; i++) {
        for (ll j = 0; j < M; j++) {
            cin >> A[i][j];
            A[i][j]--;
        }
    }

    vector<bool> ok(M, true);
    ll ans = INT_MAX;

    for (ll i = 0; i < M; i++) {
        vector<ll> selected_num(M, 0);
        for (ll j = 0; j < N; j++) {
            for (ll k = 0; k < M; k++) {
                if (ok[A[j][k]]) {
                    selected_num[A[j][k]]++;
                    break;
                }
            }
        }

        ll max_num = 0, max_index = -1;
        for (ll j = 0; j < M; j++) {
            if (selected_num[j] > 0) {
                if (selected_num[j] > max_num) {
                    max_num = selected_num[j];
                    max_index = j;
                }
            }
        }

        ans = min(ans, max_num);

        ok[max_index] = false;
    }

    cout << ans << endl;
}