betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング お題箱より。 Problem - F - Codeforces 問題概要 整数 と、開き括弧・閉じ括弧からなる文字列 が与えられる。長さ の正しい括弧列であって、その連続部分文字列として をどこかに含むものの個数を で求めよ。 制約 解法 DPを立てる 正しい括弧列の問題は、( を 、) を とした累積和を考えるのが定石です。先頭からの累積和がどの時点でも負にならず、かつ最後に になるものが正しい括弧列です。 今回のように制約が小さく、「数学で一発」みたいな解法が考えづらい場合、以下のようなDPを考えることが多いです。 先頭 文字までを作って、その時点までの累積和が で、かつ○○が であるもの… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F04%2F23%2F224408" title="Codeforces Round #501 (Div. 3) F. Bracket Substring - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-04-23 22:44:08 rich https://betrue12.hateblo.jp/entry/2020/04/23/224408 1.0 100%