AtCoder が提供しているABC（AtCoder Beginner Contest）299 のB問題をC++とPythonで解いてみました。ABC299は、2023年4月22日21:00に実施されました。
この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Trick Taking
問題はリンク先をご覧ください。
トランプゲームの1トリックの勝ちを判定する問題です。AtCoder Problems による Difficulty は算出されていません。B問題としては通常の難易度だと思います。
解答案
ナポレオンやコントラクトブリッジなどのトランプゲームで与えられた1トリックに勝つ人を判定します。
- 値1: 色がTである最大の値を出したプレイヤーを記憶する（切り札）。
- 値2: 色がT以外で、プレイヤー1の色と同じ色の最大の値を出したプレイヤーを記憶する（リード）。
- 切り札が出ている場合は値1を出力する。それ以外の場合は値2を出力する。
C++ プログラム例（ABC299B）
値1を出したプレイヤーを変数 t_index で、最大値を変数 t_max に記憶します。値2を出したプレイヤーを変数 else_index で、最大値を else_max に記憶します。
プレイヤーの番号を出力するときは、配列の添え字で管理しているため、1を加えて出力しています（36、38行目）。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, t;
cin >> n >> t;
vector<int> c(n);
for (int i = 0; i < n; ++i) {
cin >> c[i];
}
vector<int> r(n);
for (int i = 0; i < n; ++i) {
cin >> r[i];
}
int t_max = 0;
int t_index = -1;
int else_max = 0;
int else_index = -1;
for (int i = 0; i < n; ++i) {
if (c[i] == t) {
if (r[i] > t_max) {
t_max = r[i];
t_index = i;
}
} else if (c[i] == c[0]) {
if (r[i] > else_max) {
else_max = r[i];
else_index = i;
}
}
}
if (t_index >= 0) {
cout << t_index + 1 << endl;
} else {
cout << else_index + 1 << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC299B）
C++のロジックをそのまま Python に書き直しました。
"""AtCoder Beginner Contest 299 B"""
n, t = map(int, input().split())
c = list(map(int, input().split()))
r = list(map(int, input().split()))
t_max = 0
t_index = -1
else_max = 0
else_index = -1
for i in range(n):
if c[i] == t:
if r[i] > t_max:
t_max = r[i]
t_index = i
elif c[i] == c[0]:
if r[i] > else_max:
else_max = r[i]
else_index = i
if t_index >= 0:
print(t_index + 1)
else:
print(else_index + 1)こちらも「AC」と判定されました。
最後に
この問題では、値2を求めるときにその他の場合で計算していました。正しくは、プレイヤー1が出した色と同じ色で計算する必要があります。これでWA1回分のペナルティ（5分）されました。A問題、B問題は急いで解こうと問題を斜め読みする傾向があります。しくじりました。
引き続き ABC の問題を紹介していきます。
