AtCoder题解｜ABC 319 C - False Hope

题目信息 📚

【题目描述】

There is a $3 \times 3$ grid with numbers between $1$ and $9$, inclusive, written in each square. The square at the $i$-th row from the top and $j$-th column from the left $(1 \leq i \leq 3, 1 \leq j \leq 3)$ contains the number $c_{i, j}$.

The same number may be written in different squares, but not in three consecutive cells vertically, horizontally, or diagonally. More precisely, it is guaranteed that $c_{i, j}$ satisfies all of the following conditions:

$c_{i, 1} = c_{i, 2} = c_{i, 3}$ does not hold for any $1 \leq i \leq 3$.
$c_{1, j} = c_{2, j} = c_{3, j}$ does not hold for any $1 \leq j \leq 3$.
$c_{1, 1} = c_{2, 2} = c_{3, 3}$ does not hold.
$c_{3, 1} = c_{2, 2} = c_{1, 3}$ does not hold.

Takahashi will see the numbers written in each cell in random order. He will get disappointed when there is a line (vertical, horizontal, or diagonal) that satisfies the following condition:

The first two squares he sees contain the same number, but the last square contains a different number.

Find the probability that Takahashi sees the numbers in all the squares without getting disappointed.

【输入】

The input is given from Standard Input in the following format:

$c_{1,1}$ $c_{1,2}$ $c_{1,3}$

$c_{2,1}$ $c_{2,2}$ $c_{2,3}$

$c_{3,1}$ $c_{3,2}$ $c_{3,3}$

【输出】

Print one line containing the probability that Takahashi sees the numbers in all the squares without getting disappointed. Your answer will be considered correct if the absolute error from the true value is at most $10^{-8}$.

【数据范围】

$c_{i,j} \in {1, 2, 3, 4, 5, 6, 7, 8, 9}$ $(1 \leq i \leq 3, 1 \leq j \leq 3)$.
$c_{i,1} = c_{i,2} = c_{i,3}$ does not hold for any $1 \leq i \leq 3$.
$c_{1,j} = c_{2,j} = c_{3,j}$ does not hold for any $1 \leq j \leq 3$.
$c_{1,1} = c_{2,2} = c_{3,3}$ does not hold.
$c_{3,1} = c_{2,2} = c_{1,3}$ does not hold.

【输入样例1】

3 1 9
2 5 6
2 7 1

【输出样例1】

0.666666666666666666666666666667

【输入样例2】

7 7 6
8 6 8
7 7 6

【输出样例2】

0.004982363315696649029982363316

【输入样例3】

3 6 7
1 9 7
5 7 5

【输出样例3】

0.4

【题目来源】

https://atcoder.jp/contests/abc319/tasks/abc319_c

题目解析 🍉

【题目分析】

枚举 + 排列。

优质题解传送门：https://anubhavnegi54.medium.com/false-hope-atcoder-abc-319-ed3a7d3e12c8

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
int g[10], order[10];
// 需要枚举判断的行、列、对角线
vector<tuple<int, int, int>> lines = {
        {1, 2, 3},  // 第一行
        {4, 5, 6},  // 第二行
        {7, 8, 9},  // 第三行
        {1, 4, 7},  // 第一列
        {2, 5, 8},  // 第二列
        {3, 6, 9},  // 第三列
        {1, 5, 9},  // 主对角线
        {3, 5, 7}   // 次对角线
};

// 查找值x在order中的下标
int findi(int x) {
    for (int i = 1; i <= 9; i++) if (order[i] == x) return i;
}

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入原始棋盘
    for (int i = 1; i <= 9; i++) cin >> g[i];

    // 设定初始排列顺序
    for (int i = 1; i <= 9; i++) order[i] = i;

    int ans = 0, tot = 0; // 设定答案数量与排列总数
    // 枚举所有的排列情况（9! = 362880）
    do {
        bool dis = false;
        tot++;
        // 对于当前排列，枚举所有行、列、对角线，判断是否有disappointed的情况
        for (auto t: lines) {
            // 如判断主对角线的3个元素是否存在disappointed的情况
            // 先取出主对角线元素下标1、5、9，分别赋给a、b、c
            // 然后查看1、5、9在当前order排列中的位次，赋给oa、ob、oc
            int a = get<0>(t), oa = findi(a);
            int b = get<1>(t), ob = findi(b);
            int c = get<2>(t), oc = findi(c);

            // 若1、5元素相同，且1、5在当前order中出现的顺序均早于9，说明存在disappointed的情况
            if (g[a] == g[b] && oa < oc && ob < oc) {
                dis = true;
                break;
            }

            // 同理，枚举1、9元素相同的情况
            if (g[a] == g[c] && oa < ob && oc < ob) {
                dis = true;
                break;
            }

            // 同理，枚举5、9元素相同的情况
            if (g[b] == g[c] && ob < oa && oc < oa) {
                dis = true;
                break;
            }
        }
        if (!dis) ans++;
    } while (next_permutation(order + 1, order + 9 + 1));

    // 输出答案
    cout << fixed << setprecision(10) << 1.0 * ans / tot << endl;

    return 0;
}