AtCoder が提供しているABC（AtCoder Beginner Contest）319 のC問題をC++とPythonで解いてみました。ABC319は、2023年9月9日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 False Hope（Difficulty : 1111）
問題はリンク先をご覧ください。
順列全探索で求めることができます。浮動小数点数の出力に注意が必要です。AtCoder Problems による Difficulty は 1111 でした。
解答案
C++ プログラム例（ABC319C）
3×3のマス目を順番に取り出す通り数は、$9! = 362880$ となります。それぞれの場合に、縦3列、横3行、ななめ2通りの8種類の集合について、最初に選ばれた数と、次に選ばれた数が異なっていれば、「がっかり」しません。この「がっかり」しない通り数（result）を $9!$ で割った値が解答となります。
プログラムの補足は以下です。
- 順列の生成には、next_permutation を使いました（48行目）。
- 生成した順列に従い、縦3列（y）、横3行（x）、ななめ（d1、d2）に値を格納していきます（26ー35行目）。
- 上記のコンテナの最初の要素と次の要素が等しいか調べます（37ー44行目）。
- すべて異なれば、変数 result の値を増やします（46行目）。
- 真の値からの絶対誤差が $10^{−8}$ 以下である必要があるため、printf で小数点以下10桁まで出力しました（50行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
vector<int> n(9);
for (int i = 0; i < 9; ++i) {
cin >> n[i];
}
vector<int> p(9);
for (int i = 0; i < 9; ++i) {
p[i] = i;
}
int result = 0;
int factorial = 0;
do {
++factorial;
vector<vector<int>> x(3);
vector<vector<int>> y(3);
vector<int> d1;
vector<int> d2;
for (int i = 0; i < 9; ++i) {
x[p[i] / 3].push_back(n[p[i]]);
y[p[i] % 3].push_back(n[p[i]]);
if ((p[i] == 0)||(p[i] == 4)||(p[i] == 8)) {
d1.push_back(n[p[i]]);
}
if ((p[i] == 2)||(p[i] == 4)||(p[i] == 6)) {
d2.push_back(n[p[i]]);
}
}
bool t = true;
for (int i = 0; i < 3; ++i) {
if ((x[i][0] == x[i][1])||(y[i][0] == y[i][1])) {
t = false;
}
}
if ((d1[0] == d1[1])||(d2[0] == d2[1])) {
t = false;
}
if (t) {
++result;
}
} while (next_permutation(p.begin(), p.end()));
printf("%.10lf\n", (double)result / (double)factorial);
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC319C）
Python 版も基本的な考え方は同じです。以下は補足です。
- 順列の生成には、itertools.permutations を使いました（9、12行目）。
- 浮動小数点数の出力には、f文字列を使いました（34行目）。
"""AtCoder Beginner Contest 319 C"""
import itertools
n = [0] * 9
n[0], n[1], n[2] = map(int, input().split())
n[3], n[4], n[5] = map(int, input().split())
n[6], n[7], n[8] = map(int, input().split())
num = list(range(9))
result = 0
factorial = 0
for p in list(itertools.permutations(num)):
factorial += 1
x = [[] for _ in range(3)]
y = [[] for _ in range(3)]
d1 = []
d2 = []
for pi in p:
x[pi // 3].append(n[pi])
y[pi % 3].append(n[pi])
if pi in [0, 4, 8]:
d1.append(n[pi])
if pi in [2, 4, 6]:
d2.append(n[pi])
t = True
for i in range(3):
if x[i][0] == x[i][1] or y[i][0] == y[i][1]:
t = False
if d1[0] == d1[1] or d2[0] == d2[1]:
t = False
if t:
result += 1
print(f"{result / factorial:.10f}")こちらも「AC」と判定されました。
最後に
D問題を先に解いたこともあり、C問題を解いている途中でコンテストが終了しました。この問題は確率を求めるために四苦八苦して時間を失っていました。「変に計算するより、全探索をするべき」という教訓を再認識しました。
引き続き ABC の問題を紹介していきます。
