差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/01/13] – ikatakos | programming_algorithm:contest_history:atcoder:2019:0112_aising2019 [2019/02/04] – ikatakos | ||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======AISing Programming Contest 2019 参加記録====== | + | ======AISing Programming Contest 2019 C, |
| [[https:// | [[https:// | ||
| - | |||
| ===== C - Alternating Path ===== | ===== C - Alternating Path ===== | ||
| 行 13: | 行 12: | ||
| * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる | * 各マスは白か黒に塗られていて、各マスの色は入力として与えられる | ||
| * 白と黒を交互に踏んで上下左右に移動したい | * 白と黒を交互に踏んで上下左右に移動したい | ||
| - | * そのように移動できる（黒マス, | + | * そのような移動を繰り返して行き来できる（黒マス, |
| * $1 \le H,W \le 400$ | * $1 \le H,W \le 400$ | ||
| 行 26: | 行 25: | ||
| その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。 | その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。 | ||
| + | |||
| + | 左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。 | ||
| 一度探索したマスはそれ以降調べる必要は無い。 | 一度探索したマスはそれ以降調べる必要は無い。 | ||
| 行 88: | 行 89: | ||
| * 互いに異なる整数 $A_1 \lt A_2 \lt ... \lt A_N$ が書かれた $N$ 枚のカードが場にある | * 互いに異なる整数 $A_1 \lt A_2 \lt ... \lt A_N$ が書かれた $N$ 枚のカードが場にある | ||
| - | * 先手と後手の2人がゲームをする | + | * 先手と後手の2人が順にカードを取っていく |
| - | * 開始前に後手は、ある整数 $x$ を決める | + | * 開始前に、ある整数 $x$ を決める |
| * 先手は、その時に場にある最も大きいカードを取る | * 先手は、その時に場にある最も大きいカードを取る | ||
| * 後手は、その時に場にある最も $x$ に近いカードを取る。同率の場合は小さい方を取る | * 後手は、その時に場にある最も $x$ に近いカードを取る。同率の場合は小さい方を取る | ||
| 行 156: | 行 157: | ||
| ==実装== | ==実装== | ||
| - | 変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時のスコアで初期化する。 | + | 変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時の先手の合計点で初期化する。 |
| クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。 | クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。 | ||
| 行 165: | 行 166: | ||
| ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$ | ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$ | ||
| + | |||
| + | $l$ を2、$r$ を1加算し、$l=r$ になる直前まで繰り返す。 | ||
| 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | 最後まで残ったクエリは、$x=21$の様に完全に交互になる。 | ||
| 行 195: | 行 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)$ で行けるんだよーというテクニック | ||
| + | |||
| + | * 木上の何かの数を数える問題で使うことがある | ||
| + | * 一方の部分木にもう一方を繋ぐ or 繋がない で状態遷移する | ||
| + | |||
| + | 今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。 | ||
| + | |||
| + | * (A) $DP1[v][i]=$ | ||
| + | * 頂点 $v$ を根とする部分木で、 | ||
| + | * 今まで切った辺が $i$ 本の時の、 | ||
| + | * $v$ を含む連結成分の__頂点の値が全て正であるような切り方__の中で、 | ||
| + | * $v$ を含む連結成分の和の最小値 | ||
| + | * (B) $DP2[v][i]=$ | ||
| + | * 頂点 $v$ を根とする部分木で、 | ||
| + | * 今まで切った辺が $i$ 本の時の、 | ||
| + | * $v$ を含む連結成分は__どうなっててもいい__ので、 | ||
| + | * $v$ を含む連結成分の和の最小値 | ||
| + | |||
| + | ただし、$v$ を含む連結成分「以外」は、条件を満たすように切られているものとする。 | ||
| + | |||
| + | 条件の1つでは、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが必ずよい。 | ||
| + | 「連結成分内の頂点が全て正」の場合は和は関係ないので $DP1$ は必ずしも最小値でなくてもよいような気も一瞬するが、これは暫定であるため、将来的に負の頂点と統合されて「連結成分内の和が負」の方の条件で切られることになるかも知れない。 | ||
| + | よって両方とも、和を低く保つようにDPを行うのがよい。 | ||
| + | |||
| + | |||
| + | FIXME | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | <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) | ||
| </ | </ | ||
