けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 109 C - Large RPS Tournament (緑色, 500 点)

DP でやったけど、もっと楽にできたみたい

問題概要

長さ  N の文字列  S と、正の整数  K が与えられる。 2^{K} 人がジャンケンのトーナメント戦を行う。

 S は "R", "P", "S" のみからなる文字列で、"R" はグー、"P" はパー、"S" はチョキを表す。 i (0-indexed) 人目の出す手は  i N で割ったあまりを  r として、常に  S_{r} である。

トーナメントの決勝戦での勝者の出す手を求めよ。

制約

  •  1 \le N, K \le 100

解法 (1):DP

次のような再帰関数を用意したくなった。

// 先頭プレイヤーが S[offset] で始まる部分トーナメントを考える
// 2^k 人の勝者を出力する
func(int offset, int k) {
    if (k == 0) return S[offset];
    offset2 を、offset から 2^(k-1) だけ進めた index を N で割ったあまりとする 
    char zenhan = func(offset, k-1);
    char kouhan = func(offset2, k-1);
    return which_win(zenhan, kouhan);
}

このままでは計算量が爆発してしまうが、メモ化すれば  O(NK) の計算量となる。

コード

#include <bits/stdc++.h>
using namespace std;

// a < b か?
bool comp(char a, char b) {
    if (a == 'R') return (b == 'P');
    else if (a == 'P') return (b == 'S');
    else return (b == 'R');
}
// a と b のどちらが勝つか?
char which(char a, char b) {
    if (comp(a, b)) return b;
    else return a;
}

vector<long long> two;
vector<vector<char>> dp;
char solve(int N, const string &S, int K, int offset) {
    if (K == 0) return S[offset];
    if (dp[K][offset] != '?') return dp[K][offset]; 
    long long offset2 = (offset + two[K-1]) % N;
    char zenhan = solve(N, S, K-1, offset);
    char kouhan = solve(N, S, K-1, offset2);
    return dp[K][offset] = which(zenhan, kouhan);
}

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    two.assign(K+1, 1);
    for (int n = 0; n < K; ++n) two[n+1] = two[n] * 2 % N;
    dp.assign(K+1, vector<char>(N+1, '?'));
    cout << solve(N, S, K, 0) << endl;
}

解法 (2):S を 2 倍サイズにしながらシミュレーション

 S を 2 つ連結した文字列を  T 人とする。実は  2^{K} 人による 1 回戦の結果は、

  •  T を左から 2 個ずつ区切って、勝者を並べてできる、長さ  N の文字列を  U とすると
  •  U の繰り返しによって表現できる

とういことがわかる。 U を再び  S とおいて、同様の処理を繰り返すだけで答えが求められる。計算量は DP と同じく  O(NK) となる。

コード

#include <bits/stdc++.h>
using namespace std;

// a < b か?
bool comp(char a, char b) {
    if (a == 'R') return (b == 'P');
    else if (a == 'P') return (b == 'S');
    else return (b == 'R');
}
// a と b のどちらが勝つか?
char which(char a, char b) {
    if (comp(a, b)) return b;
    else return a;
}

int main() {
    int N, K;
    string S;
    cin >> N >> K >> S;
    
    auto run = [&]() -> void {
        string T = S + S;
        S = "";
        for (int i = 0; i < N*2; i += 2) S += which(T[i], T[i+1]);
    };
    for (int k = 0; k < K; ++k) run();
    cout << S[0] << endl;
}