ABC264D - "redocta".swap(i,i+1)

方法1:転倒数

考え方

最近,以下の出題があったので,「転倒数」が最初に浮かんだ.
ABC261F - Sorting Color Balls - 競プロはじめました

「自分より小さいのに自分よりあとに現れる数」の(すべての「自分」に関する)総和が答え.

計算量が小さいので,BITの代わりにリストを使って計算した.

回答例

S = input()
ans = 0
d = {x:i for i, x in enumerate('atcoder')}
S = [d[s] for s in S]

cnt = [0] * 10
for s in S[::-1]:
    for i in range(s):
        ans += cnt[i]
    cnt[s] += 1

print(ans)

方法2:BFS

考え方

"atcoder"が現れるまで,全探索する.
Submission #34013231 - freee Programming Contest 2022(AtCoder Beginner Contest 264)

メモ

なるほど〜
Submission #33997352 - freee Programming Contest 2022(AtCoder Beginner Contest 264)