実行時のスタックサイズの調整について

[riantkb]

スタックサイズが小さく、再帰が深いようなコードがスタックオーバーフローするため、ulimit -s で調整した方が良いかもしれません。

詳細

OS のデフォルトだとスタックサイズが小さく設定されており、競技プログラミングでたまに登場するような多少複雑な 10^5 回オーダーで再帰するような関数を実行しようとするとスタックオーバーフローが起きることがあります。 そのため、ジャッジシステムの中ではスタックサイズを拡張しているものもあります。

現状、mojacoder の playground では RE になり、atcoder のコードテストでは動くようなコードに例えば以下のようなものがあります。

import sys
sys.setrecursionlimit(2 ** 20)

def calc(x):
    if x == 0:
        return x
    else:
        return 1 + calc(x - 1)

print(calc(30000))

#include<bits/stdc++.h>
using namespace std;

long long f(int p, const vector<vector<int>>& edge, int& cnt) {
    long long res = 0;
    int c = cnt;
    ++cnt;
    for (auto& i : edge[p]) {
        res += f(i, edge, cnt);
    }
    res += cnt - c;
    return res;
}

int main() {
    int n = 200000;
    vector<vector<int>> edge(n);
    for (int i = 0; i < n - 1; ++i) {
        edge[i] = {i + 1};
    }
    int cnt = 0;
    cout << f(0, edge, cnt) << '\n';
    cout << cnt << '\n';
    return 0;
}

また、本日開催されたコンテストでもスタックサイズが原因で dfs 等を用いた解法が通らなかった、ということが起きていたようです。

解決方法

ulimit -s でスタックサイズを指定してあげると解決するのではないかと考えています。 atcoder では 1048576 (kbytes)、library-checker では unlimited が指定されていそう なので、その辺りを指定するのが良いと思います（playground で調べた限り mojacoder の現状のスタックサイズは 10240 (kbytes) だと思われます）。

コードの変更自体は、以下の部分で ulimit を指定しているタイミングで同時に指定してあげれば済むと思っています。（そのくらい自分でやれという気もしています、誤差ジャッジの件といいすみません……） https://github.com/makutamoto/mojacoder/blob/b9f3f86f943f71d814e59399f61c08ac64e5220f/mojacoder-backend/judge-image/run.go#L30