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

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

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

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

問題概要

制約

解法 (1)：DP

コード

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

コード