2019-12-17

AtCoder Beginner Contest 146：D - Coloring Edges on Tree

問題
解法
解答

問題

https://atcoder.jp/contests/abc146/tasks/abc146_d

解法

まず，最も多くの辺が繋がっている頂点がもつ辺の数が必要となる色の数になる．また，ある 1 つの頂点を木の根とし，そこから辺を塗っていく DFS をする．具体的には，(今いる頂点, 親の頂点, 親と今いる頂点間の辺の色) の情報を持っておき，今いる頂点から伸びている辺は，色 (親と今いる頂点間の辺の色 + k (1 <= k <= 今いる頂点から子に伸びている辺の数)) で塗ればよい（色は mod K にする必要がある）．最後に，入力で与えられた辺の順番通りに答えを出力しなければいけないので，DFS で塗っていった順番から変換する必要がある．ここでソートなどを使うと O(NlogN)．

解答

https://atcoder.jp/contests/abc146/submissions/8987520

f:id:babcs2035:20191217135001p:plain

2019-12-16

AtCoder Beginner Contest 147：E - Balanced Path

競技プログラミング AtCoder 500 点問題

問題
解法
解答

問題

https://atcoder.jp/contests/abc147/tasks/abc147_e

解法

dp(i, j, k) := マス (0, 0) からマス (i, j) までのパスで「偏り」が（以上でも以下でもなく）k となるかどうか

という DP を考えると，遷移は (0, 0, |A[0][0] - B[0][0]|) から始めて，

dp(i + 1, j, m1) = true

dp(i + 1, j, m2) = true

dp(i, j + 1, m1) = true

dp(i, j + 1, m2) = true

（ただし，m1 = |k - d|, m2 = k + d）

となる．m1, m2 は「偏り」が小さくなるか大きくなるかの 2 通りを試すことを意味している．答えは dp(H - 1, W - 1, k) が true であるような最小の k になる．「偏り」の最大が 80 * (H + W - 1) となるから，計算量は O(HW * 80(H + W - 1))．