AtcoderでREの解消の仕方がわかりません

Question

AtcoderのEducational DP contest 02問題で、何度やってもREとなってしまうのですが、どこが悪いのかがわかりません。
入力例ではすべて正答できるのですがどのような場合にREとなっているのでしょうか？
よろしくお願いします。

以下は私の提出コードです。
リンク内容

Comments

[退会済みユーザー]

pythonではデフォルトの再帰段数制限が1,000くらいになっています。なので、Nの値が100,000などの大きな値になった時に再帰呼び出しをするとREが発生します。プログラムの先頭に以下のようなコードを入れて試してみてください。
import sys;sys.setrecursionlimit(10**6)

Answer 1

質問のコードでは、n>1000あたりで再帰回数がpythonの上限を超えランタイムエラーを起こします。
sys.setrecursionlimit()で再帰突入回数の上限を変更できます（デフォルトは通常1000）
100000を設定すればとりあえず再帰回数はクリアできますが、今度はスタックサイズが足りないのでsegmentation faultを引き起こします。atcoderの提出では同じくREになるでしょう。
これを解決するためにはresource.setrlimit()でスタックサイズを増やします。

以下のように先頭に設定を加えて実行してください。

import resource;
import random
# 再帰回数上弦を100000回に設定
sys.setrecursionlimit(100000)
# スタックサイズを無制限に設定
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

まあ、これでもACにはならずにTLEになってしまうと思います。
トップページに書いてある通り、C++かJava推奨のコンテストなので...

Comments

[sikotaro]

回答いただきありがとうございました。
REの数は減りましたがいくつかでTLEになってしまいました。
再帰を使わないコードを考えてみようと思います。