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で頂点を結合していって入力を全て受け取った後に同じグループかの情報を整理した。その後は道路と線路のグループが同じ組み合わせのを数えた。