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

• 問題: No.3510 RPS Eliminations
• ユーザー: takuma saito
• 提出日時: 2026-04-19 17:39:07
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: RE
• 実行時間: -
• コード長: 3,444 bytes
• コンパイル時間: 2,721 ms
• コンパイル使用メモリ: 351,812 KB
• 実行使用メモリ: 66,688 KB
• 最終ジャッジ日時: 2026-04-19 17:40:03
• 合計ジャッジ時間: 13,485 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge1_1

ファイルパターン	結果
sample	-- * 1
other	RE * 20 TLE * 1 -- * 7

ソースコード

#include <bits/stdc++.h>
using namespace std;

typedef __int128_t i128;
const i128 INF = (i128)2e18;

struct Nd {
    int l = -1, r = -1, p = -1, li = -1;
    i128 dp[3] = {0, 0, 0};
};

int wt[3][3] = {
    {-1, 1, 0},
    {1, -1, 2},
    {0, 2, -1}
};

int ord[] = {1, 0, 2};
char hc[] = {'R', 'P', 'S'};

void solve() {
    int N;
    long long K_raw;
    if (!(cin >> N >> K_raw)) return;
    i128 K_lim = K_raw;

    vector<int> A(N - 1);
    for (int &x : A) cin >> x;

    vector<Nd> t(2 * N + 1);
    vector<int> ps(N + 1), nx(N + 2), pv(N + 2);

    for (int i = 1; i <= N; ++i) {
        ps[i] = i;
        t[i].li = i;
        nx[i] = i + 1;
        pv[i] = i - 1;
    }

    int nn = N + 1;
    for (int i = 0; i < N - 1; ++i) {
        int idx = A[i];
        int u = ps[idx], v = ps[nx[idx]];
        int m = nn++;
        t[m].l = u; t[m].r = v;
        t[u].p = t[v].p = m;
        ps[idx] = m;
        int tg = nx[idx];
        nx[idx] = nx[tg];
        pv[nx[tg]] = idx;
    }

    int rt = nn - 1;

    auto f_dp = [&](auto self, int u) -> void {
        if (t[u].li != -1) {
            for (int i = 0; i < 3; ++i) t[u].dp[i] = 1;
            return;
        }
        self(self, t[u].l);
        self(self, t[u].r);
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (i == j) continue;
                int w = wt[i][j];
                t[u].dp[w] = min(INF, t[u].dp[w] + t[t[u].l].dp[i] * t[t[u].r].dp[j]);
            }
        }
    };
    f_dp(f_dp, rt);

    vector<int> lv(N + 1);
    auto g_lv = [&](auto self, int u) -> void {
        if (t[u].li != -1) { lv[t[u].li] = u; return; }
        self(self, t[u].l);
        self(self, t[u].r);
    };
    g_lv(g_lv, rt);

    auto rec = [&](int gh) {
        if (t[rt].dp[gh] < K_lim) {
            cout << -1 << endl;
            return;
        }

        i128 ck = K_lim;
        vector<vector<i128>> cdp(nn, vector<i128>(3));
        for (int i = 1; i < nn; ++i) for (int j = 0; j < 3; ++j) cdp[i][j] = t[i].dp[j];

        string res = "";
        for (int i = 1; i <= N; ++i) {
            int ln = lv[i];
            for (int h : ord) {
                vector<i128> od = cdp[ln];
                for (int j = 0; j < 3; ++j) cdp[ln][j] = (j == h ? 1 : 0);

                int cu = ln;
                vector<pair<int, vector<i128>>> path;
                while (cu != rt) {
                    int pa = t[cu].p;
                    path.push_back({pa, cdp[pa]});
                    fill(cdp[pa].begin(), cdp[pa].end(), 0);
                    int L = t[pa].l, R = t[pa].r;
                    for (int x = 0; x < 3; ++x) {
                        for (int y = 0; y < 3; ++y) {
                            if (x == y) continue;
                            cdp[pa][wt[x][y]] = min(INF, cdp[pa][wt[x][y]] + cdp[L][x] * cdp[R][y]);
                        }
                    }
                    cu = pa;
                }

                if (cdp[rt][gh] >= ck) {
                    res += hc[h];
                    break;
                } else {
                    ck -= cdp[rt][gh];
                    cdp[ln] = od;
                    for (auto &p : path) cdp[p.first] = p.second;
                }
            }
        }
        cout << res << endl;
    };

    rec(0); rec(1); rec(2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}