Python 雪子さん問題

●

yukicoder - 家を通り過ぎないランダムウォーク問題

例によってプログラミング問題です。今回は「直線上の位置0にいる雪子さんが、nの距離にある自宅に帰ろうとしています。雪子さんは酔っ払ってるので前・後ろにランダムで歩きます。ただしn*2歩あるくと疲れ果てて倒れます。雪子さんが自宅に帰れるパターンの総数を求めよ。」先日重複順列を作ろうとしていたのはこのためだったのだ。

●

これが重複順列作成の方針。こういう考え方でいってみる。初めての gif 作成。

上の図ではカーソルが全パターン最深部まで進んじゃってるけれど、本問題では全パターン網羅する必要ない。カーソルが引き返す条件を、「カーソルが2nに達したとき」「+の合計がnに達したとき」「カーソルがnに達したのに+の合計が0未満」としてみる。条件を先日の重複順列関数に足すと……。

def foo(n):

    # 家に辿り着いたルート数。
    answer = 0
    # 雪子現在地。
    yukiko = 0
    # 雪子現在歩数。
    cursor = -1
    # 雪子体力限界。
    max_cursor = n * 2 - 1
    # 歩行履歴リスト。
    lis = [0 for i in range(n * 2)]
    # 問題の都合で登場する数値。
    big_num = pow(10, 9) + 7

    # 重複順列関数に雪子条件を足したもの。
    def bar(yukiko, cursor, lis):

        nonlocal answer

        for i in [1,-1]:
            # 1歩移動。
            cursor += 1
            lis[cursor] = i
            yukiko += i

            # 帰宅。記録してから、時間よ戻れ。
            if yukiko == n:
                answer += 1
                cursor -= 1
                yukiko -= i
            # 限界の半分まできたのにまだ現在地0を超えてなかったら無理。時間よ戻れ。
            # 体力限界。時間よ戻れ。
            elif (cursor-1 == n and yukiko <= 0) or (cursor == max_cursor):
                cursor -= 1
                yukiko -= i
            # 次の1歩へ。
            else:
                yukiko, cursor, lis = bar(yukiko, cursor, lis)

        # for が終わったら時間よ戻れ。
        yukiko -= lis[cursor]
        cursor -= 1
        return yukiko, cursor, lis

    bar(yukiko, cursor, lis)
    # 問題の都合。10^9+7の余りを返却します。
    return answer % big_num

できた! とても大変であった。

●

テストケースを作って、時間を測ってみる。

# 計測開始!
import time
start = time.time()

# スタート。
import yukiko_node

# テスト。入力値、答えの順番。
test_cases = [
    [1, 1],
    [2, 3],
    [3, 4],
    [4, 19],
    [5, 26],
    [6, 144],
    [7, 197],
    [8, 1171],
    [9, 1597],
    [10, 9878],
]
for test_case in test_cases:
    answer = yukiko_node.foo(test_case[0])
    if answer != test_case[1]:
        print(f'はずれー 出題:{test_case} 今出た答え:{answer}')
        exit()


margin = time.time() - start
print(f'結果: {margin}秒')