C - Palindrome Concatenation - うにゅーん、って感じだ

問題はこちらindeednow-finalb-open.contest.atcoder.jp

なぜこの問題かというと、コード祭り練習会の問題(AtCoder Problems)で一番なるほどなぁ、面白いなぁと思ったからです、はい。

どこが面白いかというと、一見めっちゃいかつそうな問題なのですが、解法を考えていくと思ったより素直な考え方で解けて、思ったより素直なコードに落とし込める、って感じなとこです、はい。

で、解法としては、まぁDPです。

dp[i] を「i番目までの文字を作るのにかかる最小コスト」とすると、

dp[i] = (0 < j < i)における (dp[j] + {j + 1番目からi番目までの文字を作るのにかかる最小コスト}) のmin

となります。

でも{j + 1番目からi番目までの文字を作るのにかかる最小コスト}ってが出なくない？って話なんですが、これについては、実はj + 1番目からi番目までという連続部分文字列が回文のときだけ考えてあげればよいです。
回文でない場合はどこかに区切りがあって、そこで切られた場合については別のjでちゃんと考慮がなされているので、結局すべてのjにおいて残りの文字列が回文のときのみ、コストを計算して比較をしてあげればよいです。

ってことは、i を 1 ~ n で回してあげて、その中で j を 0 ~ i - 1 で回してあげて、その中で j + 1 から i の文字列が回文かどうかを判定し、回文だったらそのコストを足して比較、ってすればよいのですね！！！

って書いたコードがこちらindeednow-finalb-open.contest.atcoder.jp

はい。TLEです。このコードでは回文判定が ${ O(n) }$ なので、全体で ${ O(n^3) }$ , n = 5000 なので間に合うわけがありません。当然の結果です。

このコードでは回文か判定する関数 kaibun(l, r) が (l, r) = (0, 1), (0, 2), (1, 2), (0, 3), (1, 3)... ととても規則的に呼ばれているので、適当に今までの結果を使ってあげれば回文判定が ${ O(1) }$ でできます。うれしい。
私は kaibun(l, r) = kaibun(l + 1, r - 1) && s[l] == s[r] を用いました。
これをメモ化再帰っぽく（実際には再帰は1回で止まる）書けば完了です。

計算量は ${ O(n^2) }$ , n = 5000 なので2500万ですね、遅い言語で重い処理をしてると1000msを超えてきそうな数字ですかね。
私も最初640ms出て、用いる配列の大きさを半分にしたら380msになりました。納得いかねぇ。

てなわけで最終的なコードはこちら。関数呼び出しに時間かかってんのかなと思って関数捨てたがあんま速度変わらず逆に少しごちゃっとしてしまった。indeednow-finalb-open.contest.atcoder.jp

DPつよくなりたいしDPコンチャレンジを再開するかな……