AtCoder

ABC299 B問題(Trick Taking)を解く

AtCoder_ABC299_B

AtCoder が提供しているABC(AtCoder Beginner Contest)299 のB問題をC++とPythonで解いてみました。ABC299は、2023年4月22日21:00に実施されました。

この回は、外部からDDoS攻撃を受けてサーバが不安定になり unrated となりました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Trick Taking

問題はリンク先をご覧ください。

ABC299 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問題は急いで解こうと問題を斜め読みする傾向があります。しくじりました。

ABC299 について、引き続き問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA