PythonでAtCoder ABC009 D問題にて、RecursionErrorを解決したい。

Question

該当の問題

https://beta.atcoder.jp/contests/abc009/tasks/abc009_4

提出したコード

# 入力
K, M = map(int, input().split())
A = list(map(int, input().split()))
C = list(map(int, input().split()))


def atM(m):
    """
    :param m:　目的の要素の1originでの位置
    :return: Aのm番目の要素
    """

    # 目的の要素がすでにある場合
    if m in range(1, len(A)+1):
        return A[m-1]
    # 新しく計算する必要がある場合
    else:
        # 計算
        result = C[1-1] & atM(m-1)
        for i in range(m-2, m-K-1, -1):
            result = result ^ (C[m-i-1] & atM(i))
        # 追加
        A.append(result)
        return result


print(atM(M))

入力sampleへの反応

入力例1　→　正常に作動
入力例2　→　正常に作動
入力例3　→　問題発生

エラー内容

Traceback (most recent call last):
File "C:/Users/user/PycharmProjects/AtCoder/ABC/9/d.py", line 17, in <module>
print(atM(M))
File "C:/Users/user/PycharmProjects/AtCoder/ABC/9/d.py", line 10, in atM
result = C[1-1] & atM(m-1)
File "C:/Users/user/PycharmProjects/AtCoder/ABC/9/d.py", line 10, in atM
result = C[1-1] & atM(m-1)
File "C:/Users/user/PycharmProjects/AtCoder/ABC/9/d.py", line 10, in atM
result = C[1-1] & atM(m-1)
[Previous line repeated 993 more times]
File "C:/Users/user/PycharmProjects/AtCoder/ABC/9/d.py", line 7, in atM
if m in range(1, len(A)+1):
RecursionError: maximum recursion depth exceeded in comparison

---

一応無駄な計算はしないように配慮したつもりなのですが、ほかの参加者の方の回答を見てもこの簡単な対策では上手くいかないことはわかりました。
もしどなたか解決方法をご存知でしたら、御時間のある折にでもお教えいただきたく思います。
よろしくお願いします。

Answer 1

何回か同じ質問に答えたことがあります。

Python 3.x - スタックオーバーフローを回避したい(144388)｜teratail

コードの先頭に以下のように追加。

import sys
sys.setrecursionlimit(適当に大きい数)  # デフォルトは1000なので動くまで増やす

アルゴリズムの見直しが必要かどうかまでは検討していません。

Comments

[kasanegi]

回答ありがとうございます！
その方法は原理までは把握してませんが、一応耳にしてはいました。
ただ今回すべてのテストケースに通る為にどの程度の数が必要なのかは不明です。
その後の検討により、この問題はアルゴリズムの見直しで劇的な改善があるケースのようなだと分かったので、そちらの方面で考えております。
回答ありがとうございました。