AtCoder Regular Contest 032 復習

はい。
http://arc032.contest.atcoder.jp/

A - ホリドッグ

素数であるかどうか見るのにアレだった。

python

def jg(t):
    i=2
    if t==1 or t==0:
        return 0
    while i**2<=t:
        if t%i==0:
            return 0
        i+=1
    return 1
n=int(raw_input())
chk=(1+n)*(n/2)
if n%2:
    chk+=(n+1)/2
 
print 'WANWAN' if jg(chk) else 'BOWWOW'

n=2の時しか素数にならないらしいので総和も素数も何も調べずに print 'WANWAN' if input()==2 else 'BOWWOW' で書けます。。

B - 道路工事

UnionFindの練習用？になるような問題っぽい？？

python

class UnionFind:
    def __init__(self, size):
        self.rank=[0]*size
        self.par=range(size)
        self.g_num=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):
        return self.find(x)==self.find(y)

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:
            return

        self.g_num-=1
        if self.rank[x]>self.rank[y]:
            self.par[y]=x
        else:
            self.par[x]=y
            if self.rank[x]==self.rank[y]:
                self.rank[y]+=1

    def group_num(self):
        return self.g_num

N,M=map(int,raw_input().split())
uf=UnionFind(N)

for i in range(M):
    a,b=map(int,raw_input().split())
    uf.unite(a-1,b-1)

print uf.group_num()-1

はい。先日のパクリのUnionFindそのまま使って既にあるグループ数-1で全ての交差点が行けるようになる最小の道路数とした。これもう少し追記したいのですけど後でで...φ(・ω・`c⌒っ