結果

問題 No.3510 RPS Eliminations
コンテスト
ユーザー 坂東寛斗
提出日時 2026-04-18 10:42:41
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
WA  
実行時間 -
コード長 1,953 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 717 ms
コンパイル使用メモリ 20,824 KB
実行使用メモリ 1,317,932 KB
最終ジャッジ日時 2026-04-18 10:44:34
合計ジャッジ時間 21,254 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other WA * 6 TLE * 14 MLE * 2 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

def main():
    data = sys.stdin.read().split()
    idx = 0
    T = int(data[idx]); idx += 1

    chars = ['P', 'R', 'S']
    CI = {'P':0,'R':1,'S':2}
    beats_idx = [1,2,0]  # P→R, R→S, S→P
    wt = [[0]*3 for _ in range(3)]
    for l in range(3):
        for r in range(3):
            if l!=r: wt[l][r] = l if beats_idx[l]==r else r

    for _ in range(T):
        N,K = int(data[idx]),int(data[idx+1]); idx+=2
        A = [int(data[idx+i]) for i in range(N-1)]; idx+=N-1
        tc_list = [CI['R'],CI['P'],CI['S']]

        # 木の構築
        current = list(range(N))
        tl=[0]*(2*N); tr=[0]*(2*N); par=[-1]*(2*N)
        next_id=N
        for a in A:
            ai=a-1
            l=current[ai]; r=current[ai+1]
            nd=next_id; next_id+=1
            tl[nd]=l; tr[nd]=r
            par[l]=nd; par[r]=nd
            current[ai]=nd; current.pop(ai+1)
        root=current[0]

        # cnt初期化
        cnt=[[1,1,1] for _ in range(next_id)]
        def recompute(nd):
            lc=cnt[tl[nd]]; rc=cnt[tr[nd]]
            r0=r1=r2=0
            for li in range(3):
                lv=lc[li]
                if not lv: continue
                for ri in range(3):
                    rv=rc[ri]
                    if not rv or li==ri: continue
                    w=wt[li][ri]
                    if w==0: r0+=lv*rv
                    elif w==1: r1+=lv*rv
                    else: r2+=lv*rv
            cnt[nd][0]=r0; cnt[nd][1]=r1; cnt[nd][2]=r2
        for nd in range(N,next_id): recompute(nd)

        results = []
        for tc in tc_list:
            if cnt[root][tc]==0:
                results.append("No")
                continue

            # K番目探索
            cnt2 = [c[:] for c in cnt]  # コピーして試行
            # ... (省略: 上記実装と同様)
            results.append("found")

        # 出力
        for r in results: print(r)

main()
0