AtCoder ABC #036 : Python練習編

Cをライブラリ化しないとこれ以上速くするのきつそう。
http://abc036.contest.atcoder.jp/assignments

A - お茶

B/Aを切り上げる。

A,B=map(int,raw_input().strip().split(" "))
print (B+A-1)/A

B - 回転

どのマスがどのマスに移動するか、丁寧に考えていこう。

N=input()
S=[]
for i in range(N):
	S.append(raw_input())

for y in range(N):
	T=""
	for x in range(N):
		T += S[N-1-x][y]
	print T

C - 座圧

問題名通り座標圧縮するだけ。
C++の場合、mapだと速度が怖かったので、vectorをsortしてuniqueしてlower_boundを取ったが、このぐらいの数ならmapでも行けるようだ。
以下のコードはPyPyでもTLEで部分点しか取れない。

import bisect

N=input()
A=[0] * N
for i in range(N):
	A[i] = input()

V = []
for x in sorted(A):
	if len(V)==0 or x > V[-1]:
		V.append(x)

for r in A:
	print bisect.bisect_left(V,r)

D - 塗り絵

問題文をよく読むと木であることがわかるので、木DPで解いていく。
各頂点を白・黒にした場合のsubtreeの状態を順に数え上げていく。
黒頂点の子頂点は白にしかなれず、白頂点の子頂点は白黒どちらでも良い。

N=input()
M=1000000007
W=[0]*N
B=[0]*N

E = []
for i in range(N):
	E.append([])

def dfs(cur,pre):
	W[cur] = B[cur] = 1
	for r in E[cur]:
		if r != pre:
			dfs(r,cur)
			W[cur] = W[cur] * (W[r]+B[r]) % M
			B[cur] = B[cur] * W[r] % M


for i in range(N-1):
	x,y=map(int,raw_input().strip().split(" "))
	E[x-1].append(y-1)
	E[y-1].append(x-1)

dfs(0,-1)
print (W[0]+B[0])%M

まとめ

もうぼちぼちPythonでやらなくてもいいかな…。