AtCoder ABC #008 : Python練習編

ABC008に参加。C,Dに手こずったけど何とか全完。
http://abc008.contest.atcoder.jp/assignments

A - アルバム

写真の通し番号S,Tがある。
S～Tの写真枚数を答えよ。

T-S+1を答えるだけ。

import sys

N,M=map(int,raw_input().strip().split(" "))
print M-N+1

B - 投票

N人で投票を行った。
N人の投票先の名前が与えられるので、最大票数獲得者の名前を答えよ。

名前をキーとしたDictionaryを持ち、票数を数えていく。

import sys

N=input()
M={}

for i in range(0,N):
	S=raw_input().strip()
	M[S] = M.get(S,0) + 1

ma = 0
r = ""
for k in M.keys():
	if M[k] > ma:
		ma = M[k]
		r = k
print r

C - コイン

N枚のコインがあり、それぞれ数字が書かれている。
コインをランダムな順で1列に並べる。
この時左から順に各コインについて、その右側にある今見ているコインの倍数のコインがあればそれを表裏反転する。
最終的に表になっているコイン枚数の期待値を求めよ。

価値xのコインは、価値がxの約数のコインの影響を受ける。
そのようなコイン枚数がp枚あるとする。
他のコインはどうでも良いので、約数であるp枚＋価値xのコインの計(p+1)枚の並びかたは(p+1)!通り。
この時価値xのコインが表になる組み合わせを求める。
それは価値xのコインの左に偶数枚約数のコインが来ることである。

左にq枚コインが来るのは、p枚中q枚コインが来る通りに、左側q枚の組み合わせq!通りと右側(p-q)枚の組み合わせ(p-q)!通りなので、各偶数qについてそれを求めればよい。

補足

もっと単純な方法もある。

• pが偶数なら、p+1は奇数でそのうちxが偶数番目に来る確率は(p/2)/(p+1)。
• pが奇数なら、p+1は偶数でそのうちxが偶数番目に来る確率は1/2。

import sys

P = [1.0]
C = [[0.0 for j in range(106)] for i in range(106)]
for i in range(0,105):
	C[i][0]=1.0
	for j in range(1,i+1):
		C[i][j] = C[i-1][j-1] + C[i-1][j]
	P.append(P[-1]*(i+1.0))

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

ret = 0.0
for x in range(0,N):
	mul = 0
	for y in range(0,N):
		if x != y and (S[x] % S[y] == 0):
			mul += 1
	for z in range(0,mul+1,2):
		ret += C[mul][z] * P[mul-z] * P[z] / P[mul+1]

print ret

D - 金塊ゲーム

W*Hの2次元領域の各マスに金塊がある。
ここにN個の機械が置かれる。
各機械を動かすと、上下左右方向にある金塊を金塊のないマスに到達するまで回収する。
機械の動かす順番を最適化し、回収できる金塊数を最大化せよ。

長方形領域で1回機械を動かすと、その時点で機械の左上・右上・左下・右下の4つの領域に分断される。
あとは各領域でメモ化再帰を行って機械を動かし、その中の金塊数を最大化すればよい。

状態として長方形領域、すなわち左端・右端・上端・下端とO(N^4)通り。
各領域においてN個の機械の内外判定を行うので、合わせてO(N^5)。

W,Hは大きいので全長方形領域に対しメモ化再帰の領域を作るとメモリに収まらない。
しかし、左端・右端・上端・下端は高々N個しか候補がないので座標圧縮するなりmapやdictionaryを使えば問題ない。

import sys

W,H=map(int,raw_input().strip().split(" "))
N=input()
X=[]
Y=[]
for i in range(0,N):
	x,y=map(int,raw_input().strip().split(" "))
	X.append(x)
	Y.append(y)

memo = {}

def dfs(l,r,t,b):
	if l > r or t > b :
		return 0
	key = (l,r,t,b)
	if key in memo:
		return memo[key]
	
	memo[key] = 0
	for i in range(0,N):
		if X[i]>=l and X[i]<=r and Y[i]>=t and Y[i]<=b:
			memo[key] = max(memo[key], r-l+b-t+1 + 
				dfs(l,X[i]-1,t,Y[i]-1)+dfs(X[i]+1,r,t,Y[i]-1)+
				dfs(l,X[i]-1,Y[i]+1,b)+dfs(X[i]+1,r,Y[i]+1,b))
	
	return memo[key]

print dfs(1,W,1,H)

まとめ

Dはもっと工夫しないと時間あふれるかと思ったけど、意外に余裕だった。