結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー Naru820
提出日時 2026-04-01 10:49:17
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,191 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 604 ms
コンパイル使用メモリ 20,696 KB
実行使用メモリ 28,760 KB
最終ジャッジ日時 2026-04-17 20:02:07
合計ジャッジ時間 7,920 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# Gemini 3
import sys

sys.setrecursionlimit(300000)


class FenwickTree:
    def __init__(self, size):
        self.tree = [0] * (size + 1)

    def add(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += i & (-i)

    def find_kth(self, k):
        idx = 0
        for i in range(17, -1, -1):
            next_idx = idx + (1 << i)
            if next_idx < len(self.tree) and self.tree[next_idx] < k:
                idx = next_idx
                k -= self.tree[idx]
        return idx + 1


def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    fenwick = FenwickTree(N)
    for i in range(1, N + 1):
        fenwick.add(i, 1)

    left_child = [0] * (2 * N - 1)
    right_child = [0] * (2 * N - 1)
    node_at_pos = list(range(-1, N))

    node_id = N
    for a in A:
        pos1 = fenwick.find_kth(a)
        pos2 = fenwick.find_kth(a + 1)

        left_child[node_id] = node_at_pos[pos1]
        right_child[node_id] = node_at_pos[pos2]

        node_at_pos[pos1] = node_id
        fenwick.add(pos2, -1)
        node_id += 1

    root = 2 * N - 2
    INF = 2 * 10**18

    # --- 簡略化されたDP計算 ---
    # dp[u] : 部分木 u が特定の文字になる組み合わせの総数
    dp = [1] * (2 * N - 1)
    for i in range(N, 2 * N - 1):
        L = left_child[i]
        R = right_child[i]
        # 合流のたびに組み合わせが2倍になる (オーバーフロー防止のためINFで頭打ち)
        dp[i] = min(INF, dp[L] * dp[R] * 2)

    # 'P'=0, 'R'=1, 'S'=2
    win = [[-1, 0, 2],
           [0, -1, 1],
           [2, 1, -1]]

    def solve_for_target(target):
        if dp[root] < K:
            return "-1"

        res = [-1] * N
        curr_K = K

        def dfs(u, ways):
            nonlocal curr_K
            if u < N:
                for c in range(3):
                    if curr_K <= ways[c]:
                        res[u] = c
                        return c
                    curr_K -= ways[c]
                return -1

            L = left_child[u]
            R = right_child[u]

            ways_L = [0] * 3
            for cL in range(3):
                w = 0
                for cR in range(3):
                    w_c = win[cL][cR]
                    if w_c != -1:
                        w += ways[w_c]
                # dp[R] は文字に依存しないスカラー値になったため、ここで一括して掛ける
                ways_L[cL] = min(INF, w * dp[R])

            realized_L = dfs(L, ways_L)

            ways_R = [0] * 3
            for cR in range(3):
                w_c = win[realized_L][cR]
                if w_c != -1:
                    ways_R[cR] = ways[w_c]

            realized_R = dfs(R, ways_R)

            return win[realized_L][realized_R]

        root_ways = [0] * 3
        root_ways[target] = 1
        dfs(root, root_ways)

        return "".join("PRS"[c] for c in res)

    print(solve_for_target(1))  # Target: R
    print(solve_for_target(0))  # Target: P
    print(solve_for_target(2))  # Target: S


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        solve()
0