Atcoder Regular Contest 085
(姉貴は関係)ないです
ゲームのルールは問題参照
(同じ数字が何回も出てくるので色を付けた)
■$x$ を $N..1$ までデクリメントして、その数でたたき割ることになる宝石の価値合計が負ならたたき割る?
次のような場合で上手くいかない。
1 -50 -49 1 1 50
これをシミュレートすると、$x=6..2$までは割られず、$x=1$で全て割られてしまう。(価値は0)
実際は、$x=2,3$で割ると、価値は2になる。6番目の宝石が、2と3で共通して犠牲になるため、2つ分の働きをする(?)ことを、貪欲法では発見できない。
■燃やす埋める問題に帰結できる。
辺に負辺ができるため、最初にもらえる最大の利益をもらった上で、そこからの差分をコストで表現し、コストを最小化する。
1 | 2 | 3 | 4 | |
---|---|---|---|---|
価値 | 10 | -10 | 20 | 30 |
↓ 10+20+30=60 を最初にもらったと仮定、そこからの差分で表現
1 | 2 | 3 | 4 | |
---|---|---|---|---|
割る | 10 | 0 | 20 | 30 |
割らない | 0 | 10 | 0 | 0 |
コードは長いけど、最大流を解くDinicは自分でライブラリとして持っておけば、実際に書くのは残りの部分。最大流に置き換える発想に行き着けるかどうかが鍵。
from collections import deque class Dinic: def __init__(self, n): self.n = n self.links = [[] for _ in range(n)] self.depth = None self.progress = None def add_link(self, _from, to, cap): self.links[_from].append([cap, to, len(self.links[to])]) self.links[to].append([0, _from, len(self.links[_from]) - 1]) def bfs(self, s): depth = [-1] * self.n depth[s] = 0 q = deque([s]) while q: v = q.popleft() for cap, to, rev in self.links[v]: if cap > 0 and depth[to] < 0: depth[to] = depth[v] + 1 q.append(to) self.depth = depth def dfs(self, v, t, flow): if v == t: return flow for i, link in enumerate(self.links[v]): if i < self.progress[v]: continue self.progress[v] = i cap, to, rev = link if cap == 0 or self.depth[v] >= self.depth[to]: continue d = self.dfs(to, t, min(flow, cap)) if d == 0: continue link[0] -= d self.links[to][rev][0] += d return d return 0 def max_flow(self, s, t): flow = 0 while True: self.bfs(s) if self.depth[t] < 0: return flow self.progress = [0] * self.n current_flow = self.dfs(s, t, float('inf')) while current_flow > 0: flow += current_flow current_flow = self.dfs(s, t, float('inf')) n = int(input()) an = list(map(int, input().split())) mf = Dinic(n + 2) max_value = 0 for i, a in enumerate(an): i += 1 if a > 0: max_value += a mf.add_link(i, n + 1, a) else: mf.add_link(0, i, -a) for j in range(2 * i, n + 1, i): mf.add_link(i, j, float('inf')) print(max_value - mf.max_flow(0, n + 1))