Kazun の競プロ記録

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

AtCoder Beginner Contest 251 C問題 Poem Online Judge

AtCoder ABC ABC251 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個のポエム $S_1, \dots, S_N$ と, 各ポエムに対する得点 $T_1, \dots, T_N$ がある.

次を満たすようなポエム $S_i$ はオリジナルであるという.

$1 \leq j \lt i$ を満たす全ての整数 $j$ に対して, $S_i \neq S_j$ である.

オリジナルのポエムのうち, 得点が最大であるのはどれか? なお, 同率である場合は添字が最小であるものとする.

制約

$1 \leq N \leq 10^5$
$S_i は英小文字からなる長さ [tex: 1$ 以上 $10$ 以下の文字列
$0 \leq T_i \leq 10^9$

解法

ポエムがオリジナルかどうかの判定は辞書や集合を用いて既出判定を行なうことにより可能である.

可能なポエムを $S_{k_1}, \dots, S_{k_r}$ とする. このとき, 各集合 $M$ を

$M:=\{(-T_{k_j}, k_j) \mid j=1,2, \dots, r\}$

とし, $M$ 上の順序を辞書式順序とすると, $(M, \leq )$ は全集合になる. そこで, $(\widetilde{t}, \widetilde{k}):=\min M$ とすると, 実はこの $\widetilde{k}$ が答えである.

実際, 第1要素が小さいということは, $T_{k_j}$ が大きいということを意味し, 第1要素同士が等しいときは第2要素. つまり, 添字が小さい方が小さいということになる. これにより, 確かに, $\widetilde{k}$ が答えになるということがわかる.

よって, オリジナルポエムかどうかの判定で辞書や集合を用いることにより, 計算量 $O(N)$ で求めることができた.