ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 81 F. Good Contest

Codeforces プログラミング 競技プログラミング

Problem - F - Codeforces

問題概要

n 問の問題からなるコンテストがある。 i 番目の問題の正解者数は、区間 \lbrack l_{i}, r_{i}\rbrack に含まれる整数の中から等確率で決まる。

問題 0, 1, ..., n-1 の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、 \bmod 998244353 で出力せよ。

制約

  • 2 \le n \le 50
  • 0 \le l_{i} \le r_{i} \le 998244351

解法

問題 i の正解者数を x_{i} と書くことにします。確率よりも場合の数のほうが計算しやすいので、条件を満たすような数列 (x_{0}, ..., x_{n-1}) の総数（場合の数）を計算して全事象数で割ることにします。

DPができそうですが、 l_{i}, r_{r} が非常に大きいのが厄介です。座標圧縮ができないか考えましょう。

座標圧縮後に扱いやすくするため、入力の r_{i} に 1 加算して半開区間 \lbrack l_{i}, r_{i}) として考えます。そしてこれらの座標点を 2n 個集めてソートし重複を除いたものが K 個あるとして、これを順に p_{0},p_{1}, ..., p_{K-1} とします。そうすると x の各要素が取りうる値の範囲は区間 \lbrack p_{0}, p_{1}), ..., \lbrack p_{K-2}, p_{K-1}) に分割され、これらは重複しないので扱いやすくなります。

区間 \lbrack p_{j}, p_{j+1}) を「ゾーン j」と呼ぶことにします。各問題 i について、区間 \lbrack l_{i}, r_{i}) が区間 \lbrack p_{j}, p_{j+1}) を含む時、 x_{i} はゾーン j 内に存在し得る（使用可能である）ということになります。

広義単調減少していく数列 (x_{0}, ..., x_{n-1}) は、大まかに描くと以下のような遷移をしていきます。各マスが問題とゾーンの組み合わせで、緑マスがその問題の正解者数 x_{i} が属するゾーンです。

f:id:betrue12:20200201015944p:plain

この数列の個数を、例えば以下のようなDPで数え上げられないか考えてみます。

  • dp\lbrack i \rbrack\lbrack j \rbrack = (x_{0}, ..., x_{i-1}) までが既に決まっていて、 x_{i-1} がゾーン j に含まれるような場合の数

しかしこれはDPの遷移が上手くいきません。 dp\lbrack i \rbrack\lbrack j \rbrack から遷移するときに、 x_{i} でゾーンを変える場合は問題ないのですが、次も同じゾーン j にいるような場合、ゾーン j の中でも x_{i-1} が具体的にいくつだったのかまで分からないと x_{i} が取れる範囲が分からないからです。

これでは面倒なので、連続する複数の x_{i} が同じゾーンに含まれる場合、それを一気に処理してしまうことを考えます。具体的には以下のように、ゾーンの区切りでのみ状態をまとめるようなDPに変更します。

  • dp\lbrack i \rbrack\lbrack j \rbrack = (x_{0}, ..., x_{i-1}) までが既に決まっていて、 x_{i-1} がゾーン j に含まれていて、 x_{i-1} がゾーン j に含まれる最後の値であるような場合の数

このDPの遷移として、「問題 i からゾーン j が始まって、そこからゾーン j が l 問連続して終わる」という事象を考えましょう。

前提として、問題 i から連続する l 問全てにおいてゾーン j が使用可能である必要があります。最初にこれをチェックします。

遷移元は k \gt j である全ての k から、 dp\lbrack i \rbrack\lbrack k \rbrack を全て持ってきて足し合わせたものです。遷移先は dp\lbrack i+l \rbrack\lbrack j \rbrack になります。このときの係数、つまりゾーン j に含まれる l 個の値の組 (x_{i}, ..., x_{i+l-1}) の場合の数を求めましょう。

ゾーン j に属している整数点の個数を L_{j} 個とします。これらの整数を使った要素数 l の広義単調減少数列は、 L_{j} 個の整数から重複を許して順番を区別せずに l 個選び、降順ソートしたものと思うことができます。この重複組合せの選び方と広義単調減少数列は1対1対応するので、その場合の数は _{L_{j}+l-1}C_{l} で求められます。

ここで二項係数を求める際に L_{j} は非常に大きくなり得ますが、 l が十分小さいので以下の式を利用して求めれば良いです。

