Atcoder Beginner Contest #011

ABC過去問解きその4。D問題で多少手こずったがなんとか自力で解答できた。数学得意な人のD問題の解答が理解できなくてつらい。問題はこちら。

A: 来月は何月？

月が与えられるので、翌月の月を答える問題。12月の次は１月なのに注意。

print int(raw_input())%12+1

B: 名前の確認

アルファベット文字列が与えられるので、最初の文字を大文字、それ以外を小文字にして出力する問題。pythonには title() メソッドがあり、与えられた文字列の最初の文字を大文字、それ以外を小文字にしてくれる。

print raw_input().title()

C: 123引き算

ある正の整数 N が与えられる。1回の操作で1か2か3を引いていき、100回以内の操作で0にしたい。しかし3つのNG数があり、操作の途中これら数字になってしまったら失敗とみなす。それでは与えられた数字を無事0にすることができるかどうかを答える問題。

実際に与えられた数字を引いていけばいい。操作数を抑えたいので、3で引ける時は3で、だめなら2で、それもだめなら１で引いていく。途中引くことができなかったり、100回以内の操作で0にできなかったら0にすることができない場合となる。

N = int(raw_input())
NG = sorted([int(raw_input()) for _ in range(3)])
for roop in range(100):
    if N in NG:
        print "NO"
        break
    if   N-3 >= 0 and N-3 not in NG: N -= 3
    elif N-2 >= 0 and N-2 not in NG: N -= 2
    elif N-1 >= 0 and N-1 not in NG: N -= 1
    else:
        print "NO"
        break
    if N == 0:
        print "YES"
        break
else:
    print "NO"

D: 大ジャンプ

あなたははじめ (0,0) にいるが N 回のジャンプで (X,Y) に移動したい。ただし、ジャンプを一回行うとつぎの４つの移動のどれか１つがランダムで選ばれる。

• X 軸に平行に +D だけ移動する。
• X 軸に平行に −D だけ移動する。
• Y 軸に平行に +D だけ移動する。
• Y 軸に平行に −D だけ移動する。

それでは N 回のジャンプ後にあなたが (0,0) から (X,Y) に移動できている確率はいくらか、という問題。 十字路が張り巡らされた街で、ある場所から目的の場所への行き方は何通りありますか？という問題の拡張版のようなもの。

自分のやり方は次のような感じ。それぞれの軸の＋とーのジャンプ数を探索し、ジャンプ数の合計が N に合うとき、 ansにそれらの並び替えの組み合わせ数を足しあわせていく。最後に4^Nで割って確率を求めるというもの。

このやり方はあまり賢いやり方ではないように思える。最後に4で割っていくとき、最初ansは超長大整数の場合があり、そのまま4.0で割ったり1.0を掛けたりしてfloatに直そうとすると "long int too large to convert to float" というOverflowエラーになってしまう。そこで求められる精度である10^-9を実現できる10桁程度まで整数による割り算を行い、そのあと実数に変換して割り算を継続している。はじめてこういうエラーが出たので戸惑ったが、テストケースの名称が条件そのままだったのでデバッグが楽に出来た。ありがたい。

fact = {i:0 for i in range(1001)}
# 階乗を返す。一度計算した値は保存しておく。
def f(n):
    res,nn = 1,n
    while n > 0:
        if fact[n] > 0:
            res *= fact[n]
            return res
        res *= n
        n -= 1
    fact[nn] = res
    return res
 
N,D = map(int,raw_input().split())
X,Y = map(int,raw_input().split())
ans = 0
for px in xrange(N+1):
    if px*D-X < 0 or (px*D-X)%D != 0: continue
    dx = (px*D-X)/D
    for py in xrange(N-px-dx+1):
        if py*D-Y < 0 or (py*D-Y)%D != 0: continue
        dy = (py*D-Y)/D
        if px+dx+py+dy == N:
            # 矢印の並び替えを思い描いてもらえばわかりやすいと思います
            ans += f(N)/f(px)/f(dx)/f(py)/f(dy)
 
for i in range(N):
    if len(str(ans)) > 14: ans /= 4
    else: ans /= 4.0
print "%.15f"%ans