🔥

【競プロ】C#でJOI問題を解く|インフルエンザ-2008年 日本情報オリンピック春合宿OJ

2021/02/05に公開

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

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

今回は、「2008年 日本情報オリンピック春合宿OJ」の「インフルエンザ」について記載する。

https://atcoder.jp/contests/joisc2008/tasks/joisc2008_flu

MLEへの対処

値の関係を配列ではなくDictionaryで保持

https://atcoder.jp/contests/joisc2008/submissions/17072641

始めは各都市の位置をジャグ配列で保持していた。

old
(int x, int y)[] cities = new (int,int)[N];
int[][] grid = new int[1001][1001]; // 本当はこんな書き方はできないが便宜上
for (var i = 0; i < cities.Length; i++)
    grid[cities[i].x][cities[i].y] = i;

https://atcoder.jp/contests/joisc2008/submissions/17844750

new
var grid = new Dictionary<int, int>(N * 2);
for (var i = 0; i < cities.Length; i++)
    grid[cities[i].x * 1013 + cities[i].y] = i;

* 1013 は素数を掛けてハッシュの衝突が起こりづらくなるといいなあというお気持ち。

GC.Collect()

グラフの構築後にガーベジコレクションを実行する。
多用するとTLEの原因になるので使う箇所は見極めが必要。

new
GC.Collect();
GitHubで編集を提案

Discussion