AtCoder が提供しているABC（AtCoder Beginner Contest）314 のB問題をC++とPythonで解いてみました。ABC314は、2023年8月12日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Roulette（Difficulty : 135）
問題はリンク先をご覧ください。
Xに賭けた人で賭けた目が一番少ない人を求めます。AtCoder Problems による Difficulty は 135 でした。
解答案
次の手順で条件を満たす人を出力します。同じような走査（1番目と2番目）を行いますが、Nの上限が100なので間に合います。
- X に賭けた人で賭けた目の個数が一番少ない個数（c_min）を求める。
- X に賭けた人で賭けた目の個数が c_min である人を配列 result に格納する。
- 配列 result の要素の個数と要素を出力する。
C++ プログラム例（ABC314B）
賭けた目は二次元配列 a[i][j] に格納します。人 a[i] の j 番目に賭けた目が a[i][j] となります。
手順に従い、c_min を求めます（21ー28行目）。次にXを当てた人で賭けた数が c_min である人を result に格納します（30ー37行目）。
最後に result の size() とすべての要素を出力します。以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> a(n);
for (int i = 0; i < n; ++i) {
int c;
cin >> c;
for (int j = 0; j < c; ++j) {
int m;
cin >> m;
a[i].push_back(m);
}
}
int x;
cin >> x;
int c_min = 100;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < a[i].size(); ++j) {
if (a[i][j] == x) {
c_min = min(c_min, (int)a[i].size());
}
}
}
vector<int> result;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < a[i].size(); ++j) {
if ((a[i][j] == x)&&(a[i].size() == c_min)) {
result.push_back(i + 1);
}
}
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
cout << result[i] << " \n"[i == result.size() - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC314B）
C++のプログラムを移植しました。リストの処理はC++と比較してすっきりと書けています（11、15行目）。
"""AtCoder Beginner Contest 314 B"""
n = int(input())
a = [[] for i in range(n)]
for i in range(n):
c = int(input())
a[i] = list(map(int, input().split()))
x = int(input())
c_min = 100
for i in range(n):
if x in a[i]:
c_min = min(c_min, len(a[i]))
result = []
for i in range(n):
if x in a[i] and len(a[i]) == c_min:
result.append(i + 1)
print(len(result))
print(*result)こちらも「AC」と判定されました。
最後に
問題を読んだ直後は、いろいろな実装を考えましたが、Nの制約が100以下であったため、2回走査するプログラムにしました。
引き続き ABC の問題を紹介していきます。
