全チームによるプレーオフ [ICPC2018 国内予選 D]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/ICPC/Prelim/1627

前提知識

• 枝刈り全探索

解法

https://onlinejudge.u-aizu.ac.jp/solutions/problem/1627/review/3029611/hamayanhamayan/C++14

枝刈り全探索をやる。
今ならやってみるかという感じになるが、本番でこの方針で実装するのは結構きついと思う。
勝敗を決めながら、全探索をしていくが、このまま行くと同点にすることができない場合は枝刈りをする。
枝刈り判定はcheck関数を使う。
「check(y) := チームyが今の決定している勝敗によって同点にすることができるか」
全探索はよくあるdfsをしていけばいい。

int N, M, A[9][9];
//---------------------------------------------------------------------------------------------------
int check(int y) {
    int win = 0, non = 0;
    rep(x, 0, N) {
        if (A[y][x] == 1) win++;
        else if (A[y][x] < 0 and y != x) non++;
    }
    return win <= (N - 1) / 2 and (N - 1) / 2 <= win + non;
}
//---------------------------------------------------------------------------------------------------
int ans = 0;
void dfs(int cu) {
    int x = cu % N;
    int y = cu / N;

    if (cu == N * N) {
        ans++;
        return;
    }

    if (x == y or 0 <= A[y][x]) {
        if (check(y)) dfs(cu + 1);
        return;
    }
    
    A[y][x] = 1; A[x][y] = 0;
    if(check(y)) dfs(cu + 1);

    A[y][x] = 0; A[x][y] = 1;
    if (check(y)) dfs(cu + 1);

    A[y][x] = A[x][y] = -1;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    while (cin >> N) {
        if (N == 0) return;
        cin >> M;
        rep(i, 0, N) rep(j, 0, N) A[i][j] = -1;
        rep(i, 0, M) {
            int a, b; cin >> a >> b;
            a--; b--;
            A[a][b] = 1;
            A[b][a] = 0;
        }

        ans = 0;
        dfs(0);
        printf("%d\n", ans);
    }
}