#1159471 (Python3) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: 왕지후
• 提出日時: 2026-04-18 11:45:45
• 言語: Python3 (3.14.3 + numpy 2.4.4 + scipy 1.17.1)
• 結果: TLE
• 実行時間: -
• コード長: 4,467 bytes
• コンパイル時間: 620 ms
• コンパイル使用メモリ: 20,824 KB
• 実行使用メモリ: 68,552 KB
• 最終ジャッジ日時: 2026-04-18 11:47:48
• 合計ジャッジ時間: 13,002 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge2_1

ファイルパターン	結果
sample	-- * 1
other	AC * 5 TLE * 2 -- * 21

ソースコード

import sys

# Increase recursion depth for deep trees up to 2*10^5
sys.setrecursionlimit(300000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    T = int(input_data[0])
    idx = 1
    
    INF = 10**18 + 1
    out_lines = []
    
    for _ in range(T):
        N = int(input_data[idx])
        K = int(input_data[idx+1])
        idx += 2
        
        A = []
        for _ in range(N - 1):
            A.append(int(input_data[idx]))
            idx += 1
            
        # If K is strictly greater than the total possible valid configurations (2^{N-1})
        if (N - 1) < 60 and K > (1 << (N - 1)):
            out_lines.extend(["-1", "-1", "-1"])
            continue
            
        # Fenwick Tree to maintain active positions
        bit = [0] * (N + 1)
        def add(i, delta):
            while i <= N:
                bit[i] += delta
                i += i & (-i)
                
        def find_kth(k_val):
            pos = 0
            for i in range(18, -1, -1):
                next_pos = pos + (1 << i)
                if next_pos <= N and bit[next_pos] < k_val:
                    pos = next_pos
                    k_val -= bit[pos]
            return pos + 1

        for i in range(1, N + 1):
            add(i, 1)
            
        pos_id = [i for i in range(N + 1)]
        
        L_child = [0] * (2 * N)
        R_child = [0] * (2 * N)
        sz = [0] * (2 * N)
        
        for i in range(1, N + 1):
            sz[i] = 1
            
        # Build the operation tree
        for i in range(1, N):
            idx1 = find_kth(A[i - 1])
            idx2 = find_kth(A[i - 1] + 1)
            
            u = pos_id[idx1]
            v = pos_id[idx2]
            
            node = N + i
            L_child[node] = u
            R_child[node] = v
            sz[node] = sz[u] + sz[v]
            
            pos_id[idx1] = node
            add(idx2, -1)
            
        root = 2 * N - 1
        
        dp_R = [0] * (2 * N)
        dp_P = [0] * (2 * N)
        dp_S = [0] * (2 * N)
        ans = [''] * (N + 1)
        
        def dfs(u, out_R, out_P, out_S, current_K):
            if u <= N:
                # Lexicographical check order: P -> R -> S
                for c in ['P', 'R', 'S']:
                    if c == 'P': ways = out_P
                    elif c == 'R': ways = out_R
                    else: ways = out_S
                    
                    if current_K <= ways:
                        ans[u] = c
                        dp_R[u] = 1 if c == 'R' else 0
                        dp_P[u] = 1 if c == 'P' else 0
                        dp_S[u] = 1 if c == 'S' else 0
                        return current_K
                    else:
                        current_K -= ways
                return current_K

            lc = L_child[u]
            rc = R_child[u]
            k = sz[rc] - 1
            
            mult = (1 << k) if k < 60 else INF
            
            # Sub-problem logic given right child is entirely unfixed
            out_L_R = min(INF, mult * (out_R + out_P))
            out_L_P = min(INF, mult * (out_P + out_S))
            out_L_S = min(INF, mult * (out_S + out_R))
            
            current_K = dfs(lc, out_L_R, out_L_P, out_L_S, current_K)
            
            LR = dp_R[lc]
            LP = dp_P[lc]
            LS = dp_S[lc]
            
            # Sub-problem logic given left child is fully evaluated/fixed
            out_R_R = min(INF, LS * out_R + LP * out_P)
            out_R_P = min(INF, LR * out_P + LS * out_S)
            out_R_S = min(INF, LP * out_S + LR * out_R)
            
            current_K = dfs(rc, out_R_R, out_R_P, out_R_S, current_K)
            
            RR = dp_R[rc]
            RP = dp_P[rc]
            RS = dp_S[rc]
            
            # Calculate and bubble-up DP combinations for current internal node
            dp_R[u] = min(INF, LR * RS + LS * RR)
            dp_P[u] = min(INF, LP * RR + LR * RP)
            dp_S[u] = min(INF, LS * RP + LP * RS)
            
            return current_K

        # Retrieve for each individual target character
        for target in ['R', 'P', 'S']:
            dfs(root, 1 if target == 'R' else 0, 1 if target == 'P' else 0, 1 if target == 'S' else 0, K)
            out_lines.append("".join(ans[1:]))

    sys.stdout.write("\n".join(out_lines) + "\n")

if __name__ == '__main__':
    solve()