halcの競プロ精進ブログ

はるくが競プロしたことを書き留めるなにか

【今日の精進】ABC225G - X

競プロ 今日の精進 橙Diff ABC

毎日格上の問題を倒すやつの5日目です。

無事5日続きました。

問題リンク

atcoder.jp

問題概要

グリッドに×を書いて×が書かれた場所のスコアを最大化してね。

ただ、線分を書くのにコスト C がかかるよ。

×が繋がってるところの線分は端折って一本にしてもいいよ。

解法

ま　た　お　前　か1

安心と信頼のお風呂です。

×をつけるマスとつけないマスに分ける燃やす埋めるをしましょう。

ひとまずは、マスのスコアを本来のスコアから×をつけるための 2C を引いたものにしましょう。

そうしたら、この前のARC085E - MULの時と同じようにコストを正にします。詳しい解説はここでは省略します。2

あとは線分をつなげることを考えます。

結論からいうと、斜めに接した×が一組あるごとにスコアを C 加算すればいいです。

普通の燃やす埋めるではできないことですが、うまくグラフをつくると燃やして埋めれます。3

あとは流してゲームエンドです。

提出コード

from atcoder.maxflow import MFGraph

def calc(typ,num=None):
    if typ==1:
        return num
    elif typ==2:
        return H*W+num
    elif typ==3:
        return H*W*2+num
    elif typ==4:
        return H*W*3
    return H*W*3+1

INF=pow(2,61)-1
H,W,C=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
gr=MFGraph(calc(5)+1)
add=0
for i in range(H):
    for j in range(W):
        if A[i][j]-C*2>0:
            add+=A[i][j]-C*2
            gr.add_edge(calc(4),calc(1,i*W+j),A[i][j]-C*2)
            gr.add_edge(calc(1,i*W+j),calc(5),0)
        else:
            gr.add_edge(calc(4),calc(1,i*W+j),0)
            gr.add_edge(calc(1,i*W+j),calc(5),-(A[i][j]-C*2))
        if i<H-1 and j<W-1:
            add+=C
            gr.add_edge(calc(4),calc(2,i*W+j),C)
            gr.add_edge(calc(2,i*W+j),calc(5),0)
            gr.add_edge(calc(2,i*W+j),calc(1,i*W+j),INF)
            gr.add_edge(calc(2,i*W+j),calc(1,(i+1)*W+(j+1)),INF)
        if i>0 and j<W-1:
            add+=C
            gr.add_edge(calc(4),calc(3,i*W+j),C)
            gr.add_edge(calc(3,i*W+j),calc(5),0)
            gr.add_edge(calc(3,i*W+j),calc(1,i*W+j),INF)
            gr.add_edge(calc(3,i*W+j),calc(1,(i-1)*W+(j+1)),INF)
print(add-gr.flow(calc(4),calc(5)))

Submission #45929306 - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)

感想

Q.風呂を流す難問しか解けない人ですか？

A.否定できません。

空いた日にやってたこと

3日目

4日目

  1. 問題はわりと無作為に選んでるんですがね…↩
  2. めんどくさいからです↩
  3. 燃やす埋める問題 [いかたこのたこつぼ]とか最小カットについて - よすぽの日記にめんどくさいのですべてを譲ります↩