差分

このページの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=6     1  2  3  4  5  6  7  8
+  k=6
-  文字列  0  0  1  0  0
+  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=6$ の最大スコアは、最後に'''1'''が立った場所を  $t$  文字目とすると、以下のスコアの最大値となる。
+上の例で、$DP[6] $は、最後に'''1'''が立った場所を$ t$ 文字目とすると、以下のスコアの最大値となる。
   *  $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
+  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=7     1  2  3  4  5  6  7  8
+  ※ *** ... スコアが加算されている
-  条件1   **********  |--------|    * の範囲のDPに  $A_1$  を加算
-  条件2            |-----|          k=7 では範囲外となったので、もう加算していてはいけない
+  k=6
-  条件3   *  |--------------|       * の範囲のDPに  $A_3$  を加算
+  2  3  4  5  ⑥  7  8
-  条件5   ****************  |--|    k=7 で範囲内となったので、新たに加算
+  条件1   **********  |---------|
+  条件2   *******  |-----|
+  条件3   *  |---------------|
+  条件5                      |--|    まだ範囲外
+  ↓
+  k=7
+  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$  を加算する
   *  $\max(DP[1]～DP[k-1])$  を求め、 $DP[k]$  に加算する。
   *  $k=R_i$  となる条件があった場合、 $DP[1]～DP[L_i-1]$  にスコア  $-A_i$  を加算する
-以上で、 $DP[k]$  の最大値が答え。
+以上で、 $DP[k]$  の最大値が答え。区間加算するタイミングと、最大値を得るタイミングに注意。
 ===実装===
@@ 行 115: / 行 128: @@
 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>
 import sys