{}_{N}C_{K} = \frac{N(N-1)\cdots(N-K+1)}{K(K-1)\cdots 1}

これでDPの遷移が計算できます。

以下のコードは i, j, l の3重ループ内で毎回二項係数を求めているので O(n^{4}) になりますが、定数倍も小さいので十分通ります。二項係数を前計算したり l を伸ばしていきながら逐次的に計算すると O(n^{3}) になりますね。

ACコード

Submission #69917823 - Codeforces

yukicoder No.980 Fibonacci Convolution Hard

yukicoder プログラミング 競技プログラミング

No.980 Fibonacci Convolution Hard - yukicoder

変な解き方をしました…。後述するように厳密に正しい解法ではないので、あまりオススメはしません。

解法

0-indexedのほうが楽なので、数列 a を a_{0} = 0, a_{1} = 1, あとは同様の漸化式で定義される数列、としておきます。クエリで与えられた q に対しては 2 を引いて s, t を非負整数とすれば同等の問題になります。

普通のフィボナッチ数列と同様、特性方程式 x^{2} - px - 1 = 0 の解を用いることで一般項を表現することができます。

  • \alpha = \frac{p+\sqrt{p^{2}+4}}{2} とする。
  • \beta = \frac{p-\sqrt{p^{2}+4}}{2} とする。
  • 一般項は、 a_{n} = \frac{1}{\sqrt{p^{2}+4}}(\alpha^{n} - \beta^{n}) と表現できる。

これを踏まえてクエリで q が与えられた時の答えを求めます。先述の通り、この q は入力から 2 引いたものとします。答えは以下のように計算できます。

\displaystyle\frac{1}{p^{2}+4}\left((\alpha^{0}-\beta^{0})(\alpha^{q}-\beta^{q}) + (\alpha^{1}-\beta^{1})(\alpha^{q-1}-\beta^{q-1}) + \cdots + (\alpha^{q}-\beta^{q})(\alpha^{0}-\beta^{0})\right)

\displaystyle =\frac{1}{p^{2}+4}\left((q+1)( \alpha^{q} + \beta^{q}) -2(\alpha^{0}\beta^{q} + \alpha^{1}\beta^{q-1} + \cdots + \alpha^{q}\beta^{0})\right)

ここで (\alpha^{0}\beta^{q} + \alpha^{1}\beta^{q-1} + \cdots + \alpha^{q}\beta^{0}) は等比数列の和の公式を用いてあげることで

\displaystyle\frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta}

と等しいことが分かります。よって答えは以下のように表現できます。

\displaystyle\frac{1}{p^{2}+4}\left( (q+1)( \alpha^{q} + \beta^{q}) -2\frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta}\right)

ただ \alpha, \beta には根号が含まれているのでそのまま \bmod ありの計算をすることはできません。一般項を利用して、なんとかこれらの値を表現できないか考えます。

まず \alpha^{q} + \beta^{q} = \frac{\alpha^{2q} + \beta^{2q}}{\alpha^{q}-\beta^{q}} であることから、これは \frac{a_{2q}}{a_{q}} と等しくなります。

同様に \frac{\alpha^{q+1} - \beta^{q+1}}{\alpha - \beta} は、 \frac{a_{q+1}}{a_{1}} = a_{q+1} と等しくなります。

これで \alpha, \beta を消去できました。答えは以下の式で求められます。

\displaystyle\frac{1}{p^{2}+4}\left( (q+1)\frac{a_{2q}}{a_{q}} -2a_{q+1}\right)

必要な範囲全ての a_{n} を前計算しておいて、各クエリに対してこの式を用いて答えを計算することで、ACすることはできました。

…が、本当は 0 除算が発生し得ることに注意する必要があります。 p^{2}+4 \equiv 0 である場合は \alpha^{q} や \beta^{q} が簡単な式で表現できるようになるので比較的対処しやすいですが、 q=0 以外で a_{q} \equiv 0 であるような場合は厄介だと思います…。

下記コードではこの 0 除算の対応をしていないため、厳密に正しい解法ではありません。

ACコード

#424321 No.980 Fibonacci Convolution Hard - yukicoder

Educational Codeforces Round 81 E. Permutation Separation

Codeforces プログラミング 競技プログラミング

Problem - E - Codeforces

問題概要

※解説と合わせるために0-indexedで表記します。

