読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

ABC025 C - 双子と○×ゲーム

解くのに3時間かかりました(弱い)

問題

abc025.contest.atcoder.jp

3*3マスの盤に、先手と後手が順に○と×を埋めていく。盤面が埋まったら次のように得点を配分する。横に隣り合うマス、縦に隣り合うマスの計12組のペアにそれぞれ得点が設定されている。各ペアに対し、2つのマスに書かれている文字が同じ場合は先手に、異なる場合は後手にそのペアの得点が入る。先手後手ともに最善を尽くしたとき、それぞれが得られる得点を求めよ。

解法

最後の盤面が決まれば両者の得点が決まる。その1手前は得点を最小化するように、その前は最大化するように…と逆順にたどっていけば両者が最善を尽くしたときの結果がわかる。これを再帰で実装する。

const int INF = 99999999;

int b[2][3];
int c[3][2];
int sm = 0;

//盤面(1:先手, 0:後手, -1:空き)
int a[3][3];

void input() {
    REP(i, 2) {
        REP(j, 3) {
            int x;
            scanf("%d", &x);
            sm += x;
            b[i][j] = x;
        }
    }
    REP(i, 3) {
        REP(j, 2) {
            int x;
            scanf("%d", &x);
            sm += x;
            c[i][j] = x;
        }
    }
}

bool exist(P p, vector<P> vec) {
    REP(i, vec.size()) {
        if (p == vec[i]) {
            return true;
        }
    }
    return false;
}

int result() {
    //先手の得点 - 後手の得点
    int score = 0;

    REP(i, 2) {
        REP(j, 3) {
            score += (a[i][j] == a[i+1][j]) ? b[i][j] : -b[i][j];
        }
    }
    REP(i, 3) {
        REP(j, 2) {
            score += (a[i][j] == a[i][j+1]) ? c[i][j] : -c[i][j];
        }
    }

    return score;
}

int dfs(int cnt) {
    if (cnt == 9) {
        return result();
    }
    if (cnt % 2 == 0) {
        //先手番
        int mx = -INF;
        REP(i, 3) {
            REP(j, 3) {
                if (a[i][j] == -1) {
                    a[i][j] = 1;
                    mx = max(mx, dfs(cnt + 1));
                    a[i][j] = -1;
                }
            }
        }
        return mx;
    }

    //後手番
    int mi = INF;
    REP(i, 3) {
        REP(j, 3) {
            if (a[i][j] == -1) {
                a[i][j] = 0;
                mi = min(mi, dfs(cnt + 1));
                a[i][j] = -1;
            }
        }
    }
    return mi;
}

void solve() {
    REP(i, 3) {
        REP(j, 3) {
            a[i][j] = -1;
        }
    }
    int score = dfs(0);
    int naoko = (sm - score) / 2;
    int choku = sm - naoko;
    printf("%d\n", choku);
    printf("%d\n", naoko);
}

int main() {
    input();
    solve();
    return 0;
}

再帰が少しわかってきた感じ。