✅ARC085E
考えたこと
最小カット絡みであることは既知
割る割らないの二択なのでカットの問題
Nは100
ある値を選ぶとその倍数はすべて割らなければならない
無限コスト辺
割らなかった宝石に報酬がある
報酬が辺コストだと最大カットになってしまう
割った宝石に「報酬得られない」が発生すると考える
「得られない報酬」を最小化する
報酬が全部正なら「一つも割らない」が自明な解になる
負の辺がある
どう扱うか？
単純にオフセットすれば良いはずだが意味合いは？
辺の値は「割らなかった時の利益」=「割った時の損失」
損失を最小化する
割った時の損失が負のものがある
まてよ？これですべて正になったらやはりSの右で切られてしまうのでは…
公式解説
割った時の損失が負=割ると得=割らないとコスト
選ぶ数と割られる宝石を分ける必要はなかった
「xが割られていて、xの倍数が割られてないとペナルティ」でよかった
実装
最小カットを求めた後、どうやって求める値にするのか
カットを最小化することでスコアが最大化されるのでなんらかのオフセットから引くことになる
そのオフセットはサンプルデータを眺めたら「正である価格の和」だったけど、これはどういう理屈？
まず基本は「全部割らなかった時に得られる報酬は価格の和」「割ることによって損失が発生する、その損失は価格とイコール」である(左図)
これが大前提としてあった上で「負の辺があると計算の都合が悪いから消したい」が来る。
2の頂点は塗られるか塗られないかの二択なのでそのどちらでも+10されるようにする(右図)
同じ塗りで、左図より10多いコストになる
なのでオフセットも10増やす
AC
pythondef main():
INF = 9223372036854775807
N = int(input())
AS = list(map(int, input().split()))
offset = sum(max(0, x) for x in AS)
d = Dinic(N + 2)
start = N
goal = N + 1
for i in range(N):
c = AS[i]
if c > 0:
d.add_edge(i, goal, c)
else:
d.add_edge(start, i, -c)
n = i + 1
x = 2 * n
while x <= N:
d.add_edge(i, x - 1, INF)
x += n
print(offset - d.max_flow(start, goal))"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]