差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] ikatakosprogramming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/05] (現在) – [解法] ikatakos
行 1: 行 1:
-======AISing Programming Contest 2019 C,D問題メモ======+======AISing Programming Contest 2019 C,D,E問題メモ======
  
 [[https://beta.atcoder.jp/contests/aising2019|AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019]] [[https://beta.atcoder.jp/contests/aising2019|AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019]]
行 12: 行 12:
   * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる   * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる
   * 白と黒を交互に踏んで上下左右に移動したい   * 白と黒を交互に踏んで上下左右に移動したい
-  * そのよう移動できる(黒マス, 白マス)の組の個数を答えよ+  * そのよう移動を繰り返して行き来できる(黒マス, 白マス)の組の個数を答えよ
   * $1 \le H,W \le 400$   * $1 \le H,W \le 400$
  
行 198: 行 198:
     r += 1     r += 1
 print('\n'.join(map(str, ans))) print('\n'.join(map(str, ans)))
 +</sxh>
 +
 +===== E - Attack to a Tree =====
 +
 +[[https://beta.atcoder.jp/contests/aising2019/tasks/aising2019_e|E - Attack to a Tree]]
 +
 +==== 問題 ====
 +
 +  * $N$ 頂点の木があり、$i$ 番目の辺は $(U_i,V_i)$ を結んでいる
 +  * 各頂点には $A_1,A_2,...,A_N$ のゼロでない値が決められている
 +  * 辺を切って、全ての連結成分が以下のいずれかの条件を満たすようにしたい
 +    * 連結成分内に正の値しかない
 +    * 連結成分内の値の合計が負
 +  * 切るべき辺の最小数を求めよ
 +
 +==== 解法 ====
 +
 +二乗の木DPというやつを使う。
 +
 +  * [[https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594|二乗の木 DP - (iwi) { 反省します - TopCoder部]]
 +
 +  * 根を決めて、葉から親に向かって統合していく木の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$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。
 +
 +<code>
 +DPの中身の例
 +  v以下の部分木の辺数が3なので、DP[v][i] は i=0..3 の値をとる
 +                    →根
 +4 --- -7 --- 3 --- 5 ...    DP1[v][0]  = 不可  DP2[v][0]  = 5
 +
 +4 -|- -7 --- 3 --- 5 ...    DP'1[v][1] = 不可  DP'2[v][1] = 1
 +4 --- -7 -|- 3 --- 5 ...    DP'1[v][1] = 8     DP'2[v][1] = 8
 +4 --- -7 --- 3 -|- 5 ... × 切り方が条件を満たしていない
 +                         → DP1[v][1]  = 8     DP2[v][1]  = 1
 +
 +4 -|- -7 -|- 3 --- 5 ...    DP'1[v][2] = 8     DP'2[v][2] = 8
 +4 -|- -7 --- 3 -|- 5 ...    DP'1[v][2] = 5     DP'2[v][2] = 5
 +4 --- -7 -|- 3 -|- 5 ...    DP'1[v][2] = 5     DP'2[v][2] = 5
 +                         → DP1[v][2]  = 5     DP2[v][2]  = 5
 +
 +4 -|- -7 -|- 3 -|- 5 ...    DP1[v][3]  = 5     DP2[v][3]  = 5
 +</code>
 +
 +===DP===
 +
 +DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。(頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数)
 +すると、上の例の ''DP1[v][1]'' のように、不可な切り方と可能な切り方が混在する場合でも、可能な切り方同士の時と同様 ''min'' を取ることで更新が行える。
 +
 +==葉==
 +
 +葉頂点 $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'[v], DP2'[v]$ と表記することにする。
 +
 +子を1つずつ統合する。子の1つを $u$ とし、$DP1[u], DP2[u]$ を $DP1'[v], DP2'[v]$ に統合する処理を考える。
 +
 +  * サイズ
 +    * 新しい $DP1''[v]$ のサイズは $len(DP1'[v]) + len(DP1[u])$ となる
 +    * INFで初期化する
 +  * DP1
 +    * $v$ を含む連結成分の全頂点が正でないといけないので、$v$ も正である必要がある
 +      * $v$ が負なら $DP1''[v]$ は全てINF
 +    * $u$ からの辺をくっつける時、$DP1''[v][i+j] ← DP1'[v][i] + DP1[u][j]$
 +    * $u$ からの辺で切る時、$DP1''[v][i+j+1] ← DP1'[v][i]$
 +      * ただし $DP1[u][j] < INF$、つまり $u$ で切断可能な形でないといけない
 +  * DP2
 +    * $u$ からの辺をくっつける時、$DP2''[v][i+j] ← DP2'[v][i] + DP2[u][j]$
 +    * $u$ からの辺で切る時、$DP2''[v][i+j+1] ← DP2'[v][i]$
 +      * ただし $DP2[u][j] < 0$、つまり $u$ で切断可能な形でないといけない
 +
 +これで欲しい情報が手に入った。
 +
 +<sxh python>
 +import sys
 +
 +sys.setrecursionlimit(5005)
 +SENTINEL = 10 ** 13
 +
 +n = int(input())
 +aaa = list(map(int, input().split()))
 +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(' ', '1', p, v, u, ret1, res1, new1)
 +        # print(' ', '2', p, v, u, ret2, res2, new2)
 +        ret1, ret2 = new1, new2
 +
 +    return ret1, ret2
 +
 +
 +res1, res2 = dfs(0, -1)
 +ans = 0
 +for ans, (s1, s2) in enumerate(zip(res1, res2)):
 +    if s1 < SENTINEL or s2 < 0:
 +        break
 +print(ans)
 </sxh> </sxh>
  
  
  
programming_algorithm/contest_history/atcoder/2019/0112_aising2019.1547362220.txt.gz · 最終更新: 2019/01/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0