AtCoder Grand Contest 018: B - Sports Festival

,

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

大量提出による荒らしがあったらしい。 対策の予定どうこうと言っているけど、不正(不正ではない)っぽい手法で捩じ込むようなACするやつがしにくくなりそうで嬉しくない。

solution

貪欲。全部実施するとして始めて減らしていく。$O(M(N+M))$。

始めは全部実施するとしておく。 その状況が解でないとしたら、そのとき最も多くの参加者がいるスポーツは中止しなければならない。 他のどのスポーツを中止しても中止した以外のスポーツの参加者は増えるため。 またスポーツの中止の順序は影響しないことも重要。 これを繰り返しながら残りひとつだけにし、その過程で最小だったものが解。

厳密な証明は不勉強のため分からない。 matroidとかですっきり示せたりするのだろうか。

implementation

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int main() {
    int n, m; scanf("%d%d", &n, &m);
    auto a = vectors(n, m, int());
    repeat (y, n) {
        repeat (x, m) {
            scanf("%d", &a[y][x]);
            -- a[y][x];
        }
    }
    vector<int> cnt(m);
    repeat (y, n) {
        cnt[a[y][0]] += 1;
    }
    int result = *whole(max_element, cnt);
    int k = m;
    vector<int> ix(n);
    while (true) {
        repeat (x, m) {
            if (cnt[x] >= result) {
                cnt[x] = -1;
                k -= 1;
            }
        }
        if (k == 0) break;
        repeat (y, n) {
            if (cnt[a[y][ix[y]]] == -1) {
                while (cnt[a[y][ix[y]]] == -1) ++ ix[y];
                assert (ix[y] < m);
                cnt[a[y][ix[y]]] += 1;
            }
        }
        setmin(result, *whole(max_element, cnt));
    }
    printf("%d\n", result);
    return 0;
}