【今日の精進】ABC244G - Construct Good Path

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

問題リンク

atcoder.jp

問題概要

グラフが与えられるよ。

いくつかの頂点は奇数回、それ以外は偶数回通るような長さ 以下のパスをひとつ出力してね。

解法

存在が保証されている構築問題は、極端な場合を考えると良いことが多いです。今回の場合は木です。

木のことを考えると、BFSしながらその道中で偶奇があってなければ寄り道すればよいことがわかります。そうすると、各辺は高々4回しか通らないのでよさそうです。

根だけは調整できるスペースがありませんが、根から初めて根で終わる前提ですから、偶奇があってなければ最後に行ったのをなかったことにすればよいです。

一般のグラフの場合も、雑に全域木をとって同様にやればよいです。

提出コード

from sys import setrecursionlimit
setrecursionlimit(1<<19-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]

def dp(pos,bef):
    global ans,cnt
    for i in gr[pos]:
        if i==bef:
            continue
        ans.append(pos)
        cnt[pos]+=1
        dp(i,pos)
    ans.append(pos)
    cnt[pos]+=1
    for i in gr[pos]:
        if i==bef:
            continue
        if S[i]!=cnt[i]%2:
            ans.append(i)
            cnt[pos]+=1
            cnt[i]+=1
            ans.append(pos)

N,M=map(int,input().split())
gr=[set() for i in range(N)]
union=UnionFind(N)
for i in range(M):
    u,v=map(int,input().split())
    if not union.same(u-1,v-1):
        union.unite(u-1,v-1)
        gr[u-1].add(v-1)
        gr[v-1].add(u-1)
S=list(map(int,input()))
ans=[]
cnt=[0]*N
dp(0,-1)
if cnt[0]%2!=S[0]:
    ans.pop()
print(len(ans))
print(*[i+1 for i in ans])

Submission #48234259 - AtCoder Beginner Contest 244

感想

私りーふさんの問題に惹かれる特性でもあるの？*1

*1:「良問だったなー」→「りーふさんかい」の流れ、冗談抜きで十数回経験してます