Kazun の競プロ記録

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

AtCoder Beginner Contest 261 C問題 NewFolder(1)

AtCoder ABC ABC261 C問題 300 pts

問題

提出解答

問題の概要

$N$ 個の英小文字列 $S_1, \dots, S_N$ が与えられ得る. 次のルールに従って, 英小文字列 $T_1, \dots, T_N$ を求めよ.

$S_1, \dots, S_{i-1}$ の中に $S_i$ が1つも無ければ, $T_i=S_i$
$S_1, \dots, S_{i-1}$ の中に $S_i$ が1つ以上ある場合, その個数を $X$ として, $T_i=S_i \oplus {\tt (} \oplus X \oplus {\tt )}$

制約

$2 \leq N \leq 2 \times 10^5$
$S_i$ は長さ $1$ 以上 $10$ 以下の英小文字列.

解法

各 $i$ に対して, $X$ を求めようとすると, 全体の時間計算量が $O(N^2)$ 時間となってしまい, 間に合わない.

そこで, 辞書や連想配列などといったデータ構造を利用し, これまでの文字列の登場回数を記録しておくことにより, 全体の時間計算量を $O(N \max \left| S_i \right|)$ 時間に抑えることができる.