ICPC国内予選2018 D問題 : 全チームによるプレーオフ

問題. 全チームによるプレーオフ

$n$ チームで引き分けのない総当たり戦を行う． $m$ 試合の結果が確定しているときに，残りのすべての試合を行い，すべてのチームの勝利数が等しくなる試合結果（プレーオフ）の組合せ数を求めよ．

制約： $n \in \{3, 5, 7, 9\}$ ，　 $1 < m < n (n - 1) / 2$

解法. 握手補題 + 枝刈り探索

全チームの勝利数が等しくなるとき，各チームの勝利数がいくつになるのかを考えます．各チームを頂点として，チーム $i$ がチーム $j$ に勝つとき， $i$ から $j$ への弧を張ることによって構成される有向グラフ $G = (V, A)$ を考えます．この有向グラフは完全グラフの各辺を向き付けしたグラフで tournament と呼ばれます．各チームの勝利数はその頂点 $v$ の出次数 $\deg^{+}_{G}(v)$ に等しく，弧の総数は $|A| = \frac{n (n - 1)}{2}$ であることから，有向グラフの握手補題，
　 $\sum_{v \in V} \deg^{+}_{G}(v) = |A|$
から，各頂点の勝利数が等しく $c$ とすると，
　 $\sum_{v \in V} \deg^{+}_{G}(v) = nc = |A| = \frac{n (n - 1)}{2}$
より，
　 $c = \frac{n - 1}{2}$
となります．
1チーム目の未確定の試合から勝敗を確定していく全探索を考えます． $i$ チーム目の試合を考えます．このとき， $j < i$ チーム目との試合結果は探索順から決まっています．ここで， $j > i$ チーム目と試合することを考えると， $i$ チームの勝ち数が $\frac{n - 1}{2}$ より少なければ勝つ可能性があり，負け数が $\frac{n - 1}{2}$ より少なければ負ける可能性があります．それ以外の場合はこれ以上試合の勝敗を確定してもプレーオフとなる組合せ数は 0 となるので探索を打ち切ります．
ここで，この枝刈り探索での状態数の上界を求めます． $n$ が大きく， $m$ が小さいとき状態数は増えるので $n = 9, m = 0$ として考えます．1チーム目は8チームと試合を行い，その内 $\frac{n - 1}{2} = 4$ チームに勝つので $\binom{8}{4}$ 通りの状態数があります．2チーム目も8チームと試合を行うのですが，1チーム目との勝敗は確定しています．もし，1チーム目に負けていた場合は残り7試合中4試合勝つ組合せが状態数となるのですが，枝刈りの条件から，7試合中3試合負ける組合せと考えることもできます．このように考えると全状態数の上界は，
　 $\binom{8}{4} \binom{7}{3} \binom{6}{3} \binom{5}{2} \binom{4}{2} \binom{3}{1} \binom{2}{1} = 10,584,000$
となります．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

struct Playoff {
    int n, ub;
    vector<vector<int>> d;

    Playoff(int _n) : n(_n), ub((n - 1) / 2), d(n, vector<int>(n)) {}
    void Input() {
        int m, x, y;
        cin >> m;
        for (int i = 0; i < m; ++i) {
            cin >> x >> y;
            d[x - 1][y - 1] = 2;
            d[y - 1][x - 1] = -2;
        }
    }

    int Solve(int s = 0, int t = 0, int win = 0, int lose = 0) {
        if (s == n - 1 && t == n - 1) return 1;
        if (s == t) return Solve(s, t + 1, win, lose);

        int s2 = s + (t == n - 1), t2 = (t == n - 1 ? 0 : t + 1), res = 0;
        if (d[s][t] != 0) {
            if (0 < d[s][t] && win < ub) {
                if (t2 == 0) res = Solve(s2, t2, 0, 0);
                else res = Solve(s2, t2, win + 1, lose);
            }
            else if (d[s][t] < 0 && lose < ub) {
                if (t2 == 0) res = Solve(s2, t2, 0, 0);
                else res = Solve(s2, t2, win, lose + 1);
            }
        }
        else {
            if (win < ub) {
                d[s][t] = 1; d[t][s] = -1;
                if (t2 == 0) res = Solve(s2, t2, 0, 0);
                else res = Solve(s2, t2, win + 1, lose);
                d[s][t] = d[t][s] = 0;
            }
            if (lose < ub) {
                d[s][t] = -1; d[t][s] = 1;
                if (t2 == 0) res += Solve(s2, t2, 0, 0);
                else res += Solve(s2, t2, win, lose + 1);
                d[s][t] = d[t][s] = 0;
            }
        }
        return res;
    }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    while (cin >> n, n) {
        Playoff p(n);
        p.Input();
        cout << p.Solve() << '\n';
    }

    return 0;
}

まとめ

枝刈り探索の状態数の上界が簡単に計算できるので，直感が正しいかハラハラしながらプログラムを書かなくてよいので幸せです．