目次
AtCoder Grand Contest 034 C,D,E 問題メモ
C - Tests
問題
- AさんとBさんが $N$ 個のテストで対決する
- Aさんは各テストに係数 $c_i$ を定めることができる。$c_i$ はテスト毎に決められた範囲 $l_i$ 以上 $u_i$ 以下でなければならない
- 総合的なスコアは $c_i \times (テスト i の得点)$ の全テストの合計点であり、これが高い方が勝ちとなる
- 今、AさんはBさんの全てのテストの得点を知っていて、$b_1,b_2,...,b_N$ である
- Aさん自身はこのままでは全てのテストで0点を取ってしまうが、1時間勉強するとどれか1つのテストの点数を1点上げることができる
- ただし、満点は全テスト共通で $X$ 点であり、1つのテストでこれを超える点数を取ることはできない
- AさんがBさんに勝つか引き分けるために、最低限勉強しなければならない時間を求めよ
- $1 \le N \le 10^5$
- $1 \le X \le 10^5$
- $1 \le l_i \le u_i \le 10^5$
解法
具体例から考える癖があるので、WAが出たときに具体例が構築しにくい問題は路頭に迷ってしまう。
$c_i$ の決定方針
$c_i$ は $l_i～u_i$ のどの数値でも取れるが、実際は $l_i$ か $u_i$ のどちらかでいい。各テストの得点につき、
- 同点ならどちらでもよい
- Aさんが高いなら $u_i$ を設定して、勝っている1点の価値を最大まで高めた方がよい
- Bさんが高いなら $l_i$ を設定して、負けている1点の価値をできる限り低めた方がよい
勉強するテストの方針
ひとまず、Aさんは全て $c_i$ を $l_i$ に設定する。Bさんは $\sum_i{l_i \times b_i}$ 点を取り、これが最低値。Aさんが縮めるべきスコアノルマでもある。
Aさんは、ある指標に基づいてテストを1つ選ぶ。一度選んだテストについては（途中でノルマが無くならない限り）満点まで勉強するのが良い。 途中まで勉強して他に手を付けるなら、最初からそちらを選んでいた方がよい。
選んだテストの $c_i$ を $u_i$ に変更する。Bさんのスコアは $b_i (u_i-l_i)$ 点上がるが、Aさんも新規に $u_i \times X$ 点を得る。
差し引き $u_i X - b_i (u_i-l_i)$ がテスト $i$ で満点を取ることで縮められる差なので、これが大きい方から選んで、ノルマが無くなる手前まで勉強していく。
端数
いくつかのテストで満点まで勉強して、Aさんが取るべきスコアノルマが $R$ 点残っていたとする。
すると、残りのテストから1つ選んで、$R \le b_i \times l_i$ なら $\displaystyle ceil(\frac{R}{l_i})$ だけ勉強し、 そうでないなら $c_i$ を $u_i$ にして $\displaystyle ceil(\frac{R+b_i \times (u_i-l_i)}{u_i})$ だけ勉強すればよい。
問題はその1つをどう選ぶかだが、「先に満点を取るテストを最大限確定させてから、端数処理するテストを残りの中で全探索」していたら、WAだった。
ここを「先に満点を取るテストを最大限確定させるが、端数処理するテストは全てから探索し、 既に満点を取ったテストなら代わりに次に効率の良いテストで満点を取る」としたら通った。
満点を取ったときの点数効率が良くても、端数に使った方がよい場合もあったようだ。
これは、多分以下のようなケースを考慮できていなかったんだと思う。
ノルマ 300 テスト 1 2 3 4 5 満点で縮められる差 100 100 51 50 49
上から取っていったらテスト3で止まって、端数49をテスト4か5で処理することになるが、場合によってはテスト4で満点を取って、テスト3で端数50を処理した方がよくなる…ということは、普通にありそう。
なお、ここでテスト3を端数で使いテスト4を代わりに満点取ることにした場合、テスト5も、ノルマ300の範囲内で満点を取ることができてしまうが、これは考慮の必要は無い。 満点を取るためには $X$ 時間の勉強が必要であり、それなら始めからテスト3を勉強した方が確実にそれ以下でノルマを達成できる。
import sys
n, x = list(map(int, input().split()))
exams = []
norma = 0
for i, line in enumerate(sys.stdin):
b, l, u = map(int, line.split())
exams.append((u * x - b * (u - l), b, l, u, i))
norma += b * l
exams_sorted = sorted(exams, reverse=True)
remain_norma = norma
sub_d = -1
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
if remain_norma < d:
sub_d = d
break
remain_norma -= d
used.add(ei)
if sub_d == -1:
print(n * x)
exit()
base_ans = i * x
base_remain_norma = remain_norma
ans = 10 ** 10
for d, b, l, u, i in exams:
if i in used:
curr_remain_norma = base_remain_norma + d - sub_d
else:
curr_remain_norma = base_remain_norma
if curr_remain_norma <= b * l:
extra = (curr_remain_norma - 1) // l + 1
else:
extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
if extra > x:
continue
ans = min(ans, base_ans + extra)
print(ans)
D - Manhattan Max Matching
問題
- 平面座標の中に、赤いボールと青いボールが置かれている
- 赤いボールは $N$ マスに置かれている。$i$ 番目のマスは $(RX_i,RY_i)$ であり、そこに $RC_i$ 個置かれている
- 青いボールも $N$ マスに置かれている。$i$ 番目のマスは $(BX_i,BY_i)$ であり、そこに $BC_i$ 個置かれている
- 赤いボールと青いボールの個数の合計は等しい。これを $A$ 個とする
- 赤いボールと青いボールを1つずつ、$A$ 個のペアにする
- 1つのペアの得点は、2つのマンハッタン距離（$|rx_i-bx_j|+|ry_i-by_j|$）
- 全てのペアの得点総計を最大化せよ
- $1 \le N \le 1000$
- $0 \le X座標,Y座標 \le 10^9$
- $1 \le RC_i,BC_i \le 10$
- 制限時間: 5sec
解法
組み合わせ最適化問題は、フローが有効な解法の1つとなる可能性がある。この問題も、最小費用流問題で解ける。
ただ、そのままでは制限時間内に収まらない。
ボールの置かれたマスを1つの頂点とし、赤頂点と青頂点を直接結ぶと、最大 1000 x 1000 辺ができる。
最小費用流の計算量は、実装にも依るが $O(F|V||E|)$ とか $O(F|E|log|V|)$ とからしいのだが、（$F$ は流す流量＝この問題ではボールの個数＝最大10000） これでは1000の3乗～4乗とかになってしまう。 いくら制限時間が5秒でも無理。
ここで、解説pdfを読むと、なるほどと同時に、そんなんどないしたら思いつくねんという発想が書いてある。
マンハッタン距離は絶対値が出てくるため厄介だが、2点の位置関係によって高々4パターンに分類できる。さらに、式を整理して赤、青の座標ごとにまとめられる。
- $(rx-bx)+(ry-by)=(rx+ry)+(-bx-by)$（パターン1）
- $(bx-rx)+(ry-by)=(-rx+ry)+(bx-by)$（パターン2）
- $(rx-bx)+(by-ry)=(rx-ry)+(-bx+by)$（パターン3）
- $(bx-rx)+(by-ry)=(-rx-ry)+(bx+by)$（パターン4）
実際にマンハッタン距離を計算するときに使われるパターンは、例えば赤$(3, 5)$、青$(10, 1)$ ならパターン2とかで一意に決まるのだが、 「他のパターンの計算結果は必ずそれより小さくなる」ので、得点を最大化したら、勝手に正しいパターンが選ばれているという理屈である。
制約は、赤と青の各パターンの数が同じこと。
よって、パターンを表す頂点4つを赤と青の間に挟む。パターン数が同じになることが保証され、辺数も $O(N^2)$ から $O(N)$ に削減される。
赤 パターン 青
１ ８ ４
超始点 ／ ９ ＼ 超終点
０ ー２ 10 ５ー ７
＼ 11 ／
３ ６
計算量は $O(F|E|log|V|)$ の場合、最大で $10^9$ のオーダーくらいか。 ただし、これはそれぞれの取り得る最大値を独立に考えた場合で、実際はもう1～2桁落ちるはず。
実装
最小費用流問題は、この辺を見るとよい。今回は最大化のため、コストを正負逆転させる。
辺のコストに負が出てくるため、経路探索にDijkstraが使いにくい（ポテンシャルという概念を導入することで一応は可能だが、何をやってるのか理解が難しい……）
ただ、いろいろ見てたら、別にDijkstraでも最小費用流に用いる場合、ポテンシャル再計算のために全ての頂点まで1度はたどり着いていないといけない？ （終点に付いたら即座に探索を打ち切れるわけではない？）ため、意外と速くならなかった。
枝刈りしつつBFSで最小値を更新していく実装の方が速かった。
ただ、データの持たせ方をガラッと変えたのでそこが効いたのかも知れないし、 Dijkstraの実装をミスっていたのかもしれないし、この辺もきちんと調べておければなあ。
import sys
from collections import deque
def min_cost_flow(links, links_from, s, t, flow, n2):
remain = flow
result = 0
INF = 10 ** 12
predecessors = [0] * n2 # link_id
while remain:
# print(remain)
distances = [INF] * n2
updated = [False] * n2
distances[s] = 0
updated[s] = True
q = deque([s])
while q:
v = q.popleft()
vc = distances[v]
updated[v] = False
for li in links_from[v]:
_, u, cap, cost = links[li]
if cap == 0:
continue
new_cost = vc + cost
if new_cost >= distances[u]:
continue
distances[u] = new_cost
predecessors[u] = li
if not updated[u]:
updated[u] = True
q.append(u)
min_cap = remain
v = t
while v != s:
li = predecessors[v]
l = links[li]
min_cap = min(min_cap, l[2])
v = l[0]
v = t
while v != s:
li = predecessors[v]
l = links[li]
l[2] -= min_cap
links[li ^ 1][2] += min_cap
v = l[0]
remain -= min_cap
result -= min_cap * distances[t]
return result
n = int(input())
lines = sys.stdin.readlines()
n2 = 2 * n + 6
s, t = 0, 2 * n + 1
k1, k2, k3, k4 = range(n2 - 4, n2)
balls = 0
links_from = [[] for _ in range(n2)]
links = [] # [[src, tgt, capacity, unit_cost], ]
def add_link(s, t, cap, cost):
i = len(links)
links.append([s, t, cap, cost])
links.append([t, s, 0, -cost])
links_from[s].append(i)
links_from[t].append(i + 1)
for i in range(n):
ri = i + 1
rx, ry, rc = map(int, lines[i].split())
balls += rc
add_link(s, ri, rc, 0)
add_link(ri, k1, rc, rx + ry)
add_link(ri, k2, rc, -rx + ry)
add_link(ri, k3, rc, rx - ry)
add_link(ri, k4, rc, -rx - ry)
for i in range(n, 2 * n):
bi = i + 1
bx, by, bc = map(int, lines[i].split())
add_link(bi, t, bc, 0)
add_link(k1, bi, bc, -bx - by)
add_link(k2, bi, bc, bx - by)
add_link(k3, bi, bc, -bx + by)
add_link(k4, bi, bc, bx + by)
print(min_cost_flow(links, links_from, s, t, balls, n2))
E - Complete Compress
問題
- $N$ 頂点の木があり、$i$ 番目の辺は $a_i$ と $b_i$ を結ぶ
- 頂点 $v_1,v_2,...$ にはコマが1個置かれていて、その他の頂点にはコマは置かれていない
- 以下の操作を繰り返し行う
- 距離が2以上離れた2コマを選ぶ
- 2コマを互いに1頂点ずつ近づける
- このような操作を繰り返して全てのコマを1頂点に集められるか判定し、できるなら最短の操作回数を示せ
- $2 \le N \le 2000$
解法
全方位木DP。普通の木DP+メモ化全探索でも可。
大まかな解法は見えるが、細かな条件を詰めるのはそれなりに考察が必要。
コマが最初から1個しか無い場合は0を出力して終了。以下、コマは2箇所以上の頂点にあるとする。
集められる頂点の条件と最短手数
最短手数で1箇所に集めるなら、全てのコマを集める頂点（$r$ とする）を決め、常に $r$ との距離が短くなるように2コマを選びたい。
○--○--, ,--①--○
r ,--④
②--○--' `--③--○--⑤
①と②、④と⑤などに対して操作を行えばrとの距離は短くなるが、
③と④に対して操作してもrと③との距離は逆に遠ざかってしまうので、無駄な操作になる
必要な操作回数は、1回の操作で2コマの $r$ に対する距離を1ずつ縮められるので、$r$ を決め打ってしまえば以下で求まる。$p$ は各コマを指す。
$\displaystyle \sum_{p}(rとpとの距離) / 2$
ただし、距離の和が奇数の場合は最後にどうしても1個余るので、集められない。
①-- r --○--②
また、以下のようなケースでも $r$ には集められないので、$r$ から出ている各辺のバランスも重要となる。
①--○-- r --○--○--○--○--○--○--○--○--○--○--○--○--②
辺のバランス
満たすべきバランスについて考える。 各辺について、距離の和を分けて考えると、
０ １
○--○--, ,--①--○
r ,--④
②--○--' `--③--○--⑤
２ ７
$r$ に集められないのは、一番大きい辺の距離が大きすぎて、他の辺のコマを全て一番大きい辺のコマとペアにしても消化しきれないケースである。
ただし、1番大きい辺以下に④と⑤のような枝分かれがある場合は、あらかじめ操作しておくことで距離を1操作につき2ずつ減らせる。（この例はそれでも無理だが）
０ １
○--○--, ,--①--○
r ,--○
②--○--' `--③--㊺--○
２ ５
なので、$r$ から出ている各辺以下の距離の和を $d_{sum}$、その中で一番大きい辺以下の距離を $d_{max}$、 一番大きい辺内部であらかじめ短縮操作しておくことが出来る回数を $c_{max}$ とすると、以下の条件なら、一番大きい辺を消化しきれる。
$d_{sum}-d_{max} \ge d_{max} - 2c_{max}$ （※最大以外の辺の距離合計≧最大限短縮した後の最大辺の距離）
ただし、あらかじめ操作しておいた方がいいかどうかは、根とする頂点によって変化するので、あくまで「生の距離」と「短縮可能な回数」の2つで記録しておく。 自身上のコマと外部のコマをペアに出来る「最大回数」と「最小回数」と言い換えてもよい。
○--○--, ,--①--○ ③の位置を中心にすると、
○ ,--④ 最大辺が左の方になり、
②--○--' `-- r --○--⑤ ④と⑤は別々に消化した方がよい
５ ４
まとめると、ある頂点 $r$ に集められるかについて、
- そこからの全てのコマの距離の和 $d_{sum}$ が奇数ならアウト
- $r$ から繋がる各辺について、上記のバランスが取れていないとアウト
- 取れていたら、$d_{sum}/2$ がその頂点に集めるときの操作回数
探索
根を $r$ とした時の、各頂点の「部分木以下の距離の和」「部分木以下で短縮可能な回数」を深さ優先探索で求める。
また、距離の和を親に伝播するのに「部分木以下にあるコマの数」も必要になるので、この3つを計算する。
まず、葉のノードは（コマ数, 距離の和, 短縮回数）について、コマは0か1、距離の和と短縮回数は0である。
節について、子ノードの情報が揃ったとする。
︙
○
／｜＼
石 3 石 1 石 5
距10 距 2 距20
短 2 短 0 短 3
コマの数は、子を合計して、自身にも置かれていれば+1すればよい。
距離は、子の値に加え、親に持っていく際にコマの数だけそれぞれ1ずつ増えるので、子の距離+子のコマの数となる。
短縮回数は、子が1つだけの場合は子の値がそのまま継承される。
子が複数の場合は、上記のバランスの通り、一番距離が大きい辺を消化しきれるかどうかを確認する。
消化しきれる場合、距離の和/2 となる。求めているのは短縮可能回数なので、ここでは距離の和が奇数でも関係ない。
消化しきれない場合、あらかじめ最大辺内部で短縮できるだけした上で、最大以外の辺の距離の合計分は短縮できる。
$c_v = d_{sum}-d_{max}+c_{max}$
つまり、上記の場合、最大距離は20、短縮しても14であり、他の辺の合計12でも消化しきれない。が、とりあえず12は短縮できる。 ここに最大辺内部で行った3回を加え、15回が親頂点の短縮可能回数となる。
根とする頂点を全探索
以上の探索を行えば、$r$ に集められるかどうか、またその時の操作回数はわかる。
各頂点、親頂点とのペアで答えをメモ化しておけば、この $r$ を全探索することで答えが求まる。
または、全方位木DPで探索することも出来る。
根以外の頂点については、先ほど求めた子の部分木情報に加え、親方向の部分木の情報さえ補えば判定できる。 これを、もう一度 $r$ から深さ優先探索する過程でトップダウンで与えていく。
与え方は、1回目の探索で子ノードの情報から親の値をまとめるのと大体同じ感じ。
探索を広げようとする辺の情報を除いた上で、残りの親を含めた接続辺で情報をまとめればよい。
import sys
from heapq import nlargest
sys.setrecursionlimit(10000)
def first_dfs(v, p, stones, dists, costs):
stone = s[v]
dist = 0
cost = 0
children_dists = []
for u in links[v]:
if u == p:
continue
us, ud, uc = first_dfs(u, v, stones, dists, costs)
stone += us
dist += us + ud
cost += uc
children_dists.append((us + ud, uc))
if len(children_dists) > 1:
md, mc = max(children_dists)
if dist - md < md - mc * 2:
cost = dist - md + mc
else:
cost = dist // 2
stones[v] = stone
dists[v] = dist
costs[v] = cost
return stone, dist, cost
def second_dfs(v, p, pd, pc):
children_dists = []
dist = 0
for u in links[v]:
if u == p:
dist += pd
children_dists.append((pd, pc))
continue
ud = stones[u] + dists[u]
uc = costs[u]
dist += ud
children_dists.append((ud, uc))
# only when source and leaf node
if len(children_dists) == 1:
u = next(iter(links[v]))
return second_dfs(u, v, s[v], 0)
(md1, mc1), (md2, mc2) = nlargest(2, children_dists)
ret = INF
hd, m = divmod(dist, 2)
if m == 0 and dist - md1 >= md1 - mc1 * 2:
ret = min(ret, hd)
for u in links[v]:
if u == p:
continue
us = stones[u]
ud = dists[u]
uc = costs[u]
# dist=0 node cannot be a center
if ud == 0:
continue
usd = us + ud
if usd == md1 and uc == mc1:
md, mc = md2, mc2
else:
md, mc = md1, mc1
td = dist - usd
if td - md < md - mc * 2:
vc = td - md + mc
else:
vc = td // 2
result = second_dfs(u, v, td + (all_stones - us), vc)
ret = min(ret, result)
return ret
n = int(input())
s = list(map(int, input()))
links = [set() for _ in [0] * n]
for line in sys.stdin:
a, b = map(int, line.split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
all_stones = sum(s)
if all_stones == 1:
print(0)
exit()
stones = [0] * n # 1を根とした木の、頂点vの部分木以下（自身含む）にある石の数
dists = [0] * n # 頂点vの部分木以下にある石 x それぞれのvとの距離 の和
costs = [0] * n # 頂点v以下の石同士で、最大限頂点vに近づけておくためにできる操作の数
first_dfs(0, -1, stones, dists, costs)
INF = 10 ** 10
ret = second_dfs(0, -1, 0, 0)
print(-1 if ret == INF else ret)
