ARC 109 | C - Large RPS Tournament

문제.

해법

코드

#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;
}

참고 자료