ABC264Dを解いた【転倒数】

筆者はレート800前後の茶～緑コーダ

ABC264のD問題を解いていく

実装コード

全列挙でも間に合いそうだが転倒数という概念がこの問題の裏テーマ(?)らしい

• (ざっくり)バブルソートしたときに何回交換しますか。という数

i 個のうち、自分より大きい値が何個あるか
= i - (自分より小さい値の個数) - (自分自身の値)
を計算して求める

• この計算にはBITが速いらしい(BIT=FenwickTreeはセグ木の簡易版？らしい)

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def sum(self, r):
        s = 0
        while r > 0:
            s += self.data[r]
            r -= r & -r
        return s

    def query(self, l, r):
        return self.sum(r) - self.sum(l)

    def __repr__(self):
        return "FenwickTree(" + str([self.query(i, i+1) for i in range(self.n)]) + ")"

def main():
    T = "atcoder"
    N = len(T)  
    ft = FenwickTree(N)
    S = rS()
    A = [T.index(s) for s in S]
    # err(A)
    ans = 0
    for i,a in enumerate(A):
        ans += i-ft.sum(a+1)
        ft.add(a,1)
        # err(ft)
    print(ans)    
        
        
if __name__ == '__main__':
    main()

感想

転倒数とFenwickTreeの概念両方同時に理解するのに苦労した。

• セグ木使えばよかったかなぁ…もったいないけど