Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選：C - k-DMC(600)
問題
https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c
制約
考え方
k-DMC数の数え上げは「We Love ABC」に似た要領でDPで求めることができる。また数え上げの対象になるのは の連続区間に含まれる k-DMC数である。よってこれはしゃくとり法で
で求めることができる。
区間の左端を進めるときのDP遷移は、DMCは、s[r] = 'C' のときにそれまでに現れたDMの数に依存し、DMはs[r] = 'M' のときにそれまでに現れたDの数に依存する。
また区間の右端は s[l] = 'D' のときにそれまで現れたMの数だけDMの数が減る。
このようなDP＋しゃくとり法で解を求めることができた。
Submission #3661694 - Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選
どこに着目して考察するべきだったか
すべての連続区間の数え上げなので、しゃくとり法が使えそう。文字列の数え上げは、すでに現れた文字列の数に依存するのでDPっぽく数え上げできる。
