差分
このページの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 | ||
---|---|---|---|
行 1: | 行 1: | ||
- | ======AISing Programming Contest 2019 C, | + | ======AISing Programming Contest 2019 C,D,E問題メモ====== |
[[https:// | [[https:// | ||
行 198: | 行 198: | ||
r += 1 | r += 1 | ||
print(' | print(' | ||
+ | </ | ||
+ | |||
+ | ===== E - Attack to a Tree ===== | ||
+ | |||
+ | [[https:// | ||
+ | |||
+ | ==== 問題 ==== | ||
+ | |||
+ | * $N$ 頂点の木があり、$i$ 番目の辺は $(U_i,V_i)$ を結んでいる | ||
+ | * 各頂点には $A_1, | ||
+ | * 辺を切って、全ての連結成分が以下のいずれかの条件を満たすようにしたい | ||
+ | * 連結成分内に正の値しかない | ||
+ | * 連結成分内の値の合計が負 | ||
+ | * 切るべき辺の最小数を求めよ | ||
+ | |||
+ | ==== 解法 ==== | ||
+ | |||
+ | 二乗の木DPというやつを使う。 | ||
+ | |||
+ | * [[https:// | ||
+ | |||
+ | * 根を決めて、葉から親に向かって統合していく木のDP | ||
+ | * 統合するときに、2つの部分木のサイズを $|l|,|r|$ とすると、$O(|l| \times |r|)$ の計算量がかかる | ||
+ | * 全体の計算量は、統合が $O(N)$ 回行われ、1回毎に頂点数×頂点数の計算をするのだから、あわせて $O(N^3)$ ?? | ||
+ | * だが、頂点数は最初の方は必ず小さいので、均すと実は $O(N^2)$ で行けるんだよーというテクニック | ||
+ | |||
+ | * 木上の何かの数を数える問題で使うことがある | ||
+ | |||
+ | 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。 | ||
+ | |||
+ | * (A) $DP1[v][i]=$ | ||
+ | * 頂点 $v$ を根とする部分木で、 | ||
+ | * 今まで切った辺が $i$ 本の時の、 | ||
+ | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で | ||
+ | * $v$ を含む連結成分の和の最小値 | ||
+ | * (B) $DP2[v][i]=$ | ||
+ | * 頂点 $v$ を根とする部分木で、 | ||
+ | * 今まで切った辺が $i$ 本の時の、 | ||
+ | * $v$ を含む連結成分は__どうなっててもいい__ので、 | ||
+ | * $v$ を含む連結成分の和の最小値 | ||
+ | |||
+ | ただし、$v$ を含む連結成分" | ||
+ | |||
+ | $i$ の範囲の上限は、部分木のサイズとなる。 | ||
+ | |||
+ | (B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。 | ||
+ | |||
+ | 本来は(A)の場合は和は関係ないので、$i$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。 | ||
+ | |||
+ | < | ||
+ | DPの中身の例 | ||
+ | vにとって子が3つなので、DP[v][i] は i=0..3 の値をとる | ||
+ | v | ||
+ | 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> | ||
+ | import sys | ||
+ | |||
+ | sys.setrecursionlimit(5005) | ||
+ | SENTINEL = 10 ** 13 | ||
+ | |||
+ | n = int(input()) | ||
+ | aaa = list(map(int, | ||
+ | links = [set() for _ in [0] * n] | ||
+ | for line in sys.stdin.readlines(): | ||
+ | u, v = map(int, line.split()) | ||
+ | u -= 1 | ||
+ | v -= 1 | ||
+ | links[u].add(v) | ||
+ | links[v].add(u) | ||
+ | |||
+ | |||
+ | def dfs(v, p): | ||
+ | a = aaa[v] | ||
+ | ret1 = [a] | ||
+ | ret2 = [a] | ||
+ | if a < 0: | ||
+ | ret1[0] = SENTINEL | ||
+ | |||
+ | for u in links[v]: | ||
+ | if u == p: | ||
+ | continue | ||
+ | res1, res2 = dfs(u, v) | ||
+ | new1 = [SENTINEL] * (len(ret1) + len(res1)) | ||
+ | new2 = [SENTINEL] * (len(ret2) + len(res2)) | ||
+ | for i, t in enumerate(ret1): | ||
+ | for j, s in enumerate(res1): | ||
+ | new1[i + j] = min(new1[i + j], t + s) | ||
+ | if s < SENTINEL: | ||
+ | new1[i + j + 1] = min(new1[i + j + 1], t) | ||
+ | for j, s in enumerate(res2): | ||
+ | new2[i + j] = min(new2[i + j], t + s) | ||
+ | if s < 0: | ||
+ | new1[i + j + 1] = min(new1[i + j + 1], t) | ||
+ | for i, t in enumerate(ret2): | ||
+ | for j, s in enumerate(res1): | ||
+ | new2[i + j] = min(new2[i + j], t + s) | ||
+ | if s < SENTINEL: | ||
+ | new2[i + j + 1] = min(new2[i + j + 1], t) | ||
+ | for j, s in enumerate(res2): | ||
+ | new2[i + j] = min(new2[i + j], t + s) | ||
+ | if s < 0: | ||
+ | new2[i + j + 1] = min(new2[i + j + 1], t) | ||
+ | |||
+ | # print(' | ||
+ | # print(' | ||
+ | ret1, ret2 = new1, new2 | ||
+ | |||
+ | return ret1, ret2 | ||
+ | |||
+ | |||
+ | res1, res2 = dfs(0, -1) | ||
+ | ans = 0 | ||
+ | for ans, (s1, s2) in enumerate(zip(res1, | ||
+ | if s1 < SENTINEL or s2 < 0: | ||
+ | break | ||
+ | print(ans) | ||
</ | </ | ||