Topcoderこれまで全然やっていなかったSRMの過去問埋めをぼちぼちやっていこうという気持ちになりまして、せっかくだから解いた問題に関しては記録をつけていこうと思います。Easyを新しいものからやっていく予定です。この1回で飽きる可能性もありますがその時は察してください。記事の形式はkmjpさんのブログの影響をめちゃめちゃ受けています(僕はkmjpさんのブログをめちゃめちゃ見過ぎているので)。次の操作を行って得られる文字列のうち、括弧の対応が正しくなるものは何通りか。s2のうち空でないものをひとつ選び、選んだ方の先頭の文字を削除して新文字列の末尾に加える。これを両方の文字列が空になるまで続ける。開かれている括弧の数)でdpしたくなるが、それだと25003で間に合わない。s2から何文字取ったかの2つだけ見ればよいことがわかってO(|S|^2)。解けてみれば至って普通のdpなんですが、3乗から2乗に落とすのにちょっと困ってしまいました。(1)はてなブログをはじめよう!fluffyowlさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。