kmjp's blog

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

AtCoder ABC #011 : Python練習編

ARC

ABC011は不参加。
最近のABCの中では若干難易度低目。
http://abc011.contest.atcoder.jp/assignments

A - 来月は何月？

与えられた翌月が何月か答える。
12月の時だけ翌月を1月と答えればよい。

import sys
N=input()+1
if N>12:
	N-=12

print N

B - 名前の確認

文字列が与えられるので、先頭を大文字に、それ以外を小文字にする。
Pythonはupper/lower関数があるので楽だね。

import sys

S=raw_input().strip().lower()
print S[0].upper() + S[1:]

C - 123引き算

Nが与えられるので、最大100回、1か2か3を引いて0に出来るか。
ただしNG値３つを経由してはならない。

NG値にならない範囲で、出来るだけ多くの数値を引き、100回後に0になっていればok。

import sys

N=input()
NG1=input()
NG2=input()
NG3=input()

if N==NG1 or N==NG2 or N==NG3:
	print "NO"
	sys.exit(0)

for i in range(0,100):
	j=min(3,N)
	while j>0 and (N-j==NG1 or N-j==NG2 or N-j==NG3):
		j-=1
	N-=j

if N==0:
	print "YES"
else:
	print "NO"

D - 大ジャンプ

初期状態で座標(X,Y)にいる。
上下左右のいずれかの方向に1/4の確率で長さDだけ移動、をN回繰り返したとき、原点に戻る確率を求めよ。

まず、X,YがDで割り切れない場合はそもそも原点にたどり着けない。
それ以外の場合、原点に戻る上下左右の移動回数u,d,l,rの条件は以下のように３つの式で表現できる。

  • u+d+l+r = N
  • l-r = X/D
  • d-u = Y/D

４変数で３式なので、１個変数を決め打ちすれば他の３つの値も決まる。
そこで１変数を総当たりすればよい。
上下左右の移動回数が決まると、その発生確率は以下の通りなので、これらを足し合わせればよい。
{}_{u+d+l+r} C_{u} \times {}_{d+l+r} C_{d} \times {}_{l+r} C_{l} \times 4^{-N}

なお、普通に上記式を計算するとNが大きい場合特に4^(-N)の計算結果の桁が小さすぎてdoubleにも収まらなくなる。
以下の方法では、Combinationの前計算の時点でCが小さくなるようにしておき、最後の4^(-N)の部分がここまで精度が落ちないようにしている。

import sys
import math

C = [[0 for j in range(1002)] for i in range(1002)]

C[0][0]=1.0
for i in range(0,1001):
	for j in range(0,1001):
		C[i+1][j] += C[i][j]/2.0
		C[i+1][j+1] += C[i][j]/2.0

N,D=map(int,raw_input().split(' '))
X,Y=map(abs,map(int,raw_input().split(' ')))

xp = X/D
yp = Y/D

if (xp+yp)%2 != N%2 or X%D>0 or Y%D>0:
	print 0.0
	sys.exit()

ret = 0.0
for x1 in range(0,N+1):
	x2 = x1-xp
	y1 = yp+(N-x1-x2-yp)/2
	y2 = (N-x1-x2-yp)/2
	if x2<0 or y1<0 or y2<0:
		continue
	ret += C[N][x1]*C[N-x1][x2]*C[N-x1-x2][y1]*pow(0.5,2*N-(N+N-x1+N-x1-x2))

print ret

まとめ

Dは解き方はさほどでもないけど、精度の問題が若干厄介だったね。