Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 292 B問題 Yellow and Red Card

AtCoder ABC292 ABC 200 pts B問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 人の人がサッカーの試合をしている.

この $N$ 人について, 以下の $Q$ 個のイベントを順に処理せよ.

$\texttt{1 x}$ : 選手 $x$ にイエローカードが提示される (累積2枚で退場)
$\texttt{2 x}$ : 選手 $x$ にレッドカードが提示される (一発退場)
$\texttt{3 x}$ : この時点で, 選手 $x$ は退場しているか? という質問に答える.

制約

$1 \leq N \leq 100$
$1 \leq Q \leq 100$
$1 \leq x \leq N$
$\texttt{3 x}$ のタイプのイベントが少なくとも $1$ 回はある.
既に退場している選手にカードが提示されることはない.

解法

レッドカードをイエローカード $2$ 枚分と見なすことにより, 各選手が提示されたイエローカードを記録することにより, 各質問に対しては選手 $x$ がイエローカードを $2$ 枚以上提示されているか? ということと同値になる.

よって, 計算量 $O(N+Q)$ 時間で全てのイベントを処理することができた.