🐕
【競プロ】C#でJOI問題を解く|プラグ-2010年 日本情報オリンピック春合宿OJ
AtCoderにてJOI(日本情報オリンピック)の問題をC#で埋めている。
AtCoderで出される問題と異なり、制約が厳しく普通に解いただけでもメモリ制限エラー(MLE)となることが多い。
今回は、「2010年 日本情報オリンピック春合宿OJ」の「プラグ」について記載する。
MLEへの対処
bool配列をBitArrayに変更
bool[]をSystem.Collections.BitArrayに差し替えるとオーバーヘッドがなくなるためかメモリを節約できた。
- ✗: https://atcoder.jp/contests/joisc2010/submissions/17897337
- ✔: https://atcoder.jp/contests/joisc2010/submissions/17897352
実はbool は内部で1バイト分確保されている。
bool[]
var boolArray = Enumerable.Repeat(true, 64).ToArray();
Console.WriteLine(Convert.ToString(Unsafe.As<bool, long>(ref boolArray[0]), 2).PadLeft(64, '0'));
// 0000000100000001000000010000000100000001000000010000000100000001
Discussion