ARC037に参加。Bまでは通せたが、Cはバグが取れずに時間切れ。

A:全優

ある生徒の各教科のテストの点、このままいくと与えられた数列のそれぞれの値となる。しかし、1分間の勉強である科目の点を1点だけ伸ばせる。すべての科目で80点以上取るのに必要な勉強時間の最小値を答えよ。

解法

各科目ごとに80点まであと何点取ればいいかを計算して足し合わせればいい。

N = int(raw_input())
m = map(int,raw_input().split())
print sum(max(0, 80-m[i]) for i in xrange(N))

B:バウムテスト

N頂点あるグラフ中の辺をM本与えられる。このグラフの中に木がいくつあるか答えよ。

解法

DFSを使うかUnion-Findを使えばいい。下の解法はUnion-Findを使ったものである。まず繋がっている頂点についてUnionする。そのあと連結グラフごとに頂点数nodeと辺の数edgeを数えて、node == edge+1 となる連結グラフがいくつあるかを答えればいい。

# Union Find
par = [0]*110
rank = [0]*110
def init_union_find(V):
    for i in xrange(V):
        par[i] = i
        rank[i] = 0
        
def find(x):
    if par[x] == x: return x
    else:
        par[x] = find(par[x])
        return par[x]
    
def unite(x,y):
    x = find(x)
    y = find(y)
    if (x == y): return
    
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if(rank[x] == rank[y]): rank[x] += 1
 
def same(x,y):
    return find(x) == find(y)
 
N, M = map(int, raw_input().split())
init_union_find(110)
edge = [0]*110
uv = [map(int, raw_input().split()) for i in xrange(M)]
for u, v in uv:
    u -= 1; v -= 1
    unite(u, v)
for u, v in uv:
    edge[find(u-1)] += 1
 
node = [0]*110
for i in xrange(N):
    node[find(i)] += 1
 
ans = 0    
for i in xrange(N):
    if node[i] == edge[i] + 1:
        ans += 1
print ans