ARC 109C-Large RPS Tournament 설명 [pyhon]

URL

https://atcoder.jp/contests/arc109/tasks/arc109_c

구속

1<= N,K<= 100
s는 RPS로 구성된 길이 n의 문자열입니다.

문제 개요

2^k명으로 가위바위보 토너먼트를 진행한다.

사람은 0-index로 배열하고 indexi는 매번 s[i%n]로 표시된 손을 내밀었다

아들을 사랑하는 상황에서 index가 작은 것이 좋다.

대회 승자 구하기

코드 커밋

n, k = map(int, input().split())
s = input()
for i in range(k):
    s = s + s  # あらかじめ２つつなげる
    next_s = []
    for j in range(n):
        if s[2 * j] == s[2 * j + 1]:
            next_s.append(s[2 * j])
        elif s[2 * j] in "RS" and s[2 * j + 1] in "RS":
            next_s.append("R")
        elif s[2 * j] in "PR" and s[2 * j + 1] in "PR":
            next_s.append("P")
        elif s[2 * j] in "SP" and s[2 * j + 1] in "SP":
            next_s.append("S")
        else:
            raise Exception
    s = "".join(next_s)
print(next_s[0])

고찰하다.

반복하는 방법 같은 느낌으로 반씩 나누고 싶어요.

토너먼트 리스트를 직접 고려하면 어려워

1라운드에서 왼쪽에서 i번째인 사람이 s[i]를 내기 위해 n라운드에서 왼쪽에서 i번째가 s'[i]가 되는 s를 순서대로 구성할 수 있다.

실시 방침

업데이트 s

s[2i]와 s[2i+1]의 승리자는 s'[i]

k회 반복

다음의 반성

간단한 문제 설정이지만 이틀 정도의 고민 끝에 자력 AC

2^k의 값을 고려하다 보니 초반부터 제곱법처럼 부분분할을 고려하는 생각을 반복했지만 토너먼트 테이블을 분할하겠다는 생각이 먼저 왔다. 몇 번째 경기일까?이런 생각을 회귀적으로 분할하는 데까지 시간이 걸렸다.

반복 제곱법과 같은 문제는 같은 처리가 되기 위해 변수를 다시 설정할 수 있는지 고려한다.

참고 자료

https://qiita.com/Kept1994/items/ea91c057b0e552323da3 쌍환의 해설.이 2^(i-1)의 상태 변환에 따라 2^i 이후의 변환을 계산하는 DP 테이블 만들기