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

SRM428 Div2Med TheLuckyString

問題
どの隣も同じ文字にならない文字列をLuckyStringと呼ぶ。
入力の文字列sを並び替えたとき、LuckyStringはいくつ生成できるか。
ただし文字列が10文字以下である。

解法
階乗を含むオーダー計算が正しく出来ますかという問題。
10! = 3628800 < 10^7 より、隣同士の比較を計算量10で出来るとしても、全体の計算量は 10^8 より小さくなる。よって、文字列sをソートしてから next_permutation(ALL(s)) をぶん回せば終わり。オーダー計算が出来るなら実装はEasyレベル。

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

#define ALL(c) (c).begin(), (c).end()

class TheLuckyString {
public:
  int count(string s) {
    int result = 0;
    int const N = s.size();
    sort(ALL(s));
    do {
      bool ok = 1;
      for(int i=1; i<N; i++) {
        if(s[i-1] == s[i]) {
          ok = 0;
        }
      }
      if(ok) result ++;
    } while(next_permutation(ALL(s)));
    
    return result;
  }
};