差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/08] – [解法] ikatakos | programming_algorithm:contest_history:atcoder:2019:0106_educational_dp_4 [2019/02/26] (現在) – [解法] ikatakos | ||
---|---|---|---|
行 41: | 行 41: | ||
なのだが、k−1 文字目以前に既に加算していた場合は新たには加算されない。 | なのだが、k−1 文字目以前に既に加算していた場合は新たには加算されない。 | ||
- | k=6 | + | k=6 |
- | 文字列 | + | 1 2 3 4 5 6 7 8 |
- | 条件1 | + | 文字列例1 |
- | 条件2 | + | 条件1 |
- | 条件3 | + | 条件2 |
- | 条件4 | + | 条件3 |
- | 条件5 | + | 条件4 |
+ | 条件5 | ||
| | ||
- | 文字列 | + | 文字列例2 |
- | 条件1 | + | 条件1 |
- | 条件2 | + | 条件2 |
- | 条件3 | + | 条件3 |
+ | | ||
k 文字目より前で最後に''' | k 文字目より前で最後に''' | ||
- | $k=6$ の最大スコアは、最後に''' | + | 上の例で、$DP[6]は、最後に‴t$ 文字目とすると、以下のスコアの最大値となる。 |
* t \lt 2 の時、DP[t] に条件1~3のスコアを加算した値 | * t \lt 2 の時、DP[t] に条件1~3のスコアを加算した値 | ||
行 68: | 行 69: | ||
上の場合分けを、各条件を主軸にまとめると、以下のようになる。 | 上の場合分けを、各条件を主軸にまとめると、以下のようになる。 | ||
- | * t \lt 5 (=L_1) なら、条件1のスコアを加算 | + | * t \lt 5 (=L_1) なら、DP[t] に条件1のスコアを加算 |
- | * t \lt 4 (=L_2) なら、条件2のスコアを加算 | + | * t \lt 4 (=L_2) なら、DP[t] に条件2のスコアを加算 |
- | * t \lt 2 (=L_3) なら、条件3のスコアを加算 | + | * t \lt 2 (=L_3) なら、DP[t] に条件3のスコアを加算 |
- | あらかじめ、k を範囲に含む条件については、スコアが加算されるべき t の範囲(1 \le t \lt L_i)に加算しておいてやる。 | + | 足し込む範囲を図化すると、以下のようになる。 |
- | k=6 1 2 3 4 5 6 7 8 | + | |
- | 条件1 | + | 条件1 |
- | 条件2 | + | 条件2 |
- | 条件3 | + | 条件3 |
+ | |||
+ | DP[6] = MAX( DP[1]+A1+A2+A3, | ||
- | すると、DP[k] は、ただ1つの区間MAXクエリ \max(DP[1]~DP[k-1]) で求められるようになる。 | + | あらかじめ、DP配列に直接、k を含む各条件のスコアをそれぞれ 1 ~ L_i-1 の範囲に加算しておいてやる。 |
+ | |||
+ | すると、DP[k] は、ただ1つの区間MAXクエリ \max(DP[1]~DP[k-1]) | ||
+ | |||
+ | 個人的に「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行えるのだから仕方ない。 | ||
ここで、現在の k を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ここで、現在の k を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ||
つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | ||
- | k=7 1 2 3 4 5 | + | |
- | 条件1 | + | |
- | 条件2 | + | |
- | 条件3 | + | |
- | 条件5 | + | 条件1 |
+ | 条件2 | ||
+ | 条件3 | ||
+ | 条件5 | ||
+ | ↓ | ||
+ | k=7 | ||
+ | 1 2 3 4 5 6 ⑦ 8 | ||
+ | 条件1 | ||
+ | 条件2 | ||
+ | 条件3 | ||
+ | 条件5 | ||
- | それには、以下の処理を行うとよい。 | + | 加算していたのを元に戻すには、同じ範囲に -A_i |
- | * k から新しく範囲となる($k=L_i$)条件に対して、$DP[1]~DP[L_i-1] に A_i$ を加算する | + | まとめると、k を1つずつ見て、$DP[k]$ を小さい方から確定させていく過程で、 |
- | * k で範囲が終了する(k=R_i)条件は、加算していたものを元に戻す(DP[1]~DP[L_i-1] に -A_i を加算する) | + | |
- | まとめると、 | ||
- | |||
- | * k を1つずつ見て、DP[k] を小さい方から確定させていく | ||
* k=L_i となる条件があった場合、DP[1]~DP[k-1] にスコア A_i を加算する | * k=L_i となる条件があった場合、DP[1]~DP[k-1] にスコア A_i を加算する | ||
* \max(DP[1]~DP[k-1]) を求め、DP[k] に加算する。 | * \max(DP[1]~DP[k-1]) を求め、DP[k] に加算する。 | ||
* k=R_i となる条件があった場合、DP[1]~DP[L_i-1] にスコア -A_i を加算する | * k=R_i となる条件があった場合、DP[1]~DP[L_i-1] にスコア -A_i を加算する | ||
- | 以上で、DP[k] の最大値が答え。 | + | 以上で、DP[k] の最大値が答え。区間加算するタイミングと、最大値を得るタイミングに注意。 |
===実装=== | ===実装=== | ||
行 115: | 行 128: | ||
Add to kは別として、残りは必ず区間の左端が '' | Add to kは別として、残りは必ず区間の左端が '' | ||
+ | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | ||
- | たとえば [1, 7] に対する加算なら以下の右図のようにindexは「2, | + | たとえば [1, 7] に対する加算なら以下の右図のようにBITで更新されるindexは「4, 6, 7」で、SegmentTreeに対応するのは「2, 6, 14」となるので、これを事前計算して保持しておくと、毎回indexを求める計算を省略できる。 |
- | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | + | BinaryIndexedTreeの | SegmentTree |
+ | 更新で訪れられる頂点 | | ||
+ | 8 | ||
+ | ④ | ||
+ | 2 ⑥ | ||
+ | 1 3 5 ⑦ | 8 9 10 11 12 13 ⑭ 15 | ||
- | BinaryIndexedTreeでの更新 | ||
- | 8 | ||
- | ④ | ||
- | 2 ⑥ | ||
- | 1 3 5 ⑦ | 8 9 10 11 12 13 ⑭ 15 | ||
- | | ||
<sxh python> | <sxh python> | ||
import sys | import sys |