#1154504 (C++23) No.3510 RPS Eliminations

• 問題: No.3510 RPS Eliminations
• ユーザー: Nzt3
• 提出日時: 2026-03-29 05:39:42
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 111 ms / 2,000 ms
• コード長: 5,125 bytes
• コンパイル時間: 1,877 ms
• コンパイル使用メモリ: 168,892 KB
• 実行使用メモリ: 45,244 KB
• 最終ジャッジ日時: 2026-04-17 19:50:18
• 合計ジャッジ時間: 8,051 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

ファイルパターン	結果
sample	AC * 1
other	AC * 28

ソースコード

// Gemini 3
#include <iostream>
#include <vector>
#include <string>
#include <array>

using namespace std;

const long long INF = 2e18; // Kの最大値 10^18 をカバーする十分大きな値

// オーバーフローを防ぐ加算
long long add(long long a, long long b) {
    if (a + b >= INF) return INF;
    return a + b;
}

// オーバーフローを防ぐ乗算
long long mul(long long a, long long b) {
    if (a == 0 || b == 0) return 0;
    if (INF / a < b) return INF;
    return a * b;
}

// 2のべき乗 (x >= 60 は INF とする)
long long P2(int x) {
    if (x >= 60) return INF;
    return 1LL << x;
}

// 辞書順に対応するマッピング: 0=P, 1=R, 2=S
char char_map_out[3] = {'P', 'R', 'S'};

// 削除とK番目の要素取得を O(log N) で行うための BIT (Fenwick Tree)
struct Fenwick {
    int n;
    vector<int> tree;
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
    
    void add(int i, int delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }
    
    int get_kth(int k) {
        int sum = 0, pos = 0;
        for (int i = 18; i >= 0; --i) { // 2^18 > 200000 なので 18 で十分
            if (pos + (1 << i) <= n && sum + tree[pos + (1 << i)] < k) {
                sum += tree[pos + (1 << i)];
                pos += (1 << i);
            }
        }
        return pos + 1;
    }
};

void solve() {
    int N;
    long long K;
    cin >> N >> K;
    vector<int> A(N);
    for(int i = 1; i < N; ++i) {
        cin >> A[i];
    }

    // $K$が最大パターン数 $2^{N-1}$ より大きい場合は構築不可能
    if (K > P2(N - 1)) {
        cout << "-1\n-1\n-1\n";
        return;
    }

    vector<int> left_child(2 * N + 1, 0);
    vector<int> right_child(2 * N + 1, 0);
    vector<int> subtree_size(2 * N + 1, 0);
    for(int i = 1; i <= N; ++i) {
        subtree_size[i] = 1;
    }

    // アクティブな部分文字列を管理し、木を構築
    Fenwick bit(N);
    for(int i = 1; i <= N; ++i) bit.add(i, 1);
    vector<int> node_at(N + 1);
    for(int i = 1; i <= N; ++i) node_at[i] = i;

    int current_nodes = N;
    for(int i = 1; i < N; ++i) {
        int pos_left = bit.get_kth(A[i]);
        int pos_right = bit.get_kth(A[i] + 1);

        int u = node_at[pos_left];
        int v = node_at[pos_right];

        int new_node = ++current_nodes;
        left_child[new_node] = u;
        right_child[new_node] = v;
        subtree_size[new_node] = subtree_size[u] + subtree_size[v];

        bit.add(pos_right, -1);
        node_at[pos_left] = new_node;
    }

    int root = current_nodes;

    // 再帰的に K番目の文字列を復元
    auto solve_dfs = [&](auto& self, int u, array<long long, 3> W, long long k, string& current_ans) -> pair<int, long long> {
        // 葉ノード（1文字の決定）
        if (left_child[u] == 0 && right_child[u] == 0) {
            long long sumW = 0;
            for (int c = 0; c < 3; ++c) {
                if (k <= W[c]) {
                    current_ans += char_map_out[c];
                    return {c, sumW};
                }
                k -= W[c];
                sumW = add(sumW, W[c]);
            }
            return {-1, -1};
        }

        int L = left_child[u];
        int R = right_child[u];

        // 左部分木の各根の文字に対する重み計算
        array<long long, 3> W_L;
        for (int c = 0; c < 3; ++c) {
            W_L[c] = add(W[c], W[(c + 2) % 3]);
        }

        // 1つの左部分木選択あたり、右部分木は 2^(size(R)-1) 個のバリエーションを持つ
        long long completions_per_L = P2(subtree_size[R] - 1);
        long long k_L = (k - 1) / completions_per_L + 1;

        pair<int, long long> res_L = self(self, L, W_L, k_L, current_ans);
        int c_L = res_L.first;
        long long sumW_L = res_L.second;

        long long k_rem = k - mul(sumW_L, completions_per_L);

        // 左の文字 c_L が決まったので、右部分木への重みをセット
        array<long long, 3> W_R = {0, 0, 0};
        W_R[(c_L + 1) % 3] = W[c_L];
        W_R[(c_L + 2) % 3] = W[(c_L + 2) % 3];

        pair<int, long long> res_R = self(self, R, W_R, k_rem, current_ans);
        int c_R = res_R.first;
        long long sumW_R = res_R.second;

        // 勝者（親の文字）の決定
        int c_u = (c_R == (c_L + 1) % 3) ? c_L : (c_L + 2) % 3;

        long long sumW_u = add(mul(sumW_L, completions_per_L), sumW_R);
        return {c_u, sumW_u};
    };

    // 出力順は問題文通り R -> P -> S 
    // ※ 0: P, 1: R, 2: S
    vector<array<long long, 3>> targets = {
        {0, 1, 0}, // 結果を R(1) にしたい
        {1, 0, 0}, // 結果を P(0) にしたい
        {0, 0, 1}  // 結果を S(2) にしたい
    };

    for(int i = 0; i < 3; ++i) {
        string ans = "";
        solve_dfs(solve_dfs, root, targets[i], K, ans);
        cout << ans << "\n";
    }
}

int main() {
    // I/Oの高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    if (cin >> T) {
        while (T--) {
            solve();
        }
    }
    return 0;
}