halcの競プロ精進ブログ

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

【今日の精進】ARC112D - Skate

競プロ 今日の精進 ARC 黄Diff

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

問題リンク

atcoder.jp

問題概要

スケート場があって、何マスかにとどまれるよ。

どのマスからでもすべてのマスに行けるように、とどまれるマスを増やしたいよ。

増やすマスの最小値を求めてね。

解法

(1,1) からすべてのマスに行ければよいです。

また、すべての行またはすべての列をカバーすればよいわけです。

最初から行ける場所のほか、「ここにいければここにもいける」みたいな関係のマスがあります。これはUnionFindなどで列挙できます。

なので、UnionFindでいい感じにまとめたときの連結成分数を求めるなどの方法で解を出すことができます。1

提出コード

class UnionFind():
    def __init__(self,size):
        self.uf=[[-1,0,1] for i in range(size)]
        
    def unite(self,fir,sec):
        one=self.root(fir)
        two=self.root(sec)
        if one!=two:
            if self.uf[one][1]>self.uf[two][1]:
                one,two=two,one
            self.uf[one][0]=two
            self.uf[two][2]+=self.uf[one][2]
            if self.uf[one][1]==self.uf[two][1]:
                self.uf[two][1]+=1
    
    def same(self,fir,sec):
        return self.root(fir)==self.root(sec)
    
    def root(self,node):
        pos=node
        change=[]
        while self.uf[pos][0]!=-1:
            change.append(pos)
            pos=self.uf[pos][0]
        for i in change:
            self.uf[i][0]=pos
        return pos
    
    def size(self,node):
        return self.uf[self.root(node)][2]

H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
for i in range(-1,1):
    for j in range(-1,1):
        S[i][j]="#"
union=UnionFind(W)
for i in range(H):
    bef=-1
    for j in range(W):
        if S[i][j]=="#":
            if bef!=-1:
                union.unite(bef,j)
            bef=j
row=set()
for i in range(W):
    row.add(union.root(i))
union=UnionFind(H)
for i in range(W):
    bef=-1
    for j in range(H):
        if S[j][i]=="#":
            if bef!=-1:
                union.unite(bef,j)
            bef=j
col=set()
for i in range(H):
    col.add(union.root(i))
print(min(len(col),len(row))-1)

Submission #46402502 - AtCoder Regular Contest 112

感想

格上（ほぼ適正）ですがゆるして…2

ARCで負けたので精進のためARC多めになりそう

空いた日にやってたこと

17日目

18日目

  1. 説明が雑ですねぇ↩
  2. 日曜昼時点では格下ですらある↩