結果

問題 No.3673 未来予知
コンテスト
ユーザー harurun
提出日時 2026-09-02 03:25:27
言語 PyPy3
(7.3.23 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 75 ms / 200 ms
+ 86µs
コード長 1,994 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 230 ms
コンパイル使用メモリ 96,208 KB
実行使用メモリ 97,812 KB
最終ジャッジ日時 2026-09-04 23:09:13
合計ジャッジ時間 4,812 ms
ジャッジサーバーID
（参考情報） 		judge6_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys

MASK = 0xFFFFFFFF


def next_state(x):
    x ^= (x << 13) & MASK
    x ^= x >> 17
    x ^= (x << 5) & MASK
    return x & MASK


def next_symbolic(x):
    y = x[:]
    for i in range(13, 32):
        y[i] ^= x[i - 13]
    x = y

    y = x[:]
    for i in range(15):
        y[i] ^= x[i + 17]
    x = y

    y = x[:]
    for i in range(5, 32):
        y[i] ^= x[i - 5]

    return y


def hand_value(c):
    if c == 'R':
        return 0
    if c == 'S':
        return 1
    if c == 'P':
        return 2
    return 3  # X


def recover_initial_state(t):
    symbolic = [1 << bit for bit in range(32)]

    equations = []

    for c in t:
        symbolic = next_symbolic(symbolic)
        value = hand_value(c)

        equations.append(symbolic[0] | ((value & 1) << 32))
        equations.append(symbolic[1] | (((value >> 1) & 1) << 32))

    pivot_row = [-1] * 32

    row = 0
    m = len(equations)

    for col in range(32):
        selected = -1

        for i in range(row, m):
            if (equations[i] >> col) & 1:
                selected = i
                break

        if selected == -1:
            continue

        equations[row], equations[selected] = equations[selected], equations[row]
        pivot_row[col] = row

        pivot = equations[row]

        for i in range(m):
            if i != row and ((equations[i] >> col) & 1):
                equations[i] ^= pivot

        row += 1

    initial = 0

    for col in range(32):
        r = pivot_row[col]
        if r != -1 and ((equations[r] >> 32) & 1):
            initial |= 1 << col

    return initial


def main():
    input = sys.stdin.readline

    T = input()
    N = int(input())

    state = recover_initial_state(T)

    for _ in range(100):
        state = next_state(state)

    winning_hand = "XRSP"
    answer = []

    for _ in range(N):
        state = next_state(state)
        answer.append(winning_hand[state & 3])

    print(''.join(answer))


if __name__ == "__main__":
    main()
0