差分
この文書の現在のバージョンと選択したバージョンの差分を表示します。
| 両方とも前のリビジョン 前のリビジョン 次のリビジョン | 前のリビジョン | ||
|
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 1 2 3 4 5 6 7 8 | + | k=6 |
| - | 文字列 0 0 1 0 0 | + | 1 2 3 4 5 6 7 8 |
| - | 条件1 |--------| 加算される | + | 文字列例1 0 0 1 0 0 DP[3] に対して…… |
| - | 条件2 |-----| 加算される | + | 条件1 |--------| 加算される |
| - | 条件3 |--------------| 既に3文字目で加算済みなので新たには加算されない | + | 条件2 |-----| 加算される |
| - | 条件4 |--| 範囲外 | + | 条件3 |--------------| 既に3文字目で加算済みなので新たには加算されない |
| - | 条件5 |--| 範囲外 | + | 条件4 |--| 範囲外 |
| + | 条件5 |--| 範囲外 | ||
| | | ||
| - | 文字列 1 1 1 1 0 | + | 文字列例2 1 1 1 1 0 DP[4] に対して…… |
| - | 条件1 |--------| 加算される | + | 条件1 |--------| 加算される |
| - | 条件2 |-----| 既に4文字目で加算済みなので新たには加算されない | + | 条件2 |-----| 既に4文字目で加算済みなので新たには加算されない |
| - | 条件3 |--------------| 既に4文字目(以前)で加算済みなので新たには加算されない | + | 条件3 |--------------| 既に4文字目で加算済みなので新たには加算されない |
| + | 条件4,5 略 | ||
| $k$ 文字目より前で最後に'''1'''が立った場所により、各条件が加算されたりされなかったりする。 | $k$ 文字目より前で最後に'''1'''が立った場所により、各条件が加算されたりされなかったりする。 | ||
| - | $k=6$ の最大スコアは、最後に'''1'''が立った場所を $t$ 文字目とすると、以下のスコアの最大値となる。 | + | 上の例で、$DP[6]$ は、最後に'''1'''が立った場所を $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 2 3 4 5 6 7 8 |
| - | 条件1 ********** |--------| * の範囲のDPに $A_1$ を加算 | + | 条件1 ********** |--------| * の範囲のDPに A1 を加算 |
| - | 条件2 ******* |-----| * の範囲のDPに $A_2$ を加算 | + | 条件2 ******* |-----| * の範囲のDPに A2 を加算 |
| - | 条件3 * |--------------| * の範囲のDPに $A_3$ を加算 | + | 条件3 * |--------------| * の範囲のDPに A3 を加算 |
| + | |||
| + | DP[6] = MAX( DP[1]+A1+A2+A3, DP[2]+A1+A2, DP[3]+A1+A2, DP[4]+A1, DP[5] ) | ||
| - | すると、$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は加算後の値）で求められるようになる。 | ||
| + | |||
| + | 個人的に「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行えるのだから仕方ない。 | ||
| ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ||
| つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | ||
| - | k=7 1 2 3 4 5 6 7 8 | + | ※ *** ... スコアが加算されている |
| - | 条件1 ********** |--------| * の範囲のDPに $A_1$ を加算 | + | |
| - | 条件2 |-----| k=7 では範囲外となったので、もう加算していてはいけない | + | k=6 |
| - | 条件3 * |--------------| * の範囲のDPに $A_3$ を加算 | + | 1 2 3 4 5 ⑥ 7 8 |
| - | 条件5 **************** |--| k=7 で範囲内となったので、新たに加算 | + | 条件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は別として、残りは必ず区間の左端が ''1'' なので、Add時やGetMax時、配列に加算したり参照する必要のある要素は $k$ によって固定である。 | Add to kは別として、残りは必ず区間の左端が ''1'' なので、Add時やGetMax時、配列に加算したり参照する必要のある要素は $k$ によって固定である。 | ||
| + | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | ||
| - | たとえば $[1, 7]$ に対する加算なら以下の右図のようにindexは「2, 6, 14」となるので、これを事前計算して保持しておくと、毎回indexを求める計算を省略できる。 | + | たとえば $[1, 7]$ に対する加算なら以下の右図のようにBITで更新されるindexは「4, 6, 7」で、SegmentTreeに対応するのは「2, 6, 14」となるので、これを事前計算して保持しておくと、毎回indexを求める計算を省略できる。 |
| - | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | + | BinaryIndexedTreeの | SegmentTree に対応する位置 |
| + | 更新で訪れられる頂点 | | ||
| + | ８ | １ | ||
| + | ④ | ② ３ | ||
| + | ２ ⑥ | ４ ５ ⑥ ７ | ||
| + | １ ３ ５ ⑦ | ８ ９ 10 11 12 13 ⑭ 15 | ||
| - | BinaryIndexedTreeでの更新 | SegmentTree に対応する位置 | ||
| - | ８ | １ | ||
| - | ④ | ② ３ | ||
| - | ２ ⑥ | ４ ５ ⑥ ７ | ||
| - | １ ３ ５ ⑦ | ８ ９ 10 11 12 13 ⑭ 15 | ||
| - | | ||
| <sxh python> | <sxh python> | ||
| import sys | import sys | ||
