kmjp's blog

競技プログラミング参加記です

AtCoder ABC #003 : Python練習編

ARC

ABCに参加。通常4問×100点だが、1問だけおまけで+1点がついている。
本番、この400点までは非常にスムーズに行ったが、最後の1点が時間内に終わらなかった。
本番はC++だけど、ここではPythonで復習。
http://abc003.contest.atcoder.jp/assignments

A - AtCoder社の給料

1～Nの目が書かれたサイコロがあり、それぞれの目は1/Nの確率で出る。
1回サイコロを振ってその目の値×10000円がもらえるとき、平均値を答えよ。

全部素直に足しても良いし、(1+N)/2*10000でも良い。

N=input()
print (1+N)*5000

B - AtCoderトランプ

2つの文字列が与えられる。
文字列中、"@"は"atcoder"のいずれか任意の1文字と置換できるとき、両文字列を同じにできるか答えよ。

色々方法があるが、以下では各文字のうち片方でも"@"があれば、それぞれ"atocoder"の各文字を"@"にし、一致するか判定する。

S=raw_input()
T=raw_input()

ng=0
for i in range(0,len(S)):
	ss=S[i]
	tt=T[i]
	if S[i]=="@" or T[i]=="@":
		if "atcoder".find(S[i]) != -1:
			ss="@"
		if "atcoder".find(T[i]) != -1:
			tt="@"
	if ss!=tt:
		ng = 1

if ng == 0:
	print "You can win"
else:
	print "You will lose"

C - AtCoderプログラミング講座

N人のレートが整数配列R[i]で与えられる。
レートCの人がR[i]の人の動画を見るとレートが(C+R[i])/2になる。
初期レート0の人がK人の動画を見るとき、最大どのレートになれるか答えよ。

1回動画を見るたびに、Cの半分が最終的なレートに影響することから、出来るだけ最後に高いレートの動画を見るのが良い。
よって、N人中上位K人について、下から順に動画を見ていけばよい。

N,K=map(int,raw_input().strip().split(" "))
R=map(int,raw_input().strip().split(" "))

R.sort()
r=0.0

for i in range(0,K):
	r = (r+R[N-K+i])/2.0
print r

D - AtCoder社の冬

R*Cのグリッド上の各マスに、机をDマス分、ラックLマス分を置いたとき、全部の机とラックを囲う長方形はX*Yマス分となった。
このような机・ラックの置き方を答えよ。

答えは以下の積である。

  • X*YマスをR*Cマス中に配置する方法 (R-X+1)*(C-Y+1)
  • X*Yマスの中にD+L分のものを置く組み合わせ
  • D+L個分のもののうち、L個のラックマスを置く組み合わせ = {}_{D+L} C_L

最後の組み合わせはパスカルの三角形で良いとして、問題は真ん中。
100点問題の時はX*Y==D+Lなので、全部のマスを埋めるように置く1通りしかない。

X*Y > D+Lの時は、包除原理で求める。
一番上の行および下の行、左および右の列がそれぞれある・ない場合の数を求めて、除いた数のパリティによって組み合わせ数を加減算する。

ちなみに、自分は本番は4ツ角および角以外の上端・下端・左端・右端のそれぞれにものがあるかないかを2^8通り列挙しようとしたけど、本番中にバグがとりきれなかった。

mo = 1000000007
R,C=map(int,raw_input().strip().split(" "))
X,Y=map(int,raw_input().strip().split(" "))
D,L=map(int,raw_input().strip().split(" "))

co=[[0 for i in range(1000)] for j in range(1000)]

for x in range(1000):
	co[x][x]=1

for x in range(1,1000):
	for y in range(0,x+1):
		co[x][y] = (co[x-1][y-1] + co[x-1][y]) % mo

ret = 0
for i in range(16):
	xx=X
	yy=Y
	pa=0
	if i & 1:
		xx-=1
		pa+=1
	if i & 2:
		xx-=1
		pa+=1
	if i & 4:
		yy-=1
		pa+=1
	if i & 8:
		yy-=1
		pa+=1
	if xx>=0 and yy>=0 and xx*yy>=D+L:
		if pa % 2 == 0:
			ret += co[xx*yy][D+L]
		else:
			ret -= co[xx*yy][D+L]

ret = ((ret%mo)+mo)%mo
ret = ret * (R-X+1) * (C-Y+1) * co[D+L][L] % mo
print ret

まとめ

包除原理、今まであまり使う機会がなかったのでよい練習になった。