Kazun の競プロ記録

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

AtCoder Beginner Contest 299 B問題 Trick Taking

AtCoder ABC ABC299 B問題 200 pts

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

問題

提出解答

問題の概要

$N$ 人がトリックテイキング型のゲームを行った.

各カードには色と値が設定されている. なお, 全てのカードの値は異なっている.

現在, 場の切り札の色は $T$ である.

$N$ 人の人は $1$ 人 $1$ 枚ずつカードを出した. $i$ 番目の人が出したカードの色は $C_i$ で, 値は $R_i$ である.

この $N$ 枚のカードから次のようにして $1$ 人の勝者を決定する.

$N$ 枚のカードの中に切り札の色のカードが存在する場合, 切り札の色のカードのうち, 値が最大であるカードを出した人が勝者である.
$N$ 枚のカードの中に切り札の色のカードが存在しない場合, $1$ 番目の人が出したカードの色のカードのうち, 値が最大であるカードを出した人が勝者である.

勝者は誰か?

制約

$2 \leq N \leq 2 \times 10^5$
$1 \leq T \leq 10^9$
$1 \leq C_i \leq 10^9$
$1 \leq R_i \leq 10^9$
$R_1, \dots, R_N$ は全て異なる.

解法

まず, 勝負の対象となるカードの色 $D$ を求め, 色 $D$ のカードのうち, 値が最大であるようなカードを出した人を求めれば良い. ここで, $D$ は

$C_1, \dots, C_N$ の中に $T$ が存在するならば, $D=T$ である.
$C_1, \dots, C_N$ の中に $T$ が存在しないならば, $D=C_1$ である.

$D$ を求めるパート, 最大の値のカードを求めるパート, 勝者を求めるパートは全て for 文で求めることができる.