Subtask 1:

Với mỗi $s$, tìm mọi $i$ thỏa mãn $i$ là submask của $s$ (nói cách khác, $s$ $\texttt{AND}$ $i = i$), và tổ chức giải đấu theo yêu cầu của đề bài.

Độ phức tạp: $\mathcal O(2^n \times 2^n) = \mathcal O(4^n)$

Code tham khảo:

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

using ll = long long;
using ld = long double;

int encode(char c){
    switch (c){
        case 'R': return 0;
        case 'P': return 1;
        case 'S': return 2;
    }
    exit(-1);
}

char decode(int x){
    switch (x){
        case 0: return 'R';
        case 1: return 'P';
        case 2: return 'S';
    }
    exit(-1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string sa;
    cin >> sa;
    vector <int> a(1 << n);
    for (int i = 0; i < (1 << n); i++){
        a[i] = encode(sa[i]);
    }

    array <array <int, 3>, 3> match{{
        {0, 1, 0},
        {1, 1, 2},
        {0, 2, 2}
    }};

    for (int i = 1; i < (1 << n); i++){
        int cur = -1;
        for (int j = 0; j < (1 << n); j++){
            if ((i & j) == j){
                if (cur == -1){
                    cur = a[j];
                }
                else{
                    cur = match[cur][a[j]];
                }
            }
        }
        cout << decode(cur);
    }
    cout << "\n";
}

Subtask 2:

Bổ đề: Số cặp $(s, i)$ thỏa mãn $0 \le i \le s < 2^n$ và $i$ là submask của $s$ là $3^n$.

Chứng minh: Với mỗi bit $b$ từ $0$ đến $n - 1$, chỉ có $3$ cặp bit có thể cho bit thứ $b$ của $s$ và $i$ là $(0, 0)$, $(1, 0)$, và $(1, 1)$.

Vậy ta chỉ cần một cách làm thông minh để chỉ truy cập duy nhất các submask của $s$, cụ thể như sau:

for (int i = s; i > 0; i = (i - 1) & s){
    // do something
}
// xử lí riêng trường hợp i = 0

Code tham khảo:

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

using ll = long long;
using ld = long double;

int encode(char c){
    switch (c){
        case 'R': return 0;
        case 'P': return 1;
        case 'S': return 2;
    }
    exit(-1);
}

char decode(int x){
    switch (x){
        case 0: return 'R';
        case 1: return 'P';
        case 2: return 'S';
    }
    exit(-1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string sa;
    cin >> sa;
    vector <int> a(1 << n);
    for (int i = 0; i < (1 << n); i++){
        a[i] = encode(sa[i]);
    }

    array <array <int, 3>, 3> match{{
        {0, 1, 0},
        {1, 1, 2},
        {0, 2, 2}
    }};

    for (int i = 1; i < (1 << n); i++){
        vector <int> b;
        for (int j = i; j > 0; j = (j - 1) & i){
            b.emplace_back(a[j]);
        }
        int cur = a[0];
        for (int idx = ssize(b) - 1; idx >= 0; idx--){
            cur = match[cur][b[idx]];
        }
        cout << decode(cur);
    }
    cout << "\n";
}

Subtask 3:

Do đề bài muốn ta tìm kết quả của mọi submask của $s$ với mọi $s$, nên một hướng nghĩ hiển nhiên ở đây là dùng SOS DP.

Cụ thể hơn, ta định nghĩa $dp[s][x]$ là kết quả thắng của giải đấu tương ứng với $s$ nếu người đầu tiên (người này coi như là người đứng ở vị trí $-1$ và chơi trước toàn bộ các học sinh). Khi thực hiện SOS DP, ta cập nhật DP như sau:

dp[i][x] = dp[i][dp[i ^ (1 << bit)][x]];

Kết quả cuối cùng với mỗi $s$ là $dp[s][a[0]]$.

Nhận xét của tác giả: Từ bài này, ta có thể nhận ra SOS DP không nhất thiết chỉ có thể thực hiện thông qua phép cộng trên số nguyên, mà có thể mở rộng ra nhiều đối tượng khác. Trong lí thuyết nhóm, thì tập các đối tượng đó chỉ cần là một semigroup, do ta chỉ cần điều kiện là phép tính của ta thỏa mãn tính chất kết hợp.

Code tham khảo:

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

using ll = long long;
using ld = long double;

int encode(char c){
    switch (c){
        case 'R': return 0;
        case 'P': return 1;
        case 'S': return 2;
    }
    exit(-1);
}

char decode(int x){
    switch (x){
        case 0: return 'R';
        case 1: return 'P';
        case 2: return 'S';
    }
    exit(-1);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    string sa;
    cin >> sa;
    vector <int> a(1 << n);
    for (int i = 0; i < (1 << n); i++){
        a[i] = encode(sa[i]);
    }

    array <array <int, 3>, 3> match{{
        {0, 1, 0},
        {1, 1, 2},
        {0, 2, 2}
    }};

    vector <array <int, 3>> dp(1 << n);
    for (int i = 0; i < (1 << n); i++){
        for (int x = 0; x < 3; x++){
            dp[i][x] = match[x][a[i]];
        }
    }
    for (int bit = 0; bit < n; bit++){
        for (int i = 0; i < (1 << n); i++){
            if (not (i >> bit & 1)){
                continue;
            }
            int j = i ^ (1 << bit);
            array <int, 3> new_dp;
            for (int x = 0; x < 3; x++){
                new_dp[x] = dp[i][dp[j][x]];
            }
            dp[i] = new_dp;
        }
    }

    for (int i = 1; i < (1 << n); i++){
        cout << decode(dp[i][a[0]]);
    }
    cout << "\n";
}