AtCoder

ABC292 B問題(Yellow and Red Card)を解く

AtCoder_ABC292_B

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 =1018, Q =105 の場合も高速に動作する方針を考えてみましょう。

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

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

ABC292 について、引き続き、E問題まで紹介します。

COMMENT

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

CAPTCHA