SRM528 div.1 500 SPartition
問題
SRM528 div.1 500 SPartition
偶数長の文字列sが与えられる。ここからsの各文字を、前から順番にX,Yのどちらかに振り分けていったとき、XとYが一致するような振り分け方は何通りか?
制約
解法
L=|s|とする。振り分けた後の文字列はL/2であり、20以下なので全て列挙することが可能である。
最終的な文字列が決まった後、振り分け方が何通りあるかを考える。f(x, y):=(Xがx番目でYがy番目であるときの場合の数)を考えるて、以下のコードのようにメモ化再帰すれば解ける。
コード
最大ケースで40ms。これをpythonで実装するとTLEする。
感想
人々のDPのコードを見ていたけど分からなかったが、Editorialのメモ化再帰のコードを見てようやく理解できた