結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー Naru820
提出日時 2026-03-18 14:02:02
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,592 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 459 ms
コンパイル使用メモリ 85,120 KB
実行使用メモリ 97,152 KB
最終ジャッジ日時 2026-04-17 19:42:04
合計ジャッジ時間 4,601 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other WA * 16 RE * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# gemini 3.1pro テスト
import sys

def solve():
    # 入力の読み込み
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    A = [int(x) for x in data[1:]]
    
    # 1. BITを用いた二分木の構築
    tree = [0] * (N + 1)
    for i in range(1, N + 1):
        tree[i] = i & (-i)
        
    def add(i, delta):
        while i <= N:
            tree[i] += delta
            i += i & (-i)
            
    def get_kth(k):
        idx = 0
        for i in range(N.bit_length(), -1, -1):
            next_idx = idx + (1 << i)
            if next_idx <= N and tree[next_idx] < k:
                idx = next_idx
                k -= tree[idx]
        return idx + 1

    left_child = [0] * (2 * N)
    right_child = [0] * (2 * N)
    node_at_index = list(range(N + 1))
    
    for i in range(1, N):
        a_i = A[i - 1]
        idx1 = get_kth(a_i)
        idx2 = get_kth(a_i + 1)
        
        u = node_at_index[idx1]
        v = node_at_index[idx2]
        
        new_node = N + i
        left_child[new_node] = u
        right_child[new_node] = v
        
        # マージ（idx2を削除し、idx1の指す先を親ノードに更新）
        node_at_index[idx1] = new_node
        add(idx2, -1)
        
    # 2. ボトムアップDPの準備
    # rank_val[u][c] : ノードuで文字cを作るときの、候補間の辞書順ランク(0,1,2)
    rank_val = [[0] * 3 for _ in range(2 * N)]
    choice = [[(0, 0)] * 3 for _ in range(2 * N)]
    
    # 文字の割り当て: R=0, P=1, S=2
    # 葉の初期化（辞書順は P < R < S）
    for i in range(1, N + 1):
        rank_val[i][1] = 0  # Pが0位
        rank_val[i][0] = 1  # Rが1位
        rank_val[i][2] = 2  # Sが2位
        
    def get_lose(c):
        return (c + 2) % 3

    # ボトムアップにランクと最適な子の組み合わせを計算
    for u in range(N + 1, 2 * N):
        L = left_child[u]
        R = right_child[u]
        
        for c in range(3):
            c1 = c
            c2 = get_lose(c)
            # 左側にcを置く場合と、左側にcに負ける文字を置く場合を比較
            if rank_val[L][c1] < rank_val[L][c2]:
                choice[u][c] = (c1, c2)
            else:
                choice[u][c] = (c2, c1)
                
        # 現在のノードでの 0, 1, 2 のランクを決定するためのソート用キー作成
        keys = []
        for c in range(3):
            pair = choice[u][c]
            # (左部分木のランク, 右部分木のランク, 対象の文字)
            keys.append((rank_val[L][pair[0]], rank_val[R][pair[1]], c))
            
        keys.sort()
        for i, item in enumerate(keys):
            c = item[2]
            rank_val[u][c] = i

    # 3. トップダウンでの文字列復元と出力
    root = 2 * N - 1
    chars = ['R', 'P', 'S']
    
    # f(S)=R, f(S)=P, f(S)=S の順に処理（0, 1, 2 の順）
    for target_c in range(3):
        ans = [0] * (N + 1)
        stack = [(root, target_c)]
        
        while stack:
            u, c = stack.pop()
            if u <= N:
                ans[u] = c
            else:
                L = left_child[u]
                R = right_child[u]
                c_L, c_R = choice[u][c]
                # 深さ優先探索で割り当てを降ろしていく
                stack.append((R, c_R))
                stack.append((L, c_L))
                
        print("".join(chars[ans[i]] for i in range(1, N + 1)))

if __name__ == '__main__':
    solve()
0