TTPC 2015 G - titech分離

• 問題
• AC

文字の数があわないなどの自明ケースは先に考慮しておく。

実際にtitechという文字列をいくつか作りかけながら、文字列$S$を先頭から走査していくことを考える。たとえばtitという文字列が2つできているときに次がeだったら、どちらに追加しても区別できない。したがって、長さ$x$の列を$\operatorname{dp}[x]$個持っているとして$\operatorname{dp}[0] := Sの長さ/6$と初期化しておけばよく、eを見たら$\operatorname{dp}[3]$を1減らして$\operatorname{dp}[4]$を1増やすという感じで遷移すればよい。ほかの文字についてもだいたい同じで、最後まで走査できたらYesということになる……のだが、問題は文字tで、$0 \rightarrow 1$と$2 \rightarrow 3$の二通りに追加できる。これはDFSで全探索すればよさそう。

しかし、計算量がどうなるかわからなくてしばらく逡巡していた。自明な評価から順に

1. titechは最大で16個作れてこの時tは32個だからDFSの末端の数は$2^{32} \simeq 4 \cdot 10^9$以下。
2. $0 \rightarrow 1$と$2 \rightarrow 3$は同じ回数だけ選ぶ必要があるから$\binom{32}{16} \simeq 6 \cdot 10^8$以下。
3. 最初は$0 \rightarrow 1$、最後は$2 \rightarrow 3$を選ぶ必要があるから$\binom{30}{15} \simeq 1.5 \cdot 10^8$以下。
4. $0 \rightarrow 1$を選んだ回数が常に$2 \rightarrow 3$を選んだ回数以上でなければならないから、カタラン数で$C_{15} \simeq 10^7$以下。

---

逆から貪欲でいいらしい。なんと……