GCJ Round 2 2016 Problem A. Rather Perplexing Showdown

問題

Dashboard - Round 2 2016 - Google Code Jam

じゃんけんトーナメントをする。各参加者はあまり戦略的でないので, 常に同じ手を出す(例えばグーしか出さない人とかがいる)。なので, もし同じ手を出す人同士が対戦すると, トーナメントが永遠に終わらなくなってしまう。これを避けるために, あなたはトーナメントが終わるような対戦順を考えなければならない。グーを出す人が R 人, チョキを出す人が S 人, パーを出す人が P 人いるとき, 上記の条件を満たす辞書順最小のトーナメント組み合わせを求めよ。

解法

勝者を決めると, その直前に誰と誰の試合が行われていたかがわかります(例えば勝者が パーの人の場合, 直前の試合は グー, パーとわかる)。

なので, 優勝者を決めれば, 必然的にトーナメント出場者の人数は決まります。この人数が出場者の条件に合えば組み合わせが存在することはわかります。

後は辞書順最小を求めるパートですが, これは dp[n][type] = (2^n 人のトーナメントで出す手が type であるような人が優勝するような場合の, 辞書順最小なトーナメントの組み合わせ)を dp メモ化再帰なりを使って求めれば終わりです。

「優勝者から考える」というのがポイントの問題でした。

bool check(string s, int R, int P, int S) {
    int rc = 0, pc = 0, sc = 0;
    for (char c : s) {
        if (c == 'R') rc++;
        if (c == 'P') pc++;
        if (c == 'S') sc++;
    }
    return rc == R && pc == P && sc == S;
}

string dp[15][3];

string dfs(int n, int type) {
    string& ret = dp[n][type];
    if (ret != "") return ret;
    if (n == 0) {
        if (type == 0) return ret = "R";
        if (type == 1) return ret = "P";
        if (type == 2) return ret = "S";
    }
    ret = min(dfs(n-1, type)+dfs(n-1, (type+2)%3), dfs(n-1, (type+2)%3) + dfs(n-1, type));
    return ret;
}

void solve() {
    int N, R, P, S;
    cin >> N >> R >> P >> S;
    string ans = "|";
    string tmp = dfs(N, 0);
    if (check(tmp, R, P, S)) ans = min(ans, tmp);
    tmp = dfs(N, 1);
    if (check(tmp, R, P, S)) ans = min(ans, tmp);
    tmp = dfs(N, 2);
    if (check(tmp, R, P, S)) ans = min(ans, tmp);
    if (ans == "|") {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << ans << endl;
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cout << "Case #" << t << ": "; 
        solve();
    }
    return 0;
}