😊
【競プロ】C#でJOI問題を解く|fish - 魚/2012年 日本情報オリンピック春合宿OJ
AtCoderにてJOI(日本情報オリンピック)の問題をC#で埋めている。
AtCoderで出される問題と異なり、制約が厳しく普通に解いただけでもメモリ制限エラー(MLE)となることが多い。
今回は、「2011年 日本情報オリンピック春合宿OJ」の「fish - 魚」について記載する。
MLEへの対処
Listの配列を確保しない
横着してList配列で状態を管理しようとしていたのをソートした配列での管理に変更した。
1要素のListは4要素分のキャパシティを確保するので見た目以上にメモリを消費してしまう。
old
var cnts = new List<(int g, int b)>[N];
new
var cnts = new (int r, int g, int b)[N];
Array.Sort(cnts);
Discussion