概要 文字列S(|S|<=50)が与えられる。この文字列から異なる文字の2つ組を取り除く処理を繰り返していき最後に残る可能性のある文字の集合を求めろ。 解法 文字cが最後に残る可能性があるかどうかについて考える。文字c以外を全て消せるかどうか判定できれば…

問題ページ C - ABCAC 公式解説のaとcを高速に求める方法について 解法 aとcをそれぞれ求めたあと a>0 && c>0 && a+c>=|y| を満たしていればABCACが構成できる文字列ABCの組み合わせは a+c-|y|+1 通りある。 SAとlcp配列とRMQ SAとlcp配列を構築する。rank[s…