長さ n の順列 p_{0}, ..., p_{n-1} が与えられる。また p_{i} を移動させるためのコスト a_{i} がそれぞれ与えられる。

この順列に対して以下の処理を行う。

  1. 順列の隣り合う2要素間の境界を自由に選び、左グループと右グループに分ける。このときどちらのグループにも1つ以上の要素が含まれる必要がある。
  2. 要素を自由に選び、別のグループに移動させる操作を0回以上行う。このとき先述のコストが発生する。移動の結果どちらかのグループが空になってもよい。

この処理によって「左のグループの任意の要素は、右のグループの任意の要素よりも小さい」という状態にしたい。そのために必要な合計コストの最小値を求めよ。

制約

  • 2 \le n \le 2\times 10^{5}
  • p_{0}, ..., p_{n-1} は 0, ..., n-1 の順列である
  • 1 \le a_{i} \le 10^{9}

解法

まず、

  • 要素を順列として与えられた順に並べたときに、最初に選ぶ左グループと右グループの境界線をどこにするか（位置の境界線）

を1つに決めたとしましょう。さらに、

  • 要素を数の小さい方から並べ直したときに、移動後の最終状態においてどこまでが左グループに入り、大きい方からどこまでが右グループに入るか（大きさの境界線）

も決めたとします。これを以下のように図示します。

f:id:betrue12:20200130223353p:plain

位置の境界線を決めた直後に、左グループに含まれる要素を青、右グループに含まれる要素を赤に塗っています。最終的には大きさの境界線の左側が全て青に、右側が全て赤になるように色を塗り直す（つまりグループを移動する）必要があるため、そうでない要素の合計コストが必要コストになります。

では位置の境界線を1つに決めた（つまり、各要素の色が決まった）として、大きさの境界線をどのように選べば必要コストを最小にできるでしょうか。

仮に大きさの境界線が一番左にあるとすると、図中の青い要素の合計コストがそのまま必要コストになります。ここから大きさの境界線を1つずつ右にずらしていくと、追い越した要素が赤であればその要素の移動コストのぶん必要コストは増え、青であれば逆に必要コストは減る、という計算になります。

つまり注目すべきは、赤い要素をプラス、青い要素をマイナスと見た時の前からの累積和です。これが一番小さくなるような位置に大きさの境界線を持ってくるのが最適で、青い要素の合計コストにその位置での累積和を足せば必要コストになります。

f:id:betrue12:20200130220610p:plain

これで見通しがクリアになりました。あとは位置の境界線を全て試しながら、それぞれに対する最適値を求めていくことを考えます。

要素を数の小さい方から並べ、赤い要素の移動コストをプラス、青い要素の移動コストをマイナスと見て、区間 \lbrack 0, i) における累積和を取った値を S_{i} と書くことにします。コストを順列の順ではなく要素の値が小さい方から並び替えたものを b_{i} とすると、位置の境界線が左端にある初期状態ではこれは +b_{i} の累積和になります。

位置の境界線を右に1つずらすと、要素のうち1つが赤から青に変わります。この要素の値を p、そのコストを b_{p} とすると、 b_{p} がプラスからマイナスの扱いに変わるので、累積和においては S_{p+1}, ..., S_{n} 全てに -2b_{p} を足すことになります。そして必要コストの最小値は、そのときの青い要素の合計コストに \min(S_{0}, ..., S_{n}) を足したものです。

f:id:betrue12:20200130222223p:plain

これは区間への加算操作と区間に対する最小値取得が可能なデータ構造を用いて処理することができて、遅延伝播セグメント木などで実現することができます。

最初に分けた時にはどちらのグループにも1つ以上の要素が含まれる必要がある、という条件から、位置の境界線としては両端以外の n-1 通りを試すことになります（うっかり端を含めてしまうと答えが必ず 0 になってしまいます）。それぞれに対する必要コスト最小値の、さらに全ての最小値を取ったものが答えです。

ACコード

Submission #69837583 - Codeforces

コード上では A[i] を最初から、位置ではなく要素の値の小さい順に移動コストを並べたもの（上記解説中の b_{i}）として格納しています。

AtCoder Grand Contest 011 E - Increasing Numbers

AtCoder プログラミング 競技プログラミング

E - Increasing Numbers

公式解説と少し違う方法で解いたので記録しておきます。

解法

