ABC244Dを解いた【転倒数】

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

ABC当日にACできなかった問題を解いていく

ABCの問題を解いていく

実装コード

転倒数っていう概念を理解しないといけないらしい。

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

今回の場合は転倒数の偶数奇数が一致するかどうかを確認すればよく、
オーダー数が非常に少ないので全列挙でも余裕みたいだが、
先日実装した転倒数のコードを流用して判定してみる

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 = ["R","G","B"]
    N = len(T)  
    ft1 = FenwickTree(N)
    ft2 = FenwickTree(N)
    S1 = rLS()
    S2 = rLS()
    A1 = [T.index(s) for s in S1]
    A2 = [T.index(s) for s in S2]
    t1 = 0
    for i,a in enumerate(A1):
        t1 += i-ft1.sum(a+1)
        ft1.add(a,1)
    t2 = 0
    for i,a in enumerate(A2):
        t2 += i-ft2.sum(a+1)
        ft2.add(a,1)
    ans = t1 % 2 == t2 % 2
    print("Yes" if ans else "No")
    
if __name__ == '__main__':
    main()

感想

前回解いた問題含めて転倒数の理解が深まった