Google Code Jam 2019 Round1C : Robot Programming Strategy

問題. Robot Programming Strategy

人でじゃんけんによるトーナメント戦を行う．相手は 人いて 番目の人はどんな対戦相手でも文字列 で表される戦略にしたがって手を出す．初手は の1番目の手を出して，引き分けなら2番目と勝敗がつくまでじゃんけんをする（引き分けの回数が の長さを越したら1番目から繰り返す）．引き分けが 回超えたらランダムに勝者を決める．
対戦相手 人の手が事前に分かるときに，どんな組合せでも優勝することができるような戦略を求めよ．そのような戦略が存在しない場合は "IMPOSSIBLE" と出力せよ．ただし，その戦略が表す文字列の長さは 1 以上 500 以下とする．

制約： ，　

解法

どんな組合せでも優勝できるような戦略が存在するということは，戦略 によってすべての対戦相手に勝つことができるということである．したがって， 人の対戦相手と並列に最大で 500 回までじゃんけんを行いながら戦略を決めることを考える．
回目のじゃんけんで相手の手の種類が 3 種類あるときは，どのような手を出して勝つことができないので答えは "IMPOSSIBLE" である．相手の手の種類が 1 種類のときは，その手に勝つ手を 回目で選ぶことによって優勝することができる．この場合はこれ以降じゃんけんをする必要はない．最後に，相手の手の種類が 2 種類のときは，引き分けとなる手を選択することによって 回目のじゃんけんに進むことができる．このとき，出した手によって勝つことができる相手が少なくとも 1 人いるが，そのような対戦者は 回目以降で対戦者として考慮する必要はない．このように戦略を決めて引き分けが 500 回を超えたなら答えは "IMPOSSIBLE" となる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

/********************************************************************/
class Solver {
public:
    Solver(int _n) : num_case(_n) {}

    void input() {
        cin >> n;
        c.resize(n);
        for (int i = 0; i < n; ++i) cin >> c[i];
    }
    void solve();
    void print() {
        cout << "Case #" << num_case << ": ";
        if (find_ans) cout << ans << '\n';
        else cout << "IMPOSSIBLE\n";
    }

private:
    // define variable
    const int num_case;
    string ans;
    bool find_ans;
    int n;
    vector<string> c;
};

void Solver::solve() {
    vector<bool> res(n, true);

    for (int i = 0; i < 500; ++i) {
        bool has_r = false, has_s = false, has_p = false;

        for (int j = 0; j < n; ++j) {
            if (!res[j]) continue;
            const char hand = c[j][i % c[j].size()];
            if (hand == 'R') has_r = true;
            else if (hand == 'S') has_s = true;
            else has_p = true;
        }

        if (!has_r && !has_s && !has_p) { find_ans = true; return ; }
        if (has_r && has_s && has_p) { find_ans = false; return; }

        if (has_r) {
            if (!has_s && !has_p) { ans += "P"; find_ans = true; return ; }
            else if (has_s) {
                ans += "R";
                for (int j = 0; j < n; ++j)
                    if (res[j] && c[j][i % c[j].size()] == 'S') res[j] = false;
            }
            else if (has_p) {
                ans += "P";
                for (int j = 0; j < n; ++j)
                    if (res[j] && c[j][i % c[j].size()] == 'R') res[j] = false;
            }
        }
        else if (has_s) {
            if (!has_p) { ans += "R"; find_ans = true; return ;}
            else {
                ans += "S";
                for (int j = 0; j < n; ++j)
                    if (res[j] && c[j][i % c[j].size()] == 'P') res[j] = false;
            }
        }
        else if (has_p) {
            ans += "S";
            find_ans = true;
            return ;
        }

    }
    find_ans = false;
}
/********************************************************************/

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(4) << setiosflags(ios::fixed);

    int T; cin >> T;
    for (int i_case = 1; i_case <= T; ++i_case) {
        Solver s(i_case);
        s.input();
        s.solve();
        s.print();
    }

    return 0;
}

某アイドルグループのじゃんけん大会かな