差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
次のリビジョン
前のリビジョン
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  ​ ​7 ​ 8 +  ​※ *** ... スコアが加算されている 
-  条件1 ​  ​********** ​ |--------| ​   範囲のDPに $A_1$ を加算 +   
-  条件2 ​           |-----| ​         k=7 では範囲外となったので、もう加算していてはいけない +  ​k=
-  条件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 ​対応する位置 
 +  更新訪れられ頂点 |  
 +                8     ​| ​          1 
 +        ④             ​| ​    ​② ​         3 
 +    2      ⑥         ​| ​ 4    5    ⑥    7 
 +  1  3  5  ⑦       | 8 9 10 11 12 13 ⑭ 15 
  
-  BinaryIndexedTreeでの更新 ​ | SegmentTree に対応する位置 
-                8           ​| ​          1 
-        ④                   ​| ​    ​② ​         3 
-    2      ⑥               ​| ​ 4    5    ⑥    7 
-  1  3  5  ⑦             | 8 9 10 11 12 13 ⑭ 15  
-  ​ 
 <sxh python> <sxh python>
 import sys import sys
programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_4.1549617743.txt.gz · 最終更新: 2019/02/08 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0