ABC 199 IPFL 해설 [ptyhon]

URL


https://atcoder.jp/contests/abc199/tasks/abc199_c

구속


1<= N<= 2*10^{5}
1<= Q<= 3*10^{5}

문제 개요

  • 길이가 2N인 문자열 S.질의응답 전체 처리 후 S
  • T, A, B 세 정수로 구성된 Q개 조회
  • T = 1의 경우 S의 A 문자 및 B 문자 대체
  • T = 2에서 S의 전반부 N자 및 후반부 N자 호환
  • 코드 커밋


    def solve(N, S, Q, T, A, B):
        ans = []
        for i in S:
            ans.append(i)
        swap_flag = False
        for i in range(Q):
            if T[i] == 1:
                if swap_flag == False:
                    idx1, idx2 = A[i], B[i]
                else:
                    if A[i] <= N:
                        idx1 = A[i] + N
                    else:
                        idx1 = A[i] - N
                    if B[i] <= N:
                        idx2 = B[i] + N
                    else:
                        idx2 = B[i] - N
                ans[idx1-1], ans[idx2-1] = ans[idx2-1], ans[idx1-1]
            else:
                swap_flag = not swap_flag
            #print("".join(ans), swap_flag)
        if swap_flag:
            ans = ans[N:] + ans[:N]
        return "".join(ans)
    
    
    if __name__ == "__main__":
        N = int(input())
        S = input()
        Q = int(input())
        T, A, B = [0]*Q, [0]*Q, [0]*Q
        for i in range(Q):
            T[i], A[i], B[i] = map(int, input().split())
        print(solve(N, S, Q, T, A, B))
    
    

    고찰하다.

  • 제한에서 각 작업을 천천히 시작하면 O(NQ)가 통과할 수 없습니다.
  • T=1의 조작은 O(1)로 할 수 있기 때문에 T=2의 조작 효율을 높이고 싶다
  • 문자열 S의 길이, 구성된 문자는 변하지 않고 순서만 바뀌기 때문에 최초의 문자열의 각 문자는 현재 각각 몇 번, 이런 매핑만 있으면 된다
  • 여기서부터 전개되는 줄 모르고 해설을 읽었다
  • 해설

  • T = 2의 앞뒤 문자열이 서로 바뀌므로 flag을 정보로 바꿀 지 여부
  • T=1의 조작이 바뀌지 않으면 바로 바꾼다. 바꾼 경우 현재 문자열의 indexi와 실제 문자열의 indexj는 1-index를 사용한다.
    i<=N이면 j=i+N
    i>N이면 j=i-N
    되다
  • 마지막 검색어를 swap 조작하는 단계에서 flag 출력 전반부의 문자열에 따라 내용을 바꾸면 OK
  • 실시 방침

  • flag
  • 포함
  • 문자열은 직접 조작할 수 없기 때문에 목록에 각각 문자
  • 를 입력합니다
  • 처음에 1-index로 첨가자의 변화를 고려하여 0-index swap

  • 다음의 반성

  • 조회 시스템의 문제는 출력에 따라 어떤 정보를 가져야 하는지를 고려해야 한다.(이번이라면 최종 문자열만 알고 싶어요. 중간 문자열은 필요 없어요. flag로 복원하면 충분해요.)
  • 오랜만에 경기 외에 문제를 풀어봤지만 차디프 하위를 풀지 못해 정진의 중요성을 느꼈다
  • 랜덤 검사기를 함수화하여 제작하기 편리하도록 하였으며, 앞으로도 계속
  • 참고 자료


    해설

    좋은 웹페이지 즐겨찾기