AGC032 A問題
問題
文字列S（長さN）の部分文字列で、すべて異なる文字からなるものは何個あるか。
解法
入力例 2 3 baa 出力例 2 5 b, a (2通り), ba (2通り)の合計5通りが答えとなります。
上記サンプルのように同一文字列の重複もカウントすることに注意。
->ある文字の出現数1回以下の制限で、すべての組み合わせを数え上げる必要がある。
例えば、S=bacaのときは
b,ba,bc,ba,bac,bca a,ac c,ca a
の11通り。
'a'の出現パターンについてみると、S[1]=aを使う場合とS[3]=aを使う場合でなんとなくペアができることに気付く。
- S[1]=aを使う場合
ba bac a ac
- S[3]=aを使う場合
ba bca a ca
あとはaを使わないパターンで、これは上からaを抜いたケースで両者で一致している。
- aを使わない場合
b bc 空文字 c
空文字を含めた12通りをaの状態でグループ分けできる。
すなわち「どこのaを使うか」と「aを使わない」の状態があり、この例では3つの状態があった。
答えは4*3状態=12から空文字を抜いた11通り。
以上を一般化すると、文字cの個数NcについてNc+1通りの状態が存在し、 各文字について独立に考え、すべての積から空文字分を引いたものが答え。
シンプルな考え方
小難しく考えず、桁数分のbitを考えるとシンプル。（N個のbit。文字列は(2N-1)通りになる。）
同じ文字のbitを同時に立ててはいけない、という制限で何通りのbitの立て方があるか。
->ある文字cの個数をNcとすれば、cのbitの立て方はNc+1通り(Nc箇所＋bitを立てない)。
よって、c='a'~'z'についてΠ(Nc+1)-1（空文字はカウントしない）が答え。
考察失敗例
DFSで前から見ていけばいいかな。でも文字の出現管理の実装めんどくさそうだし計算量的にも怪しいな。じゃあ数学的な問題か。総数から重複分を引いていくのはどうだろうか。・・・解法みえず、複雑になりすぎてあきらめる。
DPでもDFSでも通るっぽいし粘るべきだったかも？
