【rust】AtCoderで作成できる配列の要素数を調べてみた

配列の数を調べたくなった動機

以下の問題を解いていた時でした。

詳細は割愛しますが、

「2*10^5× Nの二次元配列を作成して解いたらいいよね」と思って実装しました。サンプルのテストケースは通りました。

意気揚々と提出すると、そこにはみるも無惨なREが…

結局コンテスト中には何が原因か分からなかったのですが、後で色々試してみると、確保していた配列のサイズが大きすぎたことが原因だと分かりました。

こんな風にしてどれだけ値を確保できるか調べました。確保できるならWAになって、確保できないならREになります。(多分)

    fn main() {
        let a = vec![0_usize; 100_000_000];
    }

調べてみたところ、WAになるのは

REになるのは、

boolのサイズは1バイトで、usizeのサイズは(多分)8バイトなので、10^9バイトくらいのサイズが確保できることになります。

usizeはシステムの環境によって左右されるとの記憶ですが、多分AtCoderのサーバでは8バイトで動いている気配を感じています。

サイズについては以下を参考にしました。

単位を換算してみると、

10^9 バイト = 10^6 キロバイト = 10^3メガバイト

10^3メガバイトってことは1000くらいってことっすね。

…

ここで、私は思い出した。

奴らに支配されたメモリ制限を。

「メモリ制限に引っかかってる…？」

と思ったけどそんなことなさそう。

そもそもメモリ制限にひっかかかるならMLE(メモリ制限超過)になるはずだし。

結局、10^9バイトが制限になる理由はよく分かりませんでした。

まあ、10^9バイト程度使うとREになることはわかったのでひとまずいいことにしましょう。

他にメモリを確保することもあるだろうし、配列のサイズは10^5とか10^6くらいを目安にするようにします。

ちなみに、この問題はVecDequeとBTreeSetを使って解きました。