差分

このページの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/08] – [解法] ikatakos
@@ 行 241: / 行 241: @@
 優先順位付きナップサック問題。
+自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。
 === データ ===
@@ 行 257: / 行 259: @@
 ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。
-$i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、
+$i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、次が同時に成立しているはずである。
   * $X+w_i \le s_j$
   * $X+w_j \gt s_i$
-となるXが存在するはずである。（与えられたブロックで実現できるかは別として、数値として）
+これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となる。重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。
-これを移項してXを消去すると、$s_i+w_i \lt s_j+w_j$ となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。
 === 遷移 ===
@@ 行 347: / 行 347: @@
 === データ ===
-$DP[i][j]=$ Ｓマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが自身を含め $j=[0:偶数,1:奇数]$ 個の場合の経路数
+$DP[i][j]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め $j=[0:偶数,1:奇数]$ 個の場合の経路数
 さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝[[wpjp>分配法則]]が成り立つ）ので、以下のようにするとより省計算量・省メモリになる。
-$DP[i]=$ Ｓマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが(偶数個の場合の経路数)-(奇数個の場合の経路数)
+$DP[i]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め(偶数個の場合の経路数)-(奇数個の場合の経路数)
 === 初期条件 ===
@@ 行 360: / 行 360: @@
 つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。
-これにより、$i$ 番目の壁マスを考えるとき、$DP[1]～DP[i-1]$ に付いては確定していることを保証できる。
+これにより、$i$ 番目の壁マスを考えるとき、$DP[1]～DP[i-1]$ については確定していることを保証できる。
 $i$ 番目の壁マスを考える。Ｓマスと $1～i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。
@@ 行 373: / 行 373: @@
 $\displaystyle DP[i] = \sum_{k=0}^{i-1}(-DP[k] \times p_{k,i})$
-DP[k] では（偶数個）-（奇数個）の値だったものが、$i$ 番目の壁マスを踏むことによって一律1個ずつ増えて（奇数個）-（偶数個）になるので、更新時に正負逆転させておくのが重要。
+DP[k] では（偶数個）-（奇数個）の値だったものが、遷移すると $i$ 番目の壁マスを踏むことによって一律1個ずつ増えて（奇数個）-（偶数個）を示す値になるので、更新時に正負逆転させておくのが重要。
 計算の便宜上、Ｇマスも"N+1番目の壁マス"と見做して同様に計算すると、答えは $-DP[N+1]$ となる。
 （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている）
+%%c++%% の場合は負数%正数が負になるので注意。Pythonでは正となるので、そのまま出力できる。
 <sxh python>