差分
このページの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: | ||
| 優先順位付きナップサック問題。 | 優先順位付きナップサック問題。 | ||
| + | |||
| + | 自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。 | ||
| === データ === | === データ === | ||
| 行 246: | 行 248: | ||
| === 初期条件 === | === 初期条件 === | ||
| - | -1など、重さ $j$ が処理済/未処理であることが区別できる値で全て埋めておく | + | $DP[0][0]=0$ |
| + | |||
| + | 他は、重さ $j$ が実現可能/不可能であることが区別できるよう、-1など正しい重さになり得ない値で埋めておく | ||
| === 優先順位 === | === 優先順位 === | ||
| 遷移の前に、優先順位を求める。 | 遷移の前に、優先順位を求める。 | ||
| - | 重たいブロックを上に積むのは非効率なので、上に積んだ方がよいブロックの順序があると予測する。 | + | 重たいブロックを上に積むのは非効率なので、優先的に積んだ方がよいブロックの順序があると予測する。 |
| ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。 | ある2つのブロック $i,j$ があり、2つとも使うことを考える。2つの上に積み上がったブロックの重さの総和を $X$ とする。 | ||
| - | $i$ の方を上にしないと、$j$ が上だと積めなくなる場合というのは、 | + | $i$ を上にすると両方積めるが、$j$ が上だと積めなくなる場合があったとすると、次が同時に成立しているはずである。 |
| * $X+w_i \le s_j$ | * $X+w_i \le s_j$ | ||
| * $X+w_j \gt s_i$ | * $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$ となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 | + | |
| === 遷移 === | === 遷移 === | ||
| 行 268: | 行 271: | ||
| あとは普通のナップサックDP。 | あとは普通のナップサックDP。 | ||
| - | 丈夫さの上限が $10^4$ なので、考慮すべき重さの総計は多くとも $2 \times 10^4$ まででよい。 | + | 重さと丈夫さの上限が $10^4$ なので、考慮すべき重さの総計は多くとも $2 \times 10^4$ まででよい。 |
| （$w_i=10^4, | （$w_i=10^4, | ||
| 行 312: | 行 315: | ||
| こういう、序盤の敵がアレンジされて強くなって終盤に出てくるのって、RPG的でいいよね。 | こういう、序盤の敵がアレンジされて強くなって終盤に出てくるのって、RPG的でいいよね。 | ||
| + | |||
| + | ===方針=== | ||
| $N$ の制約がそこまで多くないので、包除原理DPを行う。 | $N$ の制約がそこまで多くないので、包除原理DPを行う。 | ||
| - | |||
| - | 「1回も壁を通過しないパターン数」＝「全体のパターン数」-「1回でも壁を通過しちゃうパターン数」 | ||
| - | |||
| - | ===方針=== | ||
| 壁マスでも通過できるとして、" | 壁マスでも通過できるとして、" | ||
| 行 342: | 行 343: | ||
| この「他の●を通ったかどうかは関係ない」というところが、経路数の計算を単純明快にしてくれる。 | この「他の●を通ったかどうかは関係ない」というところが、経路数の計算を単純明快にしてくれる。 | ||
| - | 下に $x$ マス、右に $y$ マス移動する経路数は、合計 $x+y$ 回の移動から下移動に当てはまる $x$ 回の移動の選び方になるので、${}_{x+y}C_{x}$ 通り。 | + | 下に $x$ マス、右に $y$ マス移動する経路数は、合計 $x+y$ 回の移動から下移動に当てはまる $x$ 回の移動の選び方になるので、${}_{x+y}C_{x}$ 通りと計算できる。 |
| それを踏まえて、必要なDPを考える。 | それを踏まえて、必要なDPを考える。 | ||
| === データ === | === データ === | ||
| - | $DP[i][j]=$ Ｓマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが自身を含め $j=[0: | + | $DP[i][j]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め $j=[0: |
| さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝[[wpjp> | さらに、最終的に必要なのは通過した壁マスが（偶数個）-（奇数個）の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える（＝[[wpjp> | ||
| - | $DP[i]=$ Ｓマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが(偶数個の場合の経路数)-(奇数個の場合の経路数) | + | $DP[i]=$ Ｓマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め(偶数個の場合の経路数)-(奇数個の場合の経路数) |
| === 初期条件 === | === 初期条件 === | ||
| 行 360: | 行 361: | ||
| つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。 | つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。 | ||
| - | これにより、$i$ 番目の壁マスを考えるとき、$DP[1]～DP[i-1]$ に付いては確定していることを保証できる。 | + | これにより、$i$ 番目の壁マスを考えるとき、$DP[1]～DP[i-1]$ については確定していることを保証できる。 |
| $i$ 番目の壁マスを考える。Ｓマスと $1～i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。 | $i$ 番目の壁マスを考える。Ｓマスと $1～i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。 | ||
| 行 367: | 行 368: | ||
| * $c_j \gt c_i$ の時、$p_{j, | * $c_j \gt c_i$ の時、$p_{j, | ||
| - | * $c_j \le c_i$ の時、$p_{j, | + | * $c_j \le c_i$ の時、$p_{j, |
| 計算の便宜上、Ｓマスも" | 計算の便宜上、Ｓマスも" | ||
| 行 373: | 行 374: | ||
| $\displaystyle DP[i] = \sum_{k=0}^{i-1}(-DP[k] \times p_{k,i})$ | $\displaystyle DP[i] = \sum_{k=0}^{i-1}(-DP[k] \times p_{k,i})$ | ||
| - | DP[k] では（偶数個）-（奇数個）の値だったものが、$i$ 番目の壁マスを踏むことによって一律1個ずつ増えて（奇数個）-（偶数個）になるので、更新時に正負逆転させておくのが重要。 | + | DP[k] では（偶数個）-（奇数個）の値だったものが、遷移すると |
| 計算の便宜上、Ｇマスも" | 計算の便宜上、Ｇマスも" | ||
| （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている） | （本来は壁マスでないＧマスを壁マスとして計算しているため、DP上では正負逆転した値となっている） | ||
| + | |||
| + | %%c++%% の場合は負数%正数が負になるので注意。Pythonでは正となるので、そのまま出力できる。 | ||
| <sxh python> | <sxh python> | ||
