差分
このページの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-1$ 文字目以前に既に加算していた場合は新たには加算されない。 | ||
- | k=6 | + | k=6 |
- | 文字列 | + | 1 2 3 4 5 6 7 8 |
- | 条件1 | + | 文字列例1 |
- | 条件2 | + | 条件1 |
- | 条件3 | + | 条件2 |
- | 条件4 | + | 条件3 |
- | 条件5 | + | 条件4 |
+ | 条件5 | ||
| | ||
- | 文字列 | + | 文字列例2 |
- | 条件1 | + | 条件1 |
- | 条件2 | + | 条件2 |
- | 条件3 | + | 条件3 |
+ | | ||
$k$ 文字目より前で最後に''' | $k$ 文字目より前で最後に''' | ||
- | $k=6$ の最大スコアは、最後に''' | + | 上の例で、$DP[6]$ は、最後に''' |
* $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 | + | 条件1 |
- | 条件2 | + | 条件2 |
- | 条件3 | + | 条件3 |
+ | |||
+ | DP[6] = MAX( DP[1]+A1+A2+A3, | ||
+ | |||
+ | あらかじめ、DP配列に、「$k$ を含む条件のスコア」をそれぞれ $1 ~ L_i-1$ の範囲に加算しておいてやる。 | ||
+ | |||
+ | すると、$DP[k]$ は、ただ1つの区間MAXクエリ $\max(DP[1]~DP[k-1])$ (DPは加算後の値)で求められるようになる。 | ||
- | すると、$DP[k]$ は、ただ1つの区間MAXクエリ $\max(DP[1]~DP[k-1])$ で求められるようになる。 | + | 「DP配列で、決定済みの部分の数値がいじられる」ことにちょっと抵抗感があるが、この方法で効率的に更新を行える。 |
ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ここで、現在の $k$ を範囲に含む条件のスコアのみが、過不足無くDPに反映された状態を保たないといけない。 | ||
つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | つまり、まだ手前だったり、既に通過した条件のスコアが足されていてはいけない。 | ||
- | k=7 1 2 3 4 5 | + | |
- | 条件1 | + | |
- | 条件2 | + | |
- | 条件3 | + | |
- | 条件5 | + | 条件1 |
+ | 条件2 | ||
+ | 条件3 | ||
+ | 条件5 | ||
+ | ↓ | ||
+ | k=7 | ||
+ | 1 2 3 4 5 6 ⑦ 8 | ||
+ | 条件1 | ||
+ | 条件2 | ||
+ | 条件3 | ||
+ | 条件5 | ||
それには、以下の処理を行うとよい。 | それには、以下の処理を行うとよい。 | ||
行 95: | 行 112: | ||
* $k$ で範囲が終了する($k=R_i$)条件は、加算していたものを元に戻す($DP[1]~DP[L_i-1]$ に $-A_i$ を加算する) | * $k$ で範囲が終了する($k=R_i$)条件は、加算していたものを元に戻す($DP[1]~DP[L_i-1]$ に $-A_i$ を加算する) | ||
- | まとめると、 | + | まとめると、$k$ を1つずつ見て、$DP[k]$ を小さい方から確定させていく過程で、 |
- | * $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: | 行 131: | ||
Add to kは別として、残りは必ず区間の左端が '' | Add to kは別として、残りは必ず区間の左端が '' | ||
+ | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | ||
- | たとえば $[1, 7]$ に対する加算なら以下の右図のようにindexは「2, | + | たとえば $[1, 7]$ に対する加算なら以下の右図のようにBITで更新されるindexは「4, 6, 7」で、SegmentTreeに対応するのは「2, 6, 14」となるので、これを事前計算して保持しておくと、毎回indexを求める計算を省略できる。 |
- | このindexの特定には、Binary Indexed Tree(Fenwick Tree) の概念を利用できる。 | + | BinaryIndexedTreeの | SegmentTree |
+ | 更新で訪れられる頂点 | | ||
+ | 8 | ||
+ | ④ | ||
+ | 2 ⑥ | ||
+ | 1 3 5 ⑦ | 8 9 10 11 12 13 ⑭ 15 | ||
- | BinaryIndexedTreeでの更新 | ||
- | 8 | ||
- | ④ | ||
- | 2 ⑥ | ||
- | 1 3 5 ⑦ | 8 9 10 11 12 13 ⑭ 15 | ||
- | | ||
<sxh python> | <sxh python> | ||
import sys | import sys | ||
行 241: | 行 257: | ||
優先順位付きナップサック問題。 | 優先順位付きナップサック問題。 | ||
+ | |||
+ | 自分より上のブロックの重さは丈夫さに関わるため、実際のタワーのように下から積み上げるのではなく、上から決めていく。 | ||
=== データ === | === データ === | ||
行 246: | 行 264: | ||
=== 初期条件 === | === 初期条件 === | ||
- | -1など、重さ $j$ が処理済/未処理であることが区別できる値で埋めておく | + | $DP[0][0]=0$ |
+ | |||
+ | 他は、重さ $j$ が実現可能/不可能であることが区別できるよう、-1など正しい重さになり得ない値で埋めておく | ||
- | DP[0][0]=0 | ||
=== 優先順位 === | === 優先順位 === | ||
行 257: | 行 276: | ||
ある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$ となり、重さと丈夫さの和が小さいブロックから上にした方がよいことが分かる。 | + | |
=== 遷移 === | === 遷移 === | ||
行 347: | 行 364: | ||
=== データ === | === データ === | ||
- | $DP[i][j]=$ Sマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが自身を含め $j=[0: | + | $DP[i][j]=$ Sマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め $j=[0: |
さらに、最終的に必要なのは通過した壁マスが(偶数個)-(奇数個)の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える(=[[wpjp> | さらに、最終的に必要なのは通過した壁マスが(偶数個)-(奇数個)の情報だけで、かつ偶数個でも奇数個でも遷移はかけ算のみで行える(=[[wpjp> | ||
- | $DP[i]=$ Sマスから $i$ 個目の壁マスまでの、今まで少なくとも通過した壁マスが(偶数個の場合の経路数)-(奇数個の場合の経路数) | + | $DP[i]=$ Sマスから $i$ 個目の壁マスまでの、通過した壁マスが少なくとも自身を含め(偶数個の場合の経路数)-(奇数個の場合の経路数) |
=== 初期条件 === | === 初期条件 === | ||
行 360: | 行 377: | ||
つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。 | つまり、右か下に移動する特性上、ソート順で後→前の順番で通過することはできない。 | ||
- | これにより、$i$ 番目の壁マスを考えるとき、$DP[1]~DP[i-1]$ に付いては確定していることを保証できる。 | + | これにより、$i$ 番目の壁マスを考えるとき、$DP[1]~DP[i-1]$ については確定していることを保証できる。 |
$i$ 番目の壁マスを考える。Sマスと $1~i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。 | $i$ 番目の壁マスを考える。Sマスと $1~i-1$ 番目の壁マスの、それぞれからの$i$ 番目の壁への経路数を求める。 | ||
行 373: | 行 390: | ||
$\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] では(偶数個)-(奇数個)の値だったものが、遷移すると |
計算の便宜上、Gマスも" | 計算の便宜上、Gマスも" | ||
(本来は壁マスでないGマスを壁マスとして計算しているため、DP上では正負逆転した値となっている) | (本来は壁マスでないGマスを壁マスとして計算しているため、DP上では正負逆転した値となっている) | ||
+ | |||
+ | %%c++%% の場合は負数%正数が負になるので注意。Pythonでは正となるので、そのまま出力できる。 | ||
<sxh python> | <sxh python> |