読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 065参加記

はい。 ox-- 1306(+4)
http://arc065.contest.atcoder.jp
C問題のみでした。。

C - 白昼夢 / Daydream

Python2

t=raw_input()
#t=t.replace('eraser','').replace('dreamer','').replace('erase','').replace('dream','')
while len(t):
    if len(t)>10 and t[:11]=='dreameraser':
        t=t[11:]
    elif len(t)>9 and t[:10]=='dreamerase':
        t=t[10:]
    elif len(t)>6 and t[:7]=='dreamer':
        t=t[7:]
    elif len(t)>4 and t[:5]=='dream':
        t=t[5:]
    elif len(t)>5 and t[:6]=='eraser':
        t=t[6:]
    elif len(t)>4 and t[:5]=='erase':
        t=t[5:]
    else:
        break
print 'YES' if t=='' else 'NO'

3WAしてからのAC。半ばワザとと言えばワザとなのですが。。replaceを使うのとかeradreamerseとかのような並びが合ったら、dreamereraseとの区別無しで誤判定のような挙動しますしね。後ろから判定していくのはあんま考えてなかったけど後ろからのが楽だったらしい。。

D - 連結 / Connectivity

Python2

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par =range(size)
        self.grp =size
 
    def find(self, x):
        if x==self.par[x]: return x
 
        self.par[x]=self.find(self.par[x])
        return self.par[x]
 
    def same(self, x, y): #2つの頂点が同じグループであるかを判定する
        return self.find(x)==self.find(y)
 
    def unite(self, x, y): #辺で接続されている2つの頂点を投げて統合する
        x,y=self.find(x),self.find(y)
        if x==y:
            return
 
        self.grp-=1
        if self.rank[x]<self.rank[y]:
            self.par[x]=y
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
 
    def group_num(self):
        return self.grp
    def ra(self):
        return self.par
 
n,k,l=map(int,raw_input().split())
uf=UnionFind(n)
uf2=UnionFind(n)
ans=[1]*n
 
for i in range(k):
    a,b=map(int,raw_input().split())
    uf.unite(a-1,b-1)
 
for i in range(l):
    a,b=map(int,raw_input().split())
    uf2.unite(a-1,b-1)
 
q1=uf.ra()
q2=uf2.ra()
d={}
for i in range(n):
    while 1:
        if q1[i]!=q1[q1[i]]:
            q1[i]=q1[q1[i]]
        else:
            break
    while 1:
        if q2[i]!=q2[q2[i]]:
            q2[i]=q2[q2[i]]
        else:
            break
 
for i in range(n):
    if (q1[i],q2[i]) in d:
        d[(q1[i],q2[i])]+=1
    else:
        d[(q1[i],q2[i])]=1
for i in range(n):
    print d[(q1[i],q2[i])],

コンテスト中は何を数えればいいのかよく分かっていなかった。解説動画を https://www.youtube.com/watch?v=jvAX9Z7beLg 見ましょう。
UnionFindで頂点を結合していって入力を全て受け取った後に同じグループかの情報を整理した。その後は道路と線路のグループが同じ組み合わせのを数えた。