ABC174 D - Alter Altar

AtCoder Python3 collections

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    C = iss()
    cnt = collections.Counter(C)
    red = cnt['R']
    print(red - collections.Counter(C[:red])['R'])


if __name__ == '__main__':
    main()

考え方

問題の条件により、赤い石(R)の隣に白い石(W)を置くことが出来ない。
つまり、赤い石(R)が左詰め(WWRR => RRWWやWRWRWRW => RRRWWWW）に
なっている状態にする最小の操作回数を求める。

赤い石がN個存在する場合、
与えられた石の列の先頭からN番目まで全て赤い石にする必要がある。
そのため、操作回数は最大でもN回必要となる。
しかし、先頭からN個までの間に初期位置として赤い石が配置されている場合には、
操作を行う必要はない。

そのため、あらかじめ赤い石の個数を数えて置き（最大操作回数）、
先頭から赤い石の合計数までの間に、初期位置として配置されている
赤い石の個数（操作が不要な赤い石）を引くことで回答を得ることが出来る。