計算量とトレードオフな雰囲気のあるメモリ制限ですが、計算量ばかりを意識してメモリの意識が疎かになることが多いので、メモリ制限についてまとめました。
はじめに
AtCoderにおけるメモリ制限は基本的に1024MB(2^10メガバイト)です。
これはintを2億5000万(2.5×10^8)個くらい格納した配列のサイズくらいです。
booleanとBitSet
ちなみにbooleanだとかなり軽く、10^9以上格納できます。さらにBitSetだと一つの真偽値を0 or 1の1bitで格納できるので、booleanの8倍格納できます。
ただし、小さいbit幅を扱うなら一つの数として所持できるintやlong(64bitまで)の方が高速です。64以上の真偽値を扱いたいならBitSetを使うことになりますが、計算速度の低下は覚悟するべきです。
BitSetの使い方
ただし、bitは右から0,1,2,3...番目とカウントします。
ちなみに...
BitSetで1の数を数えるときはbs.cardinality()でint型が帰ってきて、
int,longの場合はInteger.bitCount(num)でint型が帰ってきます。