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