目次
はじめに
この記事では、ABC345のC問題を解説していきます。
ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。
ABC345 C – One Time Swap
問題
文字列Sが与えられます。一度だけ、Sのいずれかの位置の2文字を交換します。この操作の結果、起こり得る文字列が何通りあるか求める問題です。
制約
- \(2 \leqq len(S) \leqq 10^6\)
思考の筋道
S内に同じ文字が存在しないケースから考えましょう。
同じ文字がない場合の具体例
次に、S内に同じ文字が存在するケースを考えます。
同じ文字がある場合の具体例
S = “aabbc” のとき
a と a など同じ文字を交換しても、交換の前後で変化がありません。これらの組合せを全組合せから引きましょう。
そのためにはS内で各アルファベットが何回登場するのか事前に調べ、保管しておく必要があります。
{“a” : 2, “b” : 2, “c” : 1}
なお、交換前と同じ文字列も1通りとしてカウントできるため、最後に+1することを忘れないようにしましょう。
\({}_5 \mathrm{ C }_2 – {}_2 \mathrm{ C }_2 – {}_2 \mathrm{ C }_2 + 1 = 9\) 通り。
コード
import string
S = input()
n = len(S)
d = {i: 0 for i in string.ascii_lowercase}
for char in S:
d[char] += 1
count = n * (n - 1) // 2
flg = False
for char in d:
if d[char] >= 2:
count -= (d[char] * (d[char] - 1)) // 2
flg = True
if flg:
count += 1
print(count)以上、ABC345のC問題の解説でした！
では、またね。
S = “abcde” のとき
この場合はどの2文字を交換しても、それぞれ異なる文字列となります。全5文字から2文字を選ぶ組合せの数がそのまま答えになります。
\({}_5 \mathrm{ C }_2 = 10\) 通り。