ABC 401-500/ABC426B - The Odd One Out - 競技プログラミング用 知識集積所

---

問題

ABC426B

必要知識

A問題レベルのものは省略

• 全探索※

考え方

1つ以外の方の文字の正体がわかれば、あとは前から1文字ずつ見る全探索※でどうにでもできる。
ということで、問題は前半部分の、1つ以外の方の文字を特定するところをどうするか。

これは、異なる文字が1つしかないということは最初の3文字の中に同じ文字は2回以上登場する、ということを利用できる。
最初の3文字（入力の制約により、絶対に3文字以上ある）を2つずつ比較して、文字が一致したらそれが正しい文字である。

これができたら、あとは、全探索※で1文字ずつそれと一致するか見ればよい。

解答例

解答例

注意点

別解

ソートして探す

文字列をソートする場合、1つだけ異なっている文字は先頭か末尾に来る。
最初の2文字を比較して、それらが同じ文字なら先頭が、そうでなければ末尾が異なっている文字である。
という方法もある。
解答例