ARC085-E MUL - Python奮闘記

問題

数列\(A\)がある。ある\(i\)を選んで\(i\)の倍数のindexの要素を消し去る、という操作を繰り返せる。残った数列の合計値の最大を求める。

気持ち

操作全体は、要素をふたつ(選ばれるor選ばれない)に分けるものとみなせる。bit探索は思い浮かぶが、当然間に合わない。

ところで要素をふたつに分けるのはグラフにカットを入れる操作と見ることもできる。選ばれた側と選ばれなかった側に分けるという。そうすると最小カット問題に帰着させる発想が生まれる。最小にしたいのは今は「損」な分であるから、辺の重みは基本「損する重み」を設定する。辺がカットの対象となった時(=辺の両端が違うグループに属するようにした場合)、相応の罰金を支払う、と捉えてもいい。

さらに具体化していくと、

S側は叩き割られたもの、T側は残されたもの
\(a>0\)のものは基本残したい。叩き割る際に罰金が発生するようにしたい。つまりS側に属するようになった時に罰金を背負わせたいので、Tとの間に辺を張る。
\(a\le0\)のものは基本叩きわりたい。上と逆の理由で、Sとの間に辺を張る。
一番めんどそうな拘束条件。\(i, j\)(\(j\)は\(i\)の倍数)に対して、「\(i\)がS側に属する\(\Rightarrow\)\(j\)がS側に属する」と言い換えられる。これは破られて欲しくないという気持ちをこめて、\(i\)から\(j\)に罰金infの辺を張る。

とうまくはめられる。最小カット問題は最大流問題と等価なので、解ける。

ACコード

Submission #19252377 - AtCoder Regular Contest 085

(ライブラリは省略)

import sys
input = sys.stdin.buffer.readline
 
INF = 10**18
 
N = int(input())
A = list(map(int, input().rstrip().split()))
 
s = N
t = N+1
 
dinic = Dinic(N+2)
base = 0
for i, a in enumerate(A):
    if a > 0:
        base += a
        dinic.add_edge(i, t, a)
    else:
        dinic.add_edge(s, i, -a)
        for j in range(2*i+1, N, i+1):
            dinic.add_edge(i, j, INF)
 
c = dinic.flow(s, t)
print(base-c)

感想

制約からフローありえるかもとは思ったが、最大流についてばかり考えていて「流すのに自由度あって拘束条件反映できなくね？」となって方針を捨ててしまった。ふたつに割り振るのをカットとみなすのはなかなか面白い。今後役立つ知見かもしれないので記事にもしておいた。