ABC409Dを解いた【巡回シフト】

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

ABC409のD問題を解いていく

実装コード

解説のコードほぼそのままになってしまった。

とりあえずなぜそうなるのかをGPTに聞いてみたので貼り付けておく。

• 先頭に近い位置の改善が最優先：辞書順は左から決まるので、最初に下がる場所（S[i] > S[i+1]）を処理するのが最も効く。
• S[ℓ] は可能な限り後方へ：S[ℓ] を抜くと、位置 ℓ により小さい S[ℓ+1] が繰り上がって、接頭辞が小さくなる。あとは S[ℓ] を必要以上に前へ戻さないよう、初めての「自分より大きい文字」の直前に置けばよい

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)

def main():
    T = rI()
    for _ in range(T):
        N = rI()
        S = rS()
        l = -1
        for i in range(N-1):
            if S[i] > S[i+1]:
                l = i
                break
        if l == -1:
            print(S)
            continue
        r = N
        for j in range(l+1, N):
            if S[l] < S[j]:
                r = j
                break
        print(S[:l] + S[l+1:r] + S[l] + S[r:])
    
if __name__ == '__main__':
    main()

感想

巡回シフトって聞くとどうしても身構えてしまう。