結果
| 問題 | No.3510 RPS Eliminations |
| コンテスト | |
| ユーザー |
 Nzt3
|
| 提出日時 | 2026-04-01 16:35:59 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
AC
|
| 実行時間 | 836 ms / 2,000 ms |
| コード長 | 4,835 bytes |
| 記録 | |
| コンパイル時間 | 229 ms |
| コンパイル使用メモリ | 85,376 KB |
| 実行使用メモリ | 233,216 KB |
| 最終ジャッジ日時 | 2026-04-17 20:02:52 |
| 合計ジャッジ時間 | 21,488 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
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_val = K # nonlocalの代わりにローカル変数として管理
# 各ノードの計算結果（どの手を選択したか）を保持
realized = [-1] * (2 * N - 1)
# スタックには [現在のノード, そのノードに渡されたways, 処理状態] を格納
# 状態: 0=初回訪問, 1=左の子の処理完了後, 2=右の子の処理完了後
root_ways = [0] * 3
root_ways[target] = 1
stack = [[root, root_ways, 0]]
while stack:
# stack[-1] で現在の要素を参照（popはまだしない）
curr = stack[-1]
u, ways, state = curr[0], curr[1], curr[2]
# --- 葉ノード（ベースケース）の処理 ---
if u < N:
stack.pop()
for c in range(3):
if curr_K_val <= ways[c]:
res[u] = c
realized[u] = c
break
curr_K_val -= ways[c]
continue
L = left_child[u]
R = right_child[u]
# --- 内部ノードの処理（状態管理） ---
if state == 0:
# 1. 左の子へ行く前の準備 (ways_L の計算)
ways_L = [0] * 3
# 元のコードの2重ループを定数時間で展開（高速化）
ways_L[0] = min(INF, (ways[0] + ways[2]) * dp[R]) # P
ways_L[1] = min(INF, (ways[0] + ways[1]) * dp[R]) # R
ways_L[2] = min(INF, (ways[1] + ways[2]) * dp[R]) # S
curr[2] = 1 # 状態を更新して左の子をスタックに積む
stack.append([L, ways_L, 0])
elif state == 1:
# 2. 左の子から戻ってきた。次に右の子へ行く準備 (ways_R の計算)
rL = realized[L]
ways_R = [0] * 3
# 勝敗ルールに基づいて realized_L に対応する K 番目の重みを分配
if rL == 0: # 左がPなら、右がRで全体がP、右がSで全体がS
ways_R[1], ways_R[2] = ways[0], ways[2]
elif rL == 1: # 左がRなら、右がPで全体がP、右がSで全体がR
ways_R[0], ways_R[2] = ways[0], ways[1]
else: # 左がSなら、右がPで全体がS、右がRで全体がR
ways_R[0], ways_R[1] = ways[2], ways[1]
curr[2] = 2 # 状態を更新して右の子をスタックに積む
stack.append([R, ways_R, 0])
else: # state == 2
# 3. 右の子からも戻ってきた。自身の realized を確定させて pop
stack.pop()
realized[u] = win[realized[L]][realized[R]]
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()