AGC048A-atcoder<S 해설 [ptyhon]

URL

구속

1 <= T <= 100
1 <= |S| <= 1000

문제 개요

영자 문자만 포함하는 문자열 S를 제공하고 인접한 두 문자를 swap로 반복하여atcoder를 대답합니다

코드 커밋

t = int(input())
for i in range(t):
    s = input()
    l = len(s)
    ans = -1
    for i in range(l):
        if s[i] != "a":
            if s[i] > "t":
                ans = max(1, i - 1)
            else:
                ans = i
            break
    if s > "atcoder":
        ans = 0
    print(ans)

고찰하다.

|S|작기 때문에 O(S922)통과

우선 판정 방법을 고려하고 모든 요소에 a 이외의 문자가 있으면 이를 시작할 수 있다.모든 요소 a는 움직여도 변하지 않기 때문에 불가능하다

최소 횟수를 고려하면 사전 순서의 정의에 따라 처음부터 순서대로 고려한다.

처음부터 첫 번째 a가 나올 때까지의 거리를 계산하고 대답한다.문자열을 a 이외의 문자열로 변환

이후 현재 문자열을 귀속적으로 계산할 수 있으며, 처음부터atcoder에서 현재 보이는 문자와 사전 순서가 다음과 같은 문자를 찾아 그곳까지의 거리를 늘릴 수 있다

같은 문자열이 먼저 나타나면 다음 귀속 여부는 이 문자보다 작은 문자가 나타날 때까지 거리에 달려 있다.

계산량은 O(S922)

실시 방침

귀속적으로 진행되기 때문에 함수화

상태는 현재 개수(atcoder의 어떤 문자와 비교), 현재 문자열의 깊이를 가지고 숨길 수 있습니다

함수가 ans인 것을 구하고자 하는 답은 ans(0,S,len(S)

이다.

와 (i, S) 처음부터atcoder의 S를 탐색하고atcoder[i] 아래 문자열로 되돌아오는 거리

if atcoder[i]　> S[j]: return j

elif atcoder[i] == S[j] and atcoder[i] > S[k](j < k):

return min(k,j+ans(i+1,S',k-j))

다음의 반성

마지막에 귀속되지 않고 for순환의 형식으로 변수 업데이트

참고 자료

Reference

이 문제에 관하여(AGC048A-atcoder<S 해설 [ptyhon]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://zenn.dev/knk_kei/articles/agc048-a-atcoder-s

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다