Yukicoder043 野球の試合

問題概要

Nチームの総当たり戦の結果が与えられる。まだ試合が行われていない場合もある。チーム0が最高の順位を取るとき、何位になるか。

$N\leqq6$

yukicoder043

解法

未確定の結果が最大15対戦分なので、これは全探索できる。

計算量:$O(2^{N^2})$

ソース

    #include <bits/stdc++.h>
    using namespace std;
    
    using VS = vector<string>;    using LL = long long;
    using PII = pair<int, int>;   using PLL = pair<LL, LL>;
    
    #define RALL(a) (a).rbegin(), (a).rend()
    #define SZ(a) int((a).size())
    #define SORT(c) sort(ALL((c)))
    #define RSORT(c) sort(RALL((c)))
    #define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
    
    int check(VS &t) {
        int N = SZ(t);
        vector<PII>rank(N, PII(0, 0));
        FOR(j, 0, N) {
            rank[j].second = j;
        }
        FOR(j, 0, N) {
            FOR(k, 0, N) {
                if (t[j][k] == 'o')rank[j].first++;
            }
        }
        RSORT(rank);
        int R = 1;
        int point = -1;
        FOR(j, 0, N) {
            if (point == -1) {
                point = rank[j].first;
            }
            else if (point == rank[j].first) {
    
            }
            else {
                R++;
                point = rank[j].first;
            }
            if (rank[j].second == 0)return R;
    
        }
    }
    
    int main() {
        cin.tie(0);
        ios_base::sync_with_stdio(false);
    
        int N; cin >> N;
        VS s(N);
        FOR(i, 0, N) {
            cin >> s[i];
        }
        vector<PII> pos;
        FOR(i, 0, N) {
            FOR(j, i + 1, N) {
                if (s[i][j] == '-') {
                    pos.push_back(PII(i, j));
                }
            }
        }
        int ans = (SZ(pos) ? N : check(s));
    
        FOR(i, 0, 1 << SZ(pos)) {
            VS t = s;
            FOR(j, 0, SZ(pos)) {
                if (i&(1 << j)) {
                    t[pos[j].first][pos[j].second] = 'o';
                    t[pos[j].second][pos[j].first] = 'x';
                }
                else {
                    t[pos[j].first][pos[j].second] = 'x';
                    t[pos[j].second][pos[j].first] = 'o';
                }
            }
            ans = min(ans, check(t));
        }
        cout << ans << "\n";
    
        return 0;
    }