AtCoder が提供しているABC（AtCoder Beginner Contest）392 D問題をC++とPythonで解いてみました。ABC392は、2025年2月8日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Doubles（Difficulty : 579）
問題の詳細は、リンク先をご覧ください。
それぞれのサイコロの目の頻度を記憶しておきます。AtCoder Problems による Difficulty は 579 でした。
解答案
C++ プログラム例（ABC392D）
それぞれのサイコロの目の頻度を map コンテナに記憶します。2つの異なるサイコロを選んで同じ数がでる確率を求めます。工夫として、2つのサイコロのうち目の種類が少ない方を基準に同じ数を探しています（26ー35行目）。この工夫をしないと TLE 判定となりました。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
cin >> n;
vector<int> k(n);
vector<map<int, int>> a(n);
for (int i = 0; i < n; ++i) {
cin >> k[i];
for (int j = 0; j < k[i]; ++j) {
int t;
cin >> t;
++a[i][t];
}
}
double result = 0.0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
ll t = 0;
int i2, j2;
if (a[i].size() < a[j].size()) {
i2 = i;
j2 = j;
} else {
i2 = j;
j2 = i;
}
for (auto e : a[i2]) {
t += (ll)e.second * (ll)a[j2][e.first];
}
result = max(result, t / (double)k[i] / (double)k[j]);
}
}
cout << fixed << setprecision(15);
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC392D）
Python版も基本的な考え方は同じです。サイコロの目の頻度は、collections.Counter を使いました。以下がプログラムです。
"""AtCoder Beginner Contest 392 D"""
from collections import Counter
n = int(input())
k = []
a = []
for i in range(n):
in_list = list(map(int, input().split()))
k.append(in_list[0])
a.append(Counter(in_list[1:]))
result = 0.0
for i in range(n):
for j in range(i + 1, n):
t = 0
if len(a[i]) < len(a[j]):
i2, j2 = i, j
else:
i2, j2 = j, i
for key, value in a[i2].items():
t += value * a[j2][key]
result = max(result, t / k[i] / k[j])
print(result)こちらも「AC」と判定されました。
最後に
Python は、collections を上手く使うと、すっきりと書けることが分かりました。
引き続き ABC の問題を紹介していきます。
