#1182023 (C++23(gcc16)) No.3673 未来予知

• 問題: No.3673 未来予知
• ユーザー: harurun
• 提出日時: 2026-09-02 02:25:59
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 1 ms / 200 ms
• コード長: 3,710 bytes
• コンパイル時間: 1,813 ms
• コンパイル使用メモリ: 184,852 KB
• 実行使用メモリ: 7,968 KB
• 最終ジャッジ日時: 2026-09-04 23:08:02
• 合計ジャッジ時間: 4,024 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_1

ファイルパターン	結果
sample	AC * 3
other	AC * 32

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <bitset>
#include <cstdint>

using namespace std;

int main() {
    // 高速入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string T;
    int N;
    if (!(cin >> T >> N)) return 0;

    // 手を数値(0~3)に変換
    // R:0, S:1, P:2, X:3
    vector<int> target(100);
    for (int i = 0; i < 100; i++) {
        if (T[i] == 'R') target[i] = 0;
        else if (T[i] == 'S') target[i] = 1;
        else if (T[i] == 'P') target[i] = 2;
        else if (T[i] == 'X') target[i] = 3;
    }

    // 各ビットが初期状態のどのビットの線形結合であるかを追跡する
    vector<bitset<32>> forms(32);
    for (int j = 0; j < 32; j++) {
        forms[j].set(j);
    }

    vector<pair<bitset<32>, int>> equations;

    // 線形シミュレーションで1ステップ進めるラムダ式
    auto apply_step = [&](vector<bitset<32>>& f) {
        // s ^= (s << 13)
        bitset<32> shifted13[32];
        for (int j = 0; j < 32; j++) {
            if (j >= 13) shifted13[j] = f[j - 13];
            else shifted13[j].reset();
        }
        for (int j = 0; j < 32; j++) f[j] ^= shifted13[j];

        // s ^= (s >> 17)
        bitset<32> shifted17[32];
        for (int j = 0; j < 32; j++) {
            if (j + 17 < 32) shifted17[j] = f[j + 17];
            else shifted17[j].reset();
        }
        for (int j = 0; j < 32; j++) f[j] ^= shifted17[j];

        // s ^= (s << 5)
        bitset<32> shifted5[32];
        for (int j = 0; j < 32; j++) {
            if (j >= 5) shifted5[j] = f[j - 5];
            else shifted5[j].reset();
        }
        for (int j = 0; j < 32; j++) f[j] ^= shifted5[j];
    };

    // 100回分の手から方程式を収集
    for (int i = 0; i < 100; i++) {
        apply_step(forms);
        // Bit 0 の方程式
        equations.push_back({forms[0], target[i] & 1});
        // Bit 1 の方程式
        equations.push_back({forms[1], (target[i] >> 1) & 1});
    }

    // ガウスの消去法（GF(2)上の掃き出し法）
    int m = equations.size();
    int r = 0;
    vector<int> pivot_col(32, -1);

    for (int c = 0; c < 32; ++c) {
        int sel = -1;
        for (int i = r; i < m; ++i) {
            if (equations[i].first[c]) {
                sel = i;
                break;
            }
        }
        if (sel == -1) continue;
        swap(equations[sel], equations[r]);
        pivot_col[c] = r;

        for (int i = 0; i < m; ++i) {
            if (i != r && equations[i].first[c]) {
                equations[i].first ^= equations[r].first;
                equations[i].second ^= equations[r].second;
            }
        }
        r++;
    }

    // 初期状態を復元
    uint32_t initial_state = 0;
    for (int c = 0; c < 32; ++c) {
        if (pivot_col[c] != -1) {
            int row_idx = pivot_col[c];
            if (equations[row_idx].second) {
                initial_state |= (1U << c);
            }
        }
    }

    // 100回目時点の状態まで進める
    uint32_t curr = initial_state;
    auto next_state_val = [](uint32_t s) {
        s ^= s << 13;
        s ^= s >> 17;
        s ^= s << 5;
        return s;
    };

    for (int i = 0; i < 100; i++) {
        curr = next_state_val(curr);
    }

    // 未来の N 回を予測し、勝つ手を出力する
    // Aliceの手に対する勝ち手: 0(R)->X, 1(S)->R, 2(P)->S, 3(X)->P
    char win_char[4] = {'X', 'R', 'S', 'P'};
    string ans = "";
    for (int i = 0; i < N; i++) {
        curr = next_state_val(curr);
        int alice_hand = curr & 3;
        ans += win_char[alice_hand];
    }

    cout << ans << "\n";

    return 0;
}