読者です 読者をやめる 読者になる 読者になる

SRM423 Div2Med MagicWords

問題概要
アルファベットの大文字で構成された vector が与えられる。この要素の順列から生成される文字列Sのうち、Sを1文字ずつシフトするように回転させたときちょうど K 回転となるものの数を答えよ。

制約

  • vector の要素は 1 〜 8
  • 各文字列は 20 文字まで

解法
next_permutation() × rotate() で計算が間に合う。rotate() の最悪計算量はO(N)なので、計算量は 8!*(20^2) =θ(10^7) なので O(10^8) で抑えられる。(計算量の記法はこんなので正しいのかわからない)

class MagicWords {
public:
  int count(vector <string> S, int K) {
    string raw;
    
    int const N = S.size();
    
    int per[N]; for(int i=0; i<N; i++) per[i] = i;
    
    int ans = 0;
    
    do {
      string raw;
      for(int i=0; i<N; i++) {
        raw += S[per[i]];
      }
      
      string work = raw;
      int const M = raw.size();
      int cnt = 0;
      for(int i=0; i<M; i++) {
        rotate(work.begin(), work.begin()+1, work.end());
        cnt += raw == work;
      }
      //cout << cnt << endl;
      ans += cnt == K;
      
    } while(next_permutation(per, per+N));
    
    return ans;
  }
};