AtCoder が提供しているABC（AtCoder Beginner Contest）355 C問題をC++とPythonで解いてみました。ABC355は、2024年5月25日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Bingo 2（Difficulty : 325）
問題の詳細は、リンク先をご覧ください。
各ターンで宣言された整数についてビンゴが成立しているか調べます。AtCoder Problems による Difficulty は 325 でした。
解答案
ビンゴが成立しているかは、盤面を見れば分かります。ただし、その方法では計算量が $2 \times 10^3 \times 2 \times 10^3 \times 2 \times 10^5 = 8 \times 10^{11}$ となります。目安となる $10^8$ を大幅に超えます。
各ターンで選ばれた整数が属する列と行と（もしあれば）斜めの線だけを調べることによって、解くことができます。
C++ プログラム例（ABC355C）
プログラムの補足です。
- 各ターンで選ばれた整数について
- 所属する列の値を増やして、ビンゴであればループを抜けます。
- 所属する行の値を増やして、ビンゴであればループを抜けます。
- 右下がり（d1）の斜め線に属している場合、値を増やして、ビンゴであればループを抜けます。
- 左下がり（d2）の斜め線に属している場合、値を増やして、ビンゴであればループを抜けます。
変数 result の初期値を-1に設定しました。このため、ビンゴが成立しない場合、-1を出力します。以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, t;
cin >> n >> t;;
vector<int> a(t);
for (int i = 0; i < t; ++i) {
cin >> a[i];
--a[i];
}
vector<set<int>> row(n);
vector<set<int>> col(n);
set<int> d1, d2;
int result = -1;
for (int i = 0; i < t; ++i) {
row[a[i] / n].insert(a[i]);
if (row[a[i] / n].size() == n) {
result = i + 1;
break;
}
col[a[i] % n].insert(a[i]);
if (col[a[i] % n].size() == n) {
result = i + 1;
break;
}
if (a[i] / n == a[i] % n) {
d1.insert(a[i]);
if (d1.size() == n) {
result = i + 1;
break;
}
}
if (a[i] / n + a[i] % n == n - 1) {
d2.insert(a[i]);
if (d2.size() == n) {
result = i + 1;
break;
}
}
}
cout << result << endl;
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC355C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 355 C"""
n, t = map(int, input().split())
a = list(map(int, input().split()))
for i in range(t):
a[i] -= 1
row = [[] for _ in range(n)]
col = [[] for _ in range(n)]
d1 = []
d2 = []
result = -1
for i in range(t):
row[a[i] // n].append(a[i])
if len(row[a[i] // n]) == n:
result = i + 1
break
col[a[i] % n].append(a[i])
if len(col[a[i] % n]) == n:
result = i + 1
break
if a[i] // n == a[i] % n:
d1.append(a[i])
if len(d1) == n:
result = i + 1
break
if a[i] // n + a[i] % n == n - 1:
d2.append(a[i])
if len(d2) == n:
result = i + 1
break
print(result)こちらも「AC」と判定されました。
最後に
列と行と斜めについて、丁寧に判断することによって解くことができました。
引き続き ABC の問題を紹介していきます。
