読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

SRM528 div.1 500 SPartition

DP topcoder

問題

SRM528 div.1 500 SPartition
偶数長の文字列sが与えられる。ここからsの各文字を、前から順番にX,Yのどちらかに振り分けていったとき、XとYが一致するような振り分け方は何通りか?

制約

 2 \le |s| \le 40

解法

L=|s|とする。振り分けた後の文字列はL/2であり、20以下なので全て列挙することが可能である。
最終的な文字列が決まった後、振り分け方が何通りあるかを考える。f(x, y):=(Xがx番目でYがy番目であるときの場合の数)を考えるて、以下のコードのようにメモ化再帰すれば解ける。

コード

最大ケースで40ms。これをpythonで実装するとTLEする。

感想

人々のDPのコードを見ていたけど分からなかったが、Editorialのメモ化再帰のコードを見てようやく理解できた