mini notes

競技プログラミングの解法メモを残していきます。

ABC171 F - Strivore (600)

問題:F - Strivore

解答:Submission #14600583 - AtCoder Beginner Contest 171

解法:最終的にできた文字列を次のように解釈する。(例:oof)

①o②o③f④
①:o以外の文字からなる長さ0以上の文字列
②:o以外の文字からなる長さ0以上の文字列
③:f以外の文字からなる長さ0以上の文字列
④:長さ0以上の文字列

例えば、最終文字列をmoonwolfとすると①:m、②:空文字列、③:nwol、となる。

すなわち、元の文字列の各文字について、その直前に自分以外の文字が0個以上入るような文字列の分類の仕方を行う。元の文字列の全ての文字が登場すれば、その後はどのような文字が来てもよい(④)。また、例えば①にfが出てきたとしても、最終的にカウントしたいのは「oo」が出てきた後のfであるため、①、②にfが出てくるのは問題ない。

組み合わせ数について。
④の長さを固定する。①~③のそれぞれの長さの組み合わせは重複順列となっている。また文字列の種類について、①~③はその後にくる文字以外の25文字の組み合わせであるため、25K - (|①|+ |②| + |③|)通り、④は26|④|通りの組み合わせがある。これを掛け合わせたものを、④の長さを0~Kまでで計算して足し合わせればよい。