ARC109 C - Large RPS Tournament

問題

atcoder.jp

解法

メモ化しながら再帰的に解く。

s="RPS", k=4の例。 トーナメント参加者の出す手は文字列sを周回して決まっていくため、同じパターンが出現する。 テーブルを以下のように定義し、一度計算した値を格納していく。

dp[k][i] = f(dp[k-1][i],dp[k-1][i+2^(k-1)]);
//f(a,b):aとbがじゃんけんして勝った手

2^(k-1)の部分はkが大きい場合にオーバフローしてしまうので、modを取って前計算しておく。

コード

string s;
int n,k;
vector<vector<char>> dp;
vector<int> pow2;

bool comp(char a, char b){
  if(a == 'R') return (b == 'S');
  if(a == 'S') return (b == 'P');
  else return (b == 'R');
}

char f(char a, char b){
  if(comp(b,a)) return b;
  else return a;
}


char dfs(int k, int i){
  if(k == 0) return s[i];
  if(dp[k][i] != '?') return dp[k][i];
  char L = dfs(k-1,i);
  char R = dfs(k-1,(i+pow2[k-1])%n);
  return dp[k][i] = f(L,R);
}

int main() {
  cin >> n >> k;
  cin >> s;
  pow2.assign(n+1,1);
  rep(i,n)pow2[i+1]=pow2[i-1]*2%n;
  dp.assign(k+1,vector<char>(n+1,'?'));
  char ans = dfs(k,0);
  cout<<ans<<endl;
  return 0;
}