🙌

ARC 109 | C - Large RPS Tournament

2020/12/27に公開

問題

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

解法

2^k1 \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;
}

参考

Discussion