F - Multiplayer Rock-Paper-Scissors

2 secs 1024 MB

kusirakusira

問題

提出

テストケース

解説

$f(g, c, p)$ を、グーが $g$ 人、チョキが $c$ 人、パーが $p$ 人のときの勝ち手（引き分けなら $D$ ）を返す関数とします。この関数自体は $O(1)$ で計算できます。

クエリ $i$ について、 $L_i, \ldots, R_i$ 番目の人のうち、グーを出した人の人数を $g$ 、チョキを出した人の人数を $c$ 、パーを出した人の人数を $p$ とします。

あなたがグーを出したときに大人数じゃんけんに勝てるかどうかを考えます。このとき、 $f(g + 1, c, p)$ が $G$ ならば勝つことができます。なぜならば、 $L_i, \ldots, R_i$ 番目の人とあなたのうち、グーを出した人の人数は $g + 1$ 人で、チョキ・パーを出した人の人数はそれぞれ $c$ 、 $p$ だからです。同様に、 $f(g, c + 1, p)$ が $C$ ならばチョキを出したときに勝つことができ、 $f(g, c, p + 1)$ が $P$ ならばパーを出したときに勝つことができます。

これより、 $L_i, \ldots, R_i$ 番目の人のうち、グー・チョキ・パーをそれぞれ出す人の人数を高速にもとめられればこの問題を解くことができます。これは累積和を使うことで $O(1)$ で求めることができます。

C++

xxxxxxxxxx
 
#include<bits/stdc++.h>
using namespace std;
​
int main() {
    int N; cin >> N;
    vector<char> A(N);
    for (auto &a : A) cin >> a;
​
    vector<int> G(N + 1), C(N + 1), P(N + 1);
    for (int i = 0; i < N; i++) {
        if (A[i] == 'G') G[i + 1]++;
        if (A[i] == 'C') C[i + 1]++;
        if (A[i] == 'P') P[i + 1]++;
    }
    for (int i = 0; i < N; i++) {
        G[i + 1] += G[i];
        C[i + 1] += C[i];
        P[i + 1] += P[i];
    }
​
    // グーがg人、チョキがc人、パーがp人のときの勝ち手　引き分けならD
    auto win_hand = [](int g, int c, int p) -> char {
        if (g == 0 && c == 0) return 'P';
        if (g == 0 && p == 0) return 'C';
        if (c == 0 && p == 0) return 'G';
        if (g == 0) {
            if (c <= p) return 'C';
            else return 'P';
        }
        if (c == 0) {
            if (p <= g) return 'P';
            else return 'G';
        }
        if (p == 0) {
            if (g <= c) return 'G';
            else return 'C';
        }
        if (g < c && g < p) return 'G';
        if (c < g && c < p) return 'C';
        if (p < g && p < c) return 'P';
        if (g == c && g < p) return 'G';
        if (g == p && g < c) return 'P';
        if (c == p && c < g) return 'C';
        return 'D';
    };
​
    int Q; cin >> Q;
    while (Q--) {
        int l, r; cin >> l >> r;
        l--; r--;
        int g = G[r + 1] - G[l];
        int c = C[r + 1] - C[l];
        int p = P[r + 1] - P[l];
        vector<char> ans;
        if (win_hand(g + 1, c, p) == 'G') ans.push_back('G');
        if (win_hand(g, c + 1, p) == 'C') ans.push_back('C');
        if (win_hand(g, c, p + 1) == 'P') ans.push_back('P');
​
        if (ans.empty()) {
            cout << -1 << endl;
        } else {
            for (int i = 0; i < (int)ans.size(); i++) {
                cout << ans[i] << (i == (int)ans.size() - 1 ? "\n" : " ");
            }
        }
    }
}

Python

xxxxxxxxxx
 
n = int(input())
A = list(map(str,input().split()))
q = int(input())
​
CG = [0]
CC = [0]
CP = [0]
​
def f(g, c, p, e):
    if(g==0): g = 10**18
    if(c==0): c = 10**18
    if(p==0): p = 10**18
    if(g == c == p):
        return "-1"
​
    m = min(g, c, p)
    if(g == m and c == m):
        if("G" == e):
            ans.append("G")
        return
    if(c == m and p == m):
        if("C" == e):
            ans.append("C")
        return
    if(p == m and g == m):
        if("P" == e):
            ans.append("P")
        return
    if(g == m):
        if("G" == e):
            ans.append("G")
        return
    if(c == m):
        if("C" == e):
            ans.append("C")
        return
    if(p == m):
        if("P" == e):
            ans.append("P")
        return
        
    
for i in range(n):
    if(A[i]=="G"):
        CG.append(CG[-1]+1)
    else:
        CG.append(CG[-1])
    if(A[i]=="C"):
        CC.append(CC[-1]+1)
    else:
        CC.append(CC[-1])
    if(A[i]=="P"):
        CP.append(CP[-1]+1)
    else:
        CP.append(CP[-1])
​
for _ in range(q):
    l, r = map(int,input().split())
    g = CG[r] - CG[l-1]
    c = CC[r] - CC[l-1]
    p = CP[r] - CP[l-1]
    ans = []
    f(g+1, c, p, "G")
    f(g, c+1, p, "C")
    f(g, c, p+1, "P")
    if(len(ans)==0):
        print(-1)
    else:
        print(*ans)