ABC292 B問題（Yellow and Red Card）を解く

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

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

B問題 Yellow and Red Card（Difficulty : 39）

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

ABC292 B問題 Yellow and Red Card

与えられたクエリを素直に処理する問題です。AtCoder Problems による Difficulty は 39 でした。

解答案

各選手が持つペナルティを配列 p で管理します。問題を以下の方針で解きます。

• N と Q を読み込む。
• Q 回、整数 query と player を読み込み、以下の処理をする。
  • query == 1: player のペナルティを1増やす。
  • query == 2: player のペナルティを2増やす。
  • query == 3: player のペナルティが2以上の場合 “Yes” を、それ以外の場合 “No” を出力する。

C++ プログラム例（ABC292B）

選手の番号は1から与えられているため、ペナルティを管理する配列 p の要素数を N + 1 で宣言します（8行目）。

以下が、上の方針で書いたC＋＋プログラムとなります。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;
	vector<int> p(n + 1, 0);

	for (int i = 0; i < q; ++i) {
		int query;
		int player;
		cin >> query >> player;
		if (query == 1) {
			p[player] += 1;
		} else if (query == 2) {
			p[player] += 2;
		} else if (query == 3) {
			if (p[player] >= 2) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		}
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC292B）

Python も C++ とほぼ同じ書き方をしました。for 文のループ変数を参照しない場合は、その意図を明確にするために “_” を使うようにしています（5行目）。

"""AtCoder Beginner Contest 292 B"""
n, q = map(int, input().split())
p = [0] * (n + 1)

for _ in range(q):
    query, player = map(int, input().split())
    if query == 1:
        p[player] += 1
    elif query == 2:
        p[player] += 2
    elif query == 3:
        print("Yes" if p[player] >= 2 else "No")

こちらも「AC」と判定されました。

最後に

B問題の公式解説で、末尾に以下の記述がありました。

Bonus (C 問題相当) : N =10¹⁸, Q =10⁵ の場合も高速に動作する方針を考えてみましょう。

https://atcoder.jp/contests/abc292/editorial/5900

この問題は、配列（リスト）の代わりに連想配列（C++ではmap、Python ではdefaultdict）を使えば解くことができます。使うコンテナが変わるだけで、大部分のコードは同一となります。

引き続き ABC の問題を紹介していきます。