ARC 109 | C - Large RPS Tournament

問題

https://atcoder.jp/contests/arc109/tasks/arc109_c

解法

$2^k$で$1 \leq n,k \leq 100$なので参加人数は大きくなり愚直にやるとTLEになってしまう。

$s$が入力例1のようにRPSだとすると以下のようになり同じ勝者の繰り返しになる。

よって$s$の文字数が偶数になるようにしてトーナメントの結果を1から$k$まで配列におさめ次のトーナメントに利用すれば最終的な勝者がもとまる。

コード

実装時のTips

• $n$が奇数だと実装しにくいので、$n$が奇数のときは$ss$として$n$を偶数として考える
• じゃんけんの勝敗はネストされたunordered_mapを使用
• DPというか若干貪欲法

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

unordered_map<char, unordered_map<char, char>> mp = {
    {'R', {{'R', 'R'}, {'P', 'P'}, {'S', 'R'}}},
    {'S', {{'S', 'S'}, {'R', 'R'}, {'P', 'S'}}},
    {'P', {{'P', 'P'}, {'R', 'P'}, {'S', 'S'}}},
};

int main() {
  ll n, k;
  string s;
  cin >> n >> k >> s;
  if (n % 2 == 1) {
    // nが奇数だと計算しにくいので偶数にする
    s = s + s;
  }
  n = s.size();
  // dp[k][i] = k回目のじゃんけんの勝者を入れる
  vector<vector<char>> dp(k + 1, vector<char>(n));
  for (int i = 0; i < n; i++) {
    dp[0][i] = s[i];
  }
  // 下からi番目のトーナメントの勝者をうめていく
  for (int i = 1; i <= k; i++) {
    // 半分記録する
    for (int j = 0; j < n / 2; j++) {
      dp[i][j] = mp[dp[i - 1][2 * j]][dp[i - 1][2 * j + 1]];
    }
    // 残りは左と同じ
    for (int j = n / 2; j < n; j++) {
      dp[i][j] = dp[i][j - n / 2];
    }
  }
  cout << dp[k][0] << endl;
}

参考