Kazun の競プロ記録

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

AtCoder Beginner Contest 236 C 問題 Route Map

AtCoder ABC ABC236 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個の駅があり, 普通列車は駅 $S_1, S_2, \dots, S_N$ の順に停まる. 一方, 急行列車は駅 $T_1, \dots, T_M$ の順に停まる.

$i=1,2, \dots, N$ に対して, 駅 $S_i$ には急行列車が停まるかどうかを判定せよ.

制約

$2 \leq M \leq N \leq 10^5$
$S_i$ は長さが $1$ 以上 $10$ 以下の英小文字からなる文字列
$i \neq j \Rightarrow S_i \neq S_j$
$T$ は $S$ の部分列
$S_1=T_1, S_N=T_M$

解法

急行列車が停まる駅全体の集合を $\mathbb{T}$ とする. このとき, $i=1,2, \dots, N$ に対して, $S_i \in \mathbb{T}$ かどうかを判定すれば良い.

このとき, $\mathbb{T}$ として集合というデータ構造を用いると, 要素判定が高速にできる.