SRM423 Div2Med MagicWords
問題概要
アルファベットの大文字で構成された vector
制約
- 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; } };