Submission #68928649

---

Source Code Expand

import sys
sys.setrecursionlimit(10 ** 6)

# import numpy as np
# <nonumba> from numba import njit, jit, boolean, int64, float64, typeof




def main():
    from io import StringIO
    execute(StringIO(sample), sys.stderr)
    print("-- ^sample! --", file=sys.stderr)

    execute(sys.stdin, sys.stdout)

    # #<nonumba> if len(solve.nopython_signatures) != 1:
    # #<nonumba>     raise KeyboardInterrupt("!! Unexpected: wrong use of jit !!")

def execute(src, dst):

    N = int(src.readline())
    S = src.readline().strip()

    ans = solve(N, S)
    print(ans, file=dst)

sample = """\
3
AABBBA
"""

# #<nonumba> @jit(nopython=True, cache=True)
def solve(N, S):
    sl = list(S)
    AB = ["A"] + sl + ["x"]
    BA = ["B"] + sl + ["x"]
    ans = min(count(AB) , count(BA))
    return ans

def count(a):
    cost = 0
    nexts = {"A": 0 , "B": 0}
    for i in range(len(a)-1):
        nowc = a[i]
        j = max (i, nexts[nowc])
        while a[i] == a[j]:
            j += 1
        costinc = j - (i+1)
        cost += costinc
        a[i+1] , a[j] = a[j] , a[i+1]
        nexts[nowc] = j
    return cost

main()

Submission Info

Judge Result