【競プロ】C#でJOI問題を解く|fish - 魚/2012年 日本情報オリンピック春合宿OJ

AtCoderにてJOI(日本情報オリンピック)の問題をC#で埋めている。

AtCoderで出される問題と異なり、制約が厳しく普通に解いただけでもメモリ制限エラー(MLE)となることが多い。

今回は、「2011年 日本情報オリンピック春合宿OJ」の「fish - 魚」について記載する。

https://atcoder.jp/contests/joisc2012/tasks/joisc2012_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);

• ✗: https://atcoder.jp/contests/joisc2012/submissions/19925608
• ✔: https://atcoder.jp/contests/joisc2012/submissions/19925793