AtCoder ABC #034 : Python練習編

今回は不参加でした。2WAしたので出てたら微妙な感じでした。
http://abc034.contest.atcoder.jp/assignments

A - テスト

問題文通り書くだけ。

X,Y=map(int,raw_input().strip().split(" "))

if X<Y:
	print "Better"
else:
	print "Worse"

B - ペア

奇数なら1足し、偶数なら1引こう。

N=input()

N = 1 + ((N-1)^1)
print N

C - 経路

を解くだけ。

W,H=map(int,raw_input().strip().split(" "))

a=1
b=1
mo = 1000000007

for i in range(1,W):
	a = a * i % mo
	b = b * i % mo

for i in range(1,H):
	a = a * (W-1+i) % mo
	b = b * i % mo

print a * pow(b, mo-2, mo) % mo

D - 食塩水

濃い順に使う…というのではだめで、狙った濃度に対し薄くしすぎないものを選ばないといけない。
そこまで薄くない食塩水でも、量が多いと濃度を薄めてしまう。

そこで二分探索を使おう。
答えの濃度vを二分探索し、その濃度を達成できるかどうかを判定する。
(P[i]-v)*W[i]が大きいほど濃度vの食塩水に対し余分な食塩を含んでいるので、左記の式が大きい順にソートし、上位K個を選択しよう。

N,K=map(int,raw_input().strip().split(" "))
W=[]
P=[]

def ok(v):
	V=[]
	for i in range(N):
		V.append([(P[i]-v)*W[i], i])
	V.sort()
	V.reverse()
	
	salt = water = 0
	for i in range(K):
		water += W[V[i][1]]
		salt += P[V[i][1]] * W[V[i][1]]
	
	if salt >= water * v:
		return 1
	else:
		return 0

for i in range(N):
	w,p=map(int,raw_input().strip().split(" "))
	W.append(w)
	P.append(p)

L = 0
R = 100.0
for i in range(200):
	M = (L+R)/2.0
	if ok(M):
		L = M
	else:
		R = M

print L

まとめ

Bは問題文読み間違えたし、Dはオーバーフローだし微妙な間違いばかり。