[Python] ABC011 D

問題

D – 大ジャンプ

回答

90点回答　深さ優先探索

\(4^8 = 65534 \) 通りであれば全探索ができる。

N, D = map(int, input().split())
X, Y = map(int, input().split())

def main(N, D, X, Y):
    # 割り切れない場合到達できない。
    if (X % D != 0 or Y % D != 0):
        return 0

    # 距離を標準化。
    x_std = X / D
    y_std = Y / D

    def dfs(now_x, now_y, count):
        if count == N:
            if now_x == x_std and now_y == y_std:
                return 1
            else:
                return 0
        
        result = 0
        count += 1    
        search_dires = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for search_dire in search_dires:
            next_x = now_x + search_dire[0]
            next_y = now_y + search_dire[1]
            result += dfs(next_x, next_y, count)
        return result

    result = dfs(0, 0, 0)
    return result / (4 ** N)

if __name__ == '__main__':
    print(main(N, D, X, Y))

100点　メモ化再帰

@functools.lru_cache(user_function) でメモ化再帰を行います。

from functools import lru_cache

N, D = map(int, input().split())
X, Y = map(int, input().split())


def main(N, D, X, Y):
    # 割り切れない場合到達できない。
    if (X % D != 0 or Y % D != 0):
        return .0

    # 距離を標準化。
    x_std = X / D
    y_std = Y / D

    @lru_cache(maxsize=2**20)    
    def dfs(count, now_x, now_y):
        if count == N:
            if now_x == x_std and now_y == y_std:
                return 1
            else:
                return 0
        
        result = 0
        count += 1    
        search_dires = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for search_dire in search_dires:
            next_x = now_x + search_dire[0]
            next_y = now_y + search_dire[1]
            result += dfs(count, next_x, next_y)
        return result

    result = dfs(0, 0, 0)
    return result / (4 ** N)

if __name__ == '__main__':
    print(main(N, D, X, Y))

101点回答

REが解決できず保留。

from math import factorial

N, D = map(int, input().split())
X, Y = map(int, input().split())

def comb(n, r):
    try:
        comb = factorial(n) / factorial(r) / factorial(n - r)
    except ValueError:
        print('error', n, r)
    
    return int(comb)

def main(N, D, X, Y):
    # 割り切れない場合到達できない。
    if (X % D != 0 or Y % D != 0):
        return .0

    # 距離を標準化。
    x_std = X / D
    y_std = Y / D
    
    count = 0
    for move_hor in range(0, N+1):
        move_ver = N - move_hor
        if (move_hor + x_std) % 2 != 0 or (move_ver + y_std)  % 2 != 0:
            continue
        
        # 左右に動く
        comb_move_hor = comb(N, move_hor)
        move_right = (move_hor + x_std) // 2
        if move_hor < move_right:
            continue
        comb_move_right = comb(move_hor, move_right)

        # 上下に動く
        move_up = (move_ver + y_std) // 2
        if move_ver < move_up:
            continue
        comb_move_up = comb(move_ver, move_up)

        count += comb_move_hor * comb_move_right * comb_move_up
    
    return count / (4 ** N)

if __name__ == '__main__':
    print(main(N, D, X, Y))