差分
このページの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,ji,j があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を XX とする。 | ある2つのブロック i,ji,j があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を XX とする。 | ||
| - | ii を上にすると両方積めるが、jj が上だと積めなくなる場合があったとすると、 | + | ii を上にすると両方積めるが、jj が上だと積めなくなる場合があったとすると、次が同時に成立しているはずである。 |
| * X+wi≤sjX+wi≤sj | * X+wi≤sjX+wi≤sj | ||
| * X+wj>siX+wj>si | * X+wj>siX+wj>si | ||
| - | となるXが存在するはずである。（与えられたブロックで実現できるかは別として、数値として） | + | これを移項してXを消去すると、si+wi<sj+wjsi+wi<sj+wj となる。重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 |
| - | + | ||
| - | これを移項してXを消去すると、si+wi<sj+wjsi+wi<sj+wj となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 | + | |
| === 遷移 === | === 遷移 === | ||
| 行 347: | 行 347: | ||
| === データ === | === データ === | ||
| - | DP[i][j]=DP[i][j]= Ｓマスから ii 個目の壁マスまでの、今まで少なくとも通過した壁マスが自身を含め j=[0:偶数,1:奇数] 個の場合の経路数 | + | DP[i][j]= Ｓマスから i 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め j=[0:偶数,1:奇数] 個の場合の経路数 |
| さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝[[wpjp> | さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝[[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 番目の壁への経路数を求める。 | i 番目の壁マスを考える。Ｓマスと 1～i−1 番目の壁マスの、それぞれからのi 番目の壁への経路数を求める。 | ||
| 行 373: | 行 373: | ||
| DP[i]=i−1∑k=0(−DP[k]×pk,i) | DP[i]=i−1∑k=0(−DP[k]×pk,i) | ||
| - | DP[k] では（偶数個）-（奇数個）の値だったものが、i 番目の壁マスを踏むことによって一律1個ずつ増えて（奇数個）-（偶数個）になるので、更新時に正負逆転させておくのが重要。 | + | DP[k] では（偶数個）-（奇数個）の値だったものが、遷移すると |
| 計算の便宜上、Ｇマスも" | 計算の便宜上、Ｇマスも" | ||
| （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている） | （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている） | ||
| + | |||
| + | %%c++%% の場合は負数%正数が負になるので注意。Pythonでは正となるので、そのまま出力できる。 | ||
| <sxh python> | <sxh python> | ||
