競プロ典型90問 090 Tenkei90's Last Problem（★7）DPの基本部分
競プロ典型90問の90問目は
小課題4が、基本DPを組む
小課題5が、重複を省く
小課題6と小課題7が、大きな値で計算できるように高度なテクニックで処理を改善する
というものになっている。
この記事では、小課題4の基本DPを解説する。
条件
ここからは、条件という言葉がよく出てくる。
条件というのは問題文にある
1 ≦ l ≦ r ≦ N を満たす任意の整数の組 (l, r) について、
min{A[l], A[l+1], …, A[r]} × (r-l+1) ≦ K
のこと。ある範囲(lからr)の、「最低値」と「幅」を掛けた値がK以下だというもの。ちなみに問題文では r は範囲の右端なので幅は r-l+1 になっている。
min{A[l], A[l+1], …, A[r]} × (r-l+1) ≦ K
をこの先、条件式ということにする。
注意点
この先の注意点
- rというのが範囲の右端だったり右端のひとつ右だったりする。問題文では右端。解説PDFでは右端が多い。ソースコードは右端のひとつ右である
- ある範囲のことを言っているときに「条件」と言った時は、その範囲内の全ての組み合わせに条件式を適用することを意味している。端の組み合わせのみに条件式を適用しているときは「端の組み合わせ」という
私は出来るだけ誤解が無いように気を付ける。
dp[h][l][r]
これは、部分列 (Al…Ar) の値がすべてh以上で、かつ、条件を満たすもの、の個数である。
この「条件を満たす」とはlからr内の全ての組み合わせで条件式が成り立っていることを言っている。
この dp[h][l][r] を構成するのは4つ(カウントされているものは4つ)。
- 最低値がh+1以上
- 最低値がhで、hになる場所の一番右が範囲の左端
- 最低値がhで、hになる場所の一番右が範囲の右端
- 最低値がhで、hになる場所の一番右が範囲の途中
hになる場所の一番右
一番右というのがやっかいな表現である。
hになる場所で場合分けをしたいのだが、範囲が4つの場合、hになる場所の組み合わせは15個ある。
oxxx xoxx xxox xxxo
ooxx oxox oxxo xoox xoxo xxoo
ooox ooxo oxoo xooo
oooo
これを一番右に来るもので場合分けすると
左から
1番目 oxxx
2番目 ooxx xoxx
3番目 ooox oxox xoox xxox
4番目 oooo ooxo oxoo oxxo xooo xoxo xxoo xxxo
となる。
dp[h][l][r]詳細
まず、lとrの端の組み合わせで条件式が成り立たないならこのdp[h][l][r]の値は0になる。
つまり、h × (r - l + 1) ≦ K とならない場合は0になる。
以下はlとrの端の組み合わせで条件式が成り立つ場合の話。
dp[h][l][r]は
最低の値がhかh+1以上かで場合分けをする。
最低の値がh+1以上なら、その値はdp[h+1][l][r]ですでに計算してある。
最低の値がhなら、さらにその場所で場合分けをする。hになる場所が2カ所以上になることもあるので、hになっている場所の一番右で場合分けをする。
一番右の場所が
lのとき、l+1のとき、l+2のとき...rのとき
のそれぞれの値を足す。この足す操作をしているのがΣ記号。
この問題のひとつ目の鍵であるΣ内の計算
次にΣ内の計算だが
hの右端がkのとき、
kの左側はlからk-1の範囲であり値はh以上である。kの右側はk+1からrの範囲であり値はh+1以上である。
場所lから場所k-1の値の選び方は、その範囲で条件式を満たす必要がある。それはdp[h][l][k-1]個ある。
場所k+1から場所rの値の選び方は、その範囲で条件式を満たす必要がある。それはdp[h+1][k+1][r]個ある。
これらを掛ければよいように思える。
ただ、我々が今求めたいものはlからrの範囲で条件式を満たすものである。
kの左側とkの右側の組み合わせでも条件式満たす必要がある。
ここで、lとrの組み合わせでhが条件式を満たすことを思い出すと、kを含むそれより小さい任意の範囲も条件式を満たす法則により、kの左側とkの右側の組み合わせでも条件式満たすことがわかる。
以上より、dp[h][l][k-1]とdp[h+1][k+1][r]の掛け算によってkの場所の値Akがhのときの値が求まる。
kの位置が端
kの位置が左端のときは、それより左は無いので、dp[h][l][k-1]の部分は1とする
kの位置が右端のときは、それより右は無いので、dp[h+1][k+1][r]の部分は1とする
DPの順番
各dp[h][l][r]を計算するときに必要なものが揃っているように、hは上からやって、範囲は小さい方からやる。
090-04.cpp の解説
dp[h][l][r] というのはlからr-1の範囲を表す。
存在しない範囲を表す dp[h][i][i]
dp[h][i][i] は存在しない範囲を表す。この値を1にしておくと計算のときに都合がよいのですべての dp[h][i][i] タイプに1を設定する。
for (int h = K; h >= 0; --h) {
for (int i = 0; i < N; ++i) {
dp[h][i][i] = 1;
}
}
トップの h = K
幅が2以上では条件式が成り立たないので、幅1のときのみ設定される。
dp[h][l][r] = dp[h][l][r - 1];
が設定される。この dp[h][l][r - 1] は dp[h][l][l] なので1が設定される。
トップより下
lとrに幅1以上のすべての組み合わせを入れるが、幅が広くなって 端の組み合わせで条件を満たさないなら次の部分で中断して dp の代入をしない。
if (h * (r - l) > K) {
continue;
}
ここを抜けると以下のことを行う。
r = l + 1 のとき
幅は1。
- そこの値がh+1以上
- そこの値がh
の2つをカウントする。
dp[h][l][r] = dp[h][l][r - 1]; //(=1)
にて、そこの値がhのときをカウント。
疑問思うかもしれないが、これは一番右の場所がhのときをカウントしている。今の場合、その左にhの範囲なし、右にh+1の範囲なしなので1が入る。
i のfor文は
dp[h + 1][i][r] はそこの値がh+1以上の値、
dp[h][l][i != l ? i - 1 : l] は i != l が false なので dp[h][l][l] つまり1
このfor文で、i はh+1の範囲の左端を意味している。
r = l + 2 のとき
範囲は2。
- 全部がh+1以上
- 左側が「一番右のh」
- 右側が「一番右のh」
の3つをカウントする
dp[h][l][r] = dp[h][l][r - 1];
にて、右側が「一番右のh」のときをカウント
i のfor文は l と l + 1 の2回走り
i = l のとき
dp[h + 1][i][r] 範囲全体がh+1
dp[h][l][i != l ? i - 1 : l] は i != l がfalseより l つまり dp[h][l][l] よって1。
これは「全部がh+1以上」をカウントしている。
i = l + 1 のとき
dp[h + 1][i][r] 右側だけh+1
dp[h][l][i != l ? i - 1 : l] は i != l がtrueより i - 1 となり l つまり dp[h][l][l] よって1。
これは左側が「一番右のh」の場合をカウントしている。
r = l + 3 のとき
範囲は3。
- 全部がh+1以上
- 一番左側が「一番右のh」
- 真ん中が「一番右のh」
- 一番右側が「一番右のh」
の4つをカウントする
dp[h][l][r] = dp[h][l][r - 1];
にて、一番右側が「一番右のh」のときをカウント
i のfor文は l から l + 2 の3回走り
i = l のとき
dp[h + 1][i][r] 範囲全体がh+1
dp[h][l][i != l ? i - 1 : l] は i != l がfalseより l つまり dp[h][l][l] よって1。
これは「全部がh+1以上」をカウントしている。
i = l + 1 のとき
dp[h + 1][i][r] h+1の範囲が中と右
dp[h][l][i != l ? i - 1 : l] は i != l がtrueより i - 1 となり l つまり dp[h][l][l] よって1。
これは一番左側が「一番右のh」の場合をカウントしている。
i = l + 2 のとき
dp[h + 1][i][r] h+1の範囲は右端のみ
dp[h][l][i != l ? i - 1 : l] は i != l がtrueより i - 1 つまり l + 1、よって dp[h][l][l+1] 。
これは真ん中が「一番右のh」の場合をカウントしている。
Discussion