十進法の桁を、一番下の桁を 0 桁目とするように表記します。 k 桁目は 10^{k} に対応する桁です。

「各桁から 1 を引く回数」の条件への言い換え

非負整数が増加的であることは、「1を任意個並べたような整数」を9個以下足し合わせたものとして表現できることと同値です。このことからこの問題を以下のように言い換えることができます。

  • 与えられた整数 N を、「1 を任意個並べたような整数を引く」という操作をできるだけ少ない回数行って 0 にせよ。その回数が T 回であるとき、 \lceil\frac{T}{9}\rceil が答えとなる。

これをさらに、各桁から 1 が引かれた合計回数に注目して言い換えます。「1 を任意個並べたような整数を引く」という操作 T 回によって k 桁目から 1 が引かれた合計回数を t_{k} とすると、 t_{0} = T かつ数列 t_{0}, t_{1}, ... は広義単調減少となります。逆にこのような数列には必ず対応する操作列が存在します。

よってこの数列を、 t_{0} をなるべく小さくするように構成していくことを目指しましょう。

数列の構成方法

方針としては下の桁から見ていきます。 k 桁目を見るときには

  • t_{0}, ..., t_{k} が広義単調減少になっている
  • k 桁目までの操作によって、 N の 0, ..., k 桁目が全て 0 になっている

ようにしながら、 t_{0} をなるべく小さく保ちます。そして後の桁で単調減少性を保てなくなったら、見終わった桁を最小限のところまで遡って回数を増やし、単調減少性を保つようにします。

N の k 桁目の値を a_{k} と書くことにします。具体的に k 桁目から 1 を引く回数 t_{k} を決めるときには、以下のようにすれば良いです。

t_{k-1} \ge a_{k} の場合

このときは単に t_{k} = a_{k} とすれば、単調減少性を保ちながら k 桁目を 0 にできます。

t_{k-1} \lt a_{k} の場合

こっちが問題です。このまま t_{k} = a_{k} とすると単調減少性が壊れるので、今までの桁を遡る必要があります。このとき 1 \le a_{k} \le 9 である（ 0 ではない）ことに注意しておきます。

まず t_{k-1} を増やします。既に N の k-1 桁目は 0 になっているので、これを保ったまま t_{k-1} を増やすとなると最小で 10 増やすことになります。新しく k-1 桁目から 10 回引くことにしたので、 a_{k} は 1 減ります。

この操作は連鎖する可能性があります。もしこの 10 増やした操作によって t_{k-2} \lt t_{k-1} となってしまったら、 t_{k-2} も 10 増やさないといけません。新しく k-2 桁目から 10 回引くことにしたので、そのぶん t_{k-1} は 1 減らします。

これを単調減少性が保たれるまで繰り返します。つまり 0 桁目まで遡ることになるか、元々 t_{m-1} \ge t_{m} + 10 であるような m 桁目で止まります。

この一連の処理は以下のようにまとめることができます。

  • m \lt k であって t_{m-1} \ge t_{m} + 10 であるような最大の m を求める。存在しない場合は m = 0 とする。
  • t_{m} に 10 を加算する。
  • t_{m+1}, ..., t_{k-1} に 9 を加算する。
  • t_{k} = a_{k}-1 とする。

1 \le a_{k} \le 9 であることから、この一連の処理によって t_{k} が負になることや t_{k-1} \lt t_{k} になることはありません。

この処理に必要なものは、まずは区間加算・一点取得のデータ構造です。遅延セグ木でも良いですし、BITをimos法の要領で使ってもできます。次に t_{m-1} \ge t_{m} + 10 となるような m を管理する必要がありますが、1回の処理で「 t_{m-1} \ge t_{m} + 10 であるかどうか」が変化し得るような箇所は定数個なので、操作のたびにそれらを調べて std::set 等に入れておけば最大値を取り出せます。

これを最上位桁まで続けて、最後の時点での \lceil\frac{t_{0}}{9}\rceil が答えになります。

ACコード

Submission #9658581 - AtCoder Grand Contest 011

キーエンス プログラミング コンテスト 2020 F - Monochromization

AtCoder プログラミング 競技プログラミング

F - Monochromization

解説放送を観て解いたので、その方針をベースに書きます。

解法

まずは判定問題

まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。

ある最終状態の盤面から操作を逆回しして考えます。盤面においてもしマスの色が全て同じ行や列がある場合、そこを操作することにすると、それらのマスは「操作前は何色でも良い」という扱いになります。この処理によって行や列を取り除き、新たにマスの色が全て同じ行や列ができた場合、それらも取り除くことができます。「ヨッシーのクッキー」みたいなイメージです。

f:id:betrue12:20200119163802p:plain

この操作をやれるだけ繰り返して残ったマスは、初期盤面からずっとこのままでないといけません。つまりこれらのマスが全て初期盤面と一致していることが、この盤面を作れる必要十分条件になります。

数え上げの軸を決める

上記の判定方法から、数え上げの方針を立てます。上記判定方法では最終盤面から取り除ける行と列を考えていきましたが、数え上げでは逆に、取り除く行と列の組み合わせパターンを全探索して、そのような取り除き方に対応する盤面を数えることにします。行と列で 2^{H+W} 通りのパターンが考えられます。

このとき重複カウントを防ぐためには、初期盤面から指定した行・列を取り除いた後の盤面において、これ以上列や行を取り除くことができないようになっている必要があります。もしまだ取り除ける行や列がある場合は、それを取り除く扱いにしたほうのパターンで数えるからです。

f:id:betrue12:20200119164533p:plain

また全てのマスを取り除くようなパターンは、「全ての行と列を取り除く」という1通りだけ数えるようにします。

このようにすると初期盤面から作れる盤面が重複なく数えられるようになります。あとは各パターンについて、取り除いた、つまり「操作した部分」の色の塗られ方を数えれば良いです。この塗られ方は、行をいくつ、列をいくつ操作することにしたかという数だけに依存します。これを計算しましょう。

ヤング図形への帰着

操作した行数を x 、列数を y とします。操作した行と列を適切に端に寄せると、操作した部分の形は以下のようになります。

f:id:betrue12:20200119164911p:plain

まずは簡単な方、長方形になる x=H かつ y=W の場合から考えましょう。

実はこの長方形の塗り方は、この中の行や列を並び替えることで、以下のような「ヤング図形」になることが分かります。

f:id:betrue12:20200119165112p:plain

このようなヤング図形は、先ほどの「ヨッシーのクッキー」操作によって必ず全てのマスを取り除けます。逆に全てのマスを取り除けるような盤面を、その取り除く順番に基づいて

  • 白で塗る行は上から、黒で塗る行は下から、取り除いた順序（つまり、塗る順序の逆順）で並べる。
  • 同様に、白で塗る列は左から、黒で塗る列は右から並べる。

という規則で並び替えると、その盤面はヤング図形になります。

よって数えるべき値は、このような x 行 y 列の盤面にできるヤング図形から、行・列の並び替えを行ったものと等しいです。ただし境界線のどちら側が白でどちら側が黒かは片方に決めておきます。上図では境界線の右または下が黒と決めています。

あるヤング図形から行・列の並び替えを行ってできる盤面数は、まず全ての並び替え x!y! 通りを考えて、「同じ行または列が k 個ある」というグループそれぞれについて (k!)^{-1} を掛ければ良いです。これを全てのヤング図形について足します。

白黒の境界をグリッド上の経路とみなすと、これは経路を数え上げるDPで計算できます。この経路において同じ方向に k ステップ連続で進むたびに同じ行または列 k 個のグループができるので、これに対応して (k!)^{-1} を掛けて遷移するようにすれば良いです。

これで長方形領域を全て塗る場合の塗られ方の数が計算できるようになりました。

L字領域の数え上げ

最後に x \lt H かつ y \lt W、つまり塗る領域がL字になる時の塗られ方の数を数えます。

行・列のはみ出ている部分の塗られ方は、行・列それぞれの塗り方だけに依存します。そのためまずは行のうち白く塗る本数 x_{1} と 列のうち白く塗る本数 y_{1} を全探索します。それぞれの黒く塗る本数を x_{2} = x - x_{1} 、 y_{2} = y - y_{1} と表記します。

まず行・列それぞれの中での白と黒の並べ方で _{x}C_{x_{1}}\times _{y}C_{y_{1}} 通りの場合があり、これらそれぞれの場合についてはみ出ている領域の塗られ方は異なるので、これらは全て区別されます。

そして行・列をそれぞれ白と黒を固めるように並び替えると、操作する行と列が交わる長方形領域は以下のようになります。

f:id:betrue12:20200119170355p:plain

つまりサイズ x_{1}y_{1} の必ず白になる領域、サイズ x_{2}y_{2} の必ず黒になる領域、そして白と黒が交わる領域がサイズ x_{1}\times y_{2} とサイズ x_{2}\times y_{1} の2つあります。

そして白と黒が交わる領域の塗られ方は、またしても行・列を適切に並び替えることで先ほどのヤング図形になります。つまり、この部分は先ほどと同じDP計算の結果が使えます。

まとめ

解法をまとめると以下のようになります。

前計算パート

x \le H, y \le W なる x, y について、 x 行 y 列の長方形領域を全て塗る場合の塗られ方の数、つまり入れ替えを考慮したヤング図形の個数を先ほど説明したDPで計算する。これを Y\lbrack x\rbrack\lbrack y\rbrack と書くことにする。

x \lt H, y \lt W なる x, y について、 x 行 y 列を塗ったL字領域を全て塗る場合の塗られ方の数を計算する。これは 0 \le x_{1} \le x, 0 \le y_{1} \le y となる x_{1}, y_{1} 全てについて _{x}C_{x_{1}}{}_{y}C_{y_{1}} Y\lbrack x_{1}\rbrack\lbrack y-y_{1}\rbrack Y\lbrack x-x_{1}\rbrack\lbrack y_{1}\rbrack を全て合計したものである。この値を L\lbrack x \rbrack\lbrack y \rbrack と書くことにする。

答え計算パート

操作する行、列のパターン 2^{H+W} 通りを全探索する。ここで全てのマスを操作するようなもの、初期盤面において指定した行・列を取り除いたあとにまだ取り除ける行・列が存在するようなものは無視する。操作する行数を x、操作する列数を y として L\lbrack x \rbrack\lbrack y \rbrack を答えに足す。

最後に「全ての行・列を操作する場合」として Y\lbrack H\rbrack\lbrack W\rbrack を答えに足す。

これで答えが求められます。大変な問題でした…。

ACコード

Submission #9586951 - Keyence Programming Contest 2020

Codeforces Round #605 (Div. 3) F. Two Bracket Sequences

Codeforces プログラミング 競技プログラミング

お題箱より。

Problem - F - Codeforces

問題概要

カッコ列 S, T が与えられる。「正しい」カッコ列であって、 S, T の両方を部分列として含むようなカッコ列のうち、長さが最小のものを1つ求めよ。

制約

1 \le |S|, |T| \le 200

解法

文字列のインデックスは0-indexedで表記します。

まずは正しいカッコ列にこだわらず、「文字列 S, T の両方を部分列として含むような長さ最小の文字列」を求めることを考えます。これは最長共通部分列（LCS）として知られるものとよく似たDPで解くことができます。

dp\lbrack i \rbrack\lbrack j \rbrack：文字列 S の i-1 文字目までと文字列 T の j-1 文字目までの両方を部分列として含む、長さ最小の文字列の長さ

このDPの dp\lbrack i \rbrack\lbrack j \rbrack からの遷移は以下の3通りです。

  • S の i 文字目を末尾に付ける。長さを 1 足して dp\lbrack i+1 \rbrack\lbrack j \rbrack に遷移する。
  • T の j 文字目を末尾に付ける。長さを 1 足して dp\lbrack i \rbrack\lbrack j+1 \rbrack に遷移する。
  • S の i 文字目と T の j 文字目が等しい場合、その文字を末尾に付ける。長さを 1 足して dp\lbrack i+1 \rbrack\lbrack j+1 \rbrack に遷移する。

カッコ列についても、これと似たようなことをします。こちらは「正しい」カッコ列でなければならないという条件があるので、これまでの (開きカッコの数)-(閉じカッコの数) を持っておくことにします。これを「深さ」と呼ぶことにします。

dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack：カッコ列 S の i-1 文字目までとカッコ列 T の j-1 文字目までの両方を部分列として含み、深さが k であるもののうち、長さ最小のカッコ列の長さ

遷移は末尾に開きカッコを付ける場合と閉じカッコを付ける場合の2通りを考え、それぞれ文字を付けた時に S, T の添字が進むかどうかをチェックすれば良いです。 k \lt 0 の範囲には遷移しません。

このDPの添字として扱うべき範囲を考えましょう。 i の最大値は |S| 、 j の最大値は |T| なので 200 以下です。 k として扱うべき値の範囲を考えます。

ここで () が 200 個続くような文字列 ()()()......() は必ず条件を満たすことに注目します。つまり答えは必ず 400 以下です。もしDPの遷移の途中で k が 200 を超えた場合、その開きカッコを全て閉じる必要があるので文字列の長さは必ず 400 を超えます。そのため、 k としても 200 以下の範囲だけを考えれば良いです。

状態数が 201^{3} で各遷移が 2 通りなので、十分間に合います。答えとなる文字列の長さは dp\lbrack |S| \rbrack\lbrack |T| \rbrack\lbrack 0 \rbrack として求められますが、実際の文字列を求める必要があるので、地道に各添字の組について遷移元の添字の組を持っておいて復元しましょう。具体的にはACコード例を参考にしてください。

ACコード

Submission #67019853 - Codeforces

DPの更新順序について、 i, j が減ることはないですが、 k は増えたり減ったりするので注意です。 i, j は普通の2重ループで小さい方から順番に見ていって、

  • 遷移で k を増やす（つまり ( を付ける）場合は、 k が小さい方から見ていく
  • 遷移で k を減らす（つまり ) を付ける）場合は、 k が大きい方から見ていく

ようにすれば良いです。このようにしないと、例えば i, j が一切変化しないまま ))))))... を付けて k を大量に減らす、というような操作を見逃す可能性があります。

Educational Codeforces Round 21 E. Selling Souvenirs

Codeforces プログラミング 競技プログラミング

お題箱より。

Problem - E - Codeforces

少し前にバチャで扱われて話題になっていましたね。公式解説のDPの正当性が分からないというリクエストだったのですが、私もわからないので（ごめんなさい…）もう少し汎用的に使える解法を書きます。

問題概要

n 個の要素について重み w_{i} 、価値 c_{i} が与えられる。これらの要素から合計重み m 以下になるように選んで合計価値を最大化せよ。

制約

  • 1 \le n \le 100000
  • 1 \le m \le 300000
  • 1 \le w_{i} \le 3
  • 1 \le c_{i} \le 10^{9}

解法

ナップサック問題です。 O(nm) は通らない制約なので、 1 \le w_{i} \le 3 という制約を活かすことになります。

重みの種類数とその値が非常に小さいときには、重みの最小公倍数に注目した解法が有効な場合があります。重み 1, 2, 3 の最小公倍数は 6 です。

ここで k=1, 2, 3 について、重み k の要素を使う個数を \frac{6}{k} で割った余り r_{k} に注目します。 (r_{1}, r_{2}, r_{3}) としてあり得る組み合わせを全探索します。 (r_{1}, r_{2}, r_{3}) の値が固定されると、重み k の要素の採用方法は以下のように考えることができます。

  • 重み k の要素を価値の大きいものから順に並べる。まず最初に r_{k} 個の要素を必ず取る。それから先は、 \frac{6}{k} 個の要素（重み合計 6 ）をまとめて取ることを 0 回以上繰り返す。

つまり、 k=1, 2, 3 について最初に取る分を取ってしまったあとは、どこから取っても重み合計 6 の単位で取ることになります。つまり各重みの要素から作った重り合計 6 の塊を全て混ぜてソートし、容量制限が許す限り価値の大きい塊から貪欲に取っていけば良いです。

最初に取る分の要素がそもそもなかったり、それだけで容量制限を超えてしまう場合は、そのような (r_{1}, r_{2}, r_{3}) には解がないということで無視します。

r_{1}, r_{2}, r_{3} が取りうる値の通り数はそれぞれ 6, 3, 2 通りであり、全組み合わせを考慮しても十分小さいです。 (r_{1}, r_{2}, r_{3}) を全探索することで全てのパターンを網羅できるので、試した中で最も価値合計の大きいものが答えになります。

ACコード

Submission #68934022 - Codeforces

余談

重みの最小公倍数が十分に小さくないと取れない解法なのでなかなか使える機会は少ないかもしれませんが、知っておくと役立つかもしれません。類題として、以下の問題も同様の考え方で解けます。

Problem - E - Codeforces

また公式解説では1種類だけ別で扱うようにすることで同時に考慮すべき種類数を減らしています。これを2つのグループに分けていると見なすと半分全列挙の考え方に繋がります。このように計算量を落とす工夫をすると、解ける幅が少し広がると思います。