日々drdrする人のメモ

今日もdrdr、明日もdrdr

ARC085 - E問題: MUL

昔いろいろ考えたけど、書き忘れた問題
問題: E - MUL

問題

1, 2, ..., Nの番号がついたN個の宝石がある。ここから宝石を壊していくが、番号iの宝石を残すと {a_i}円得られる。
数字xを選び、xの倍数の番号がついた宝石を壊すという操作を0回以上行う時、最大で得られる円を求める。

解法

この問題はProject Selection Problemとして考えられ、最小カットで解を求められる。

Project Selection Problemについては以下を参考:
Max-flow min-cut theorem - Wikipedia
最小カットを使って「燃やす埋める問題」を解く
tokoharuさんの"LPとグラフと定式化"

フローの始点を {S}, 終点を {T}とし、番号iの宝石の頂点を {V_i}とする。
各iについて {a_i > 0}の時はコスト {a_i} {S \rightarrow V_i}の辺をはり、 {a_i < 0}の時はコスト {-a_i} {V_i \rightarrow T}の辺をはる。
また、番号xの宝石を破壊した時、xの倍数全ての宝石を必ず壊さないといけないということを表すために、コスト {\infty} {V_{kx} \rightarrow V_x (k > 1)}の辺をはる。

その上で {S}から {T}への最大流を計算し、
 {\sum_i \max(0, a_i) - \text{maxflow}(S, T)}を解として出力する。


この最小カットは具体例を考えた方が、なぜこのように辺を張るのかがわかりやすそうなので、具体例を書いておく。

まず、問題の入力例1を考える。

6
1 2 -6 4 5 3

この場合は以下の図のようにグラフが構築され、最小カットが求まる。
f:id:smijake3:20180504011156p:plain
最小カットにより、壊す方と壊さない方の2つのグループに分断される。
この最小カットで求まった流量3は番号6の宝石を壊すことによる損失である。

また、問題の入力例4を考える。

2
-10000 100000

この場合は以下のように最小カットが求まる。
f:id:smijake3:20180504012822p:plain
この最小カットでも止まった流量10000は番号1の宝石を壊さないことによる損失である。


今回の最小カットの結果について、以下の解釈でよさそう

  • カットした結果、始点Sから到達できる {V_i}は壊さない宝石、到達できない {V_i}は壊す宝石
  • カットされた辺が獲得円を減少させる原因になったもの
    • カットする辺候補が複数存在する場合は、どこに原因を着地させても結果は変わらない


提出 (Python3): Submission #2451765 - AtCoder Regular Contest 085

N = int(input())
*A, = map(int, input().split())
dinic = Dinic(N+2)

INF = 10**18

su = 0
for x in range(1, N+1):
    a = A[x-1]
    if a > 0:
        su += a
        # コストa の S -> V_x の辺をはる
        dinic.add_edge(0, x+1, a)
    elif a < 0:
        # コスト-a の V_x -> T の辺をはる
        dinic.add_edge(x+1, 1, -a)

# コスト∞ の V_{kx} -> V_x の辺をはる
for x in range(1, N+1):
    for y in range(x+x, N+1, x):
        dinic.add_edge(y+1, x+1, INF)

print(su - dinic.max_flow(0, 1))