AtCoder ABC #040 : Python練習編

またしょうもないミスで1WAする…。
http://abc040.contest.atcoder.jp/assignments

A - 赤赤赤赤青

左端に寄せる場合と右端に寄せる場合の小さい方を取ろう。

N,X=map(int,raw_input().strip().split(" "))
print min(X-1,N-X)

B - □□□□□

縦か横を総当たりすれば、もう片方も自明に決まる。あとはその範囲で値を最小化しよう。

N=input()
mi = 101010

for w in range(1,N+1):
	h = N/w
	if h > 0:
		mi = min(mi, N-w*h + abs(w-h))

print mi

C - 柱柱柱柱柱

1つ手前か2つ手前からジャンプする手段のうち、総コストが低い方を選ぼう。

N=input()
A=map(int,raw_input().strip().split(" "))
C=[0]*N
for i in range(1,N):
	C[i] = C[i-1] + abs(A[i]-A[i-1])
	if i>1:
		C[i] = min(C[i], C[i-2] + abs(A[i]-A[i-2]))

print C[N-1]

D - 道路の老朽化対策について

N頂点M辺の無向グラフが与えられる。
各辺は作られた年が与えられる。
Q個のクエリiが与えられる。
V[i]番の頂点から、W[i]年以降に作られた辺を通って到達可能な頂点数を求めよ。

Union-Findで解く。
まず辺とクエリを年別に分類しよう。
yを200000→0までデクリメントしていき、以下を順に行う。

• W[i]=yであるクエリに対して、V[i]と連結する頂点数を求める
• y年に作られた辺に対し頂点を連結する

以下のPython解はPyPyでもTLEするので注意。

# UF
ufn = 101010
rank = [0]*ufn
cnt = [1]*ufn
par = []
for i in range(ufn):
	par.append(i)

def get(x):
	if par[x] != x:
		par[x] = get(par[x])
	return par[x]
	
def count(x):
	return cnt[get(x)]

def unite(x,y):
	x = get(x)
	y = get(y)
	if x == y:
		return x
	cnt[x] = cnt[y] = cnt[x] + cnt[y]
	if rank[x] > rank[y]:
		par[x] = y
		return y
	else:
		par[y] = x
		return x


P=[]
R=[]
for i in range(202020):
	P.append([])
	R.append([])
A=[]
B=[]
V=[]
ret=[0]*202020

N,M=map(int,raw_input().strip().split(" "))
for i in range(M):
	a,b,y=map(int,raw_input().strip().split(" "))
	A.append(a-1)
	B.append(b-1)
	R[y].append(i)

Q=input()
for i in range(Q):
	v,w=map(int,raw_input().strip().split(" "))
	V.append(v-1)
	P[w].append(i)

for i in range(202010,-1,-1):
	for p in P[i]:
		ret[p] = count(V[p])
	for r in R[i]:
		unite(A[r],B[r])

for i in range(Q):
	print ret[i]

まとめ

D問題、Yの制限みてWも1以上と思ったら、W[i]=0があって1WAした…。
いや、サンプルケース２でそのケースあったんだけど、３が先に通ったので出しちゃったんだよね。
しょうもない。