【今日の精進】ARC085E - MUL - halcの競プロ精進ブログ

Twitter(今もTwitter)*1でこんなことを言っていました。

私、丸紅コン終わったら毎日精進鯖みたいなことします(鬼畜)
1日1問もDiffが自らのレート以上の問題が解けていなかった場合爆発することにします(え？)

ちなみにレートが変わる日は変わる前のレートで考えます
— はるく@競プロ (@halc_kyopro) 2023年9月20日

少し早いですが始めます。

毎日格上の問題を倒すやつの記念すべき1日目です。

一体いつまで続けることができるのでしょうか…*2

問題リンク

atcoder.jp

問題概要

宝石が $N$ 個あって、 $i$ 番目の宝石の価値は $a_i$ だよ。(これは負になることもあるよ)

好きな数の倍数番目の宝石をすべて破壊するハンマー*3を適切に使うことで、残った宝石の価値の総和を最大化してね。

解法

燃やして埋めましょう。*4

「残す宝石」「壊す宝石」のグループに分けることを考えます。

あとで最小カットを適用することを考えると、負のコストを作ってはいけないので、以下のようにしてすべて正のコストにしておきます。

$a_i\geq 0$ の場合、先に報酬をもらっておいて、残すならコスト $0$ 、壊すならコスト $a_i$
$a_i\lt 0$ の場合、残すならコスト $-a_i$ 、壊すならコスト $0$

ところで、宝石 $i$ を壊したい場合、 $i$ の倍数の宝石をすべて壊す必要があります。

そのため、この条件を満たさなかった場合、末代まで呪われることにします。*5

ここに風呂を流せば最大フローがそのまま最小コストになるので、先にもらった報酬からこれを引くと答えが求められます。

提出コード

from atcoder import maxflow

INF=pow(2,61)-1
N=int(input())
A=list(map(int,input().split()))
gr=maxflow.MFGraph(N+2)
ans=0
for i,j in enumerate(A):
    if j>0:
        gr.add_edge(N,i,0)
        gr.add_edge(i,N+1,j)
        ans+=j
    else:
        gr.add_edge(N,i,-j)
        gr.add_edge(N+1,i,0)
for i in range(N):
    for j in range(i*2+1,N,i+1):
        gr.add_edge(i,j,INF)
print(ans-gr.flow(N,N+1))

Submission #45765472 - AtCoder Regular Contest 085

感想

PythonにもACL導入されたの嬉しいなぁ*6

橙問題の割にそこそこ典型な問題でした。

お風呂最強！*7

*1:Xと言ってる人もいるらしいですが私は知りません。

*2:5日続いたら褒めてください

*3:小回りが効かねえなぁ（半ギレ）

*4:燃やす埋める問題 [いかたこのたこつぼ]とか蟻本P.212とか参照（説明放棄）

*5:多分私はコストを $\infty$ にしろと言いたいのでしょう。

*6:ただし、私がライブラリを整備し終えたら必要なくなるものとします

*7:強いからといって振り回して泡を撒き散らしたり食べたりするのはやめましょう