Kazun の競プロ記録

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

AtCoder Beginner Contest 252 B問題 Takahashi's Failure

AtCoder ABC ABC252 B問題 200 pts

問題

提出解答

問題の概要

$A_1, \dots, A_N$ から最大値を一つ選ぶ. このとき, 選んだ項を第 $I$ 項としたとき, $I \in \{B_1, \dots, B_K\}$ となる可能性はあるか?

制約

$1 \leq K \leq N \leq 100$
$1 \leq A_i \leq 100$
$1 \leq B_i \leq N$
$B_i$ は全て異なる.

解法

判定すべき条件は以下と同値である.

$A_{B_j}=\max A$ となる $1$ 以上 $K$ 以下の整数 $K$ は存在するか?

これを判定するためには, 実際に各 $j=1,2, \dots, N$ に対して, $A_{B_j}=\max A$ を満たすかどうかをチェックすれば良い.

計算量は $O(N+K)$ である.