No.3391 Line up Dominoes
一応自力AC。
DPで解く。DPで遷移したときの要素は区間和になることが分かるので、毎回累積和を取って流し込んだ。
PyPyだとMLEになってしまったので、RUSTに直してもらいAC（コンテスト中だとできないが……）。
解説を読むとPyPyでも普通にACできるようなのだが、よく分かっていない。
No.3392 Count 23578 Sequence
自力AC。
階差数列を考えると、回文の個数を数える問題に帰着できるので、Manacherを使って解ける。
しばらく気付けなかったが、階差数列を考えると気付けて良かった。
0 件のコメント:
コメントを投稿