差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/04] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/05] (現在) – [解法] ikatakos | ||
|---|---|---|---|
| 行 225: | 行 225: | ||
| * 木上の何かの数を数える問題で使うことがある | * 木上の何かの数を数える問題で使うことがある | ||
| - | * 一方の部分木にもう一方を繋ぐ or 繋がない で状態遷移する | ||
| 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。 | 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。 | ||
| 行 232: | 行 231: | ||
| * 頂点 $v$ を根とする部分木で、 | * 頂点 $v$ を根とする部分木で、 | ||
| * 今まで切った辺が $i$ 本の時の、 | * 今まで切った辺が $i$ 本の時の、 | ||
| - | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で、 | + | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で |
| * $v$ を含む連結成分の和の最小値 | * $v$ を含む連結成分の和の最小値 | ||
| * (B) $DP2[v][i]=$ | * (B) $DP2[v][i]=$ | ||
| 行 240: | 行 239: | ||
| * $v$ を含む連結成分の和の最小値 | * $v$ を含む連結成分の和の最小値 | ||
| - | ただし、$v$ を含む連結成分「以外」は、条件を満たすように切られているものとする。 | + | ただし、$v$ を含む連結成分"以外"は、条件を満たすように切られているものとする。 |
| - | 条件の1つでは、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが必ずよい。 | + | $i$ の範囲の上限は、部分木のサイズとなる。 |
| - | 「連結成分内の頂点が全て正」の場合は和は関係ないので $DP1$ は必ずしも最小値でなくてもよいような気も一瞬するが、これは暫定であるため、将来的に負の頂点と統合されて「連結成分内の和が負」の方の条件で切られることになるかも知れない。 | + | |
| - | よって両方とも、和を低く保つようにDPを行うのがよい。 | + | |
| + | (B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。 | ||
| - | FIXME | + | 本来は(A)の場合は和は関係ないので、$i$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。 |
| + | < | ||
| + | DPの中身の例 | ||
| + | v以下の部分木の辺数が3なので、DP[v][i] は i=0..3 の値をとる | ||
| + | | ||
| + | 4 --- -7 --- 3 --- 5 ... DP1[v][0] | ||
| + | 4 -|- -7 --- 3 --- 5 ... DP' | ||
| + | 4 --- -7 -|- 3 --- 5 ... DP' | ||
| + | 4 --- -7 --- 3 -|- 5 ... × 切り方が条件を満たしていない | ||
| + | → DP1[v][1] | ||
| + | 4 -|- -7 -|- 3 --- 5 ... DP' | ||
| + | 4 -|- -7 --- 3 -|- 5 ... DP' | ||
| + | 4 --- -7 -|- 3 -|- 5 ... DP' | ||
| + | → DP1[v][2] | ||
| + | 4 -|- -7 -|- 3 -|- 5 ... DP1[v][3] | ||
| + | </ | ||
| + | ===DP=== | ||
| + | |||
| + | DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。（頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数） | ||
| + | すると、上の例の '' | ||
| + | |||
| + | ==葉== | ||
| + | |||
| + | 葉頂点 $w$ の場合、1頂点のみなので次のようなDPとなる。 | ||
| + | |||
| + | * $w$ が正の場合 | ||
| + | * $DP1[w][0] = A_w$ | ||
| + | * $DP2[w][0] = A_w$ | ||
| + | * $w$ が負の場合 | ||
| + | * $DP1[w][0] =$ 不可 | ||
| + | * $DP2[w][0] = A_w$ | ||
| + | |||
| + | ==葉以外== | ||
| + | |||
| + | 葉以外の頂点 $v$ の場合、次のように子供の結果と統合する。 | ||
| + | |||
| + | まず、統合元を用意する。葉頂点と同じように作る。この時、暫定のDPを、$DP1' | ||
| + | |||
| + | 子を1つずつ統合する。子の1つを $u$ とし、$DP1[u], | ||
| + | |||
| + | * サイズ | ||
| + | * 新しい $DP1'' | ||
| + | * INFで初期化する | ||
| + | * DP1 | ||
| + | * $v$ を含む連結成分の全頂点が正でないといけないので、$v$ も正である必要がある | ||
| + | * $v$ が負なら $DP1'' | ||
| + | * $u$ からの辺をくっつける時、$DP1'' | ||
| + | * $u$ からの辺で切る時、$DP1'' | ||
| + | * ただし $DP1[u][j] < INF$、つまり $u$ で切断可能な形でないといけない | ||
| + | * DP2 | ||
| + | * $u$ からの辺をくっつける時、$DP2'' | ||
| + | * $u$ からの辺で切る時、$DP2'' | ||
| + | * ただし $DP2[u][j] < 0$、つまり $u$ で切断可能な形でないといけない | ||
| + | |||
| + | これで欲しい情報が手に入った。 | ||
| <sxh python> | <sxh python> | ||
