⛳
【競プロ】C#でJOI問題を解く|折り紙-2008年 日本情報オリンピック春合宿OJ
AtCoderにてJOI(日本情報オリンピック)の問題をC#で埋めている。
AtCoderで出される問題と異なり、制約が厳しく普通に解いただけでもメモリ制限エラー(MLE)となることが多い。
今回は、「2008年 日本情報オリンピック春合宿OJ」の「折り紙」について記載する。
MLEへの対処
値をbyteで保持
折り紙の折り方を表す変数のうち byte型で保持することにした。
old
readonly struct Paper
{
public readonly int p;
public readonly int q;
public readonly int r;
public readonly int s;
}
new
readonly struct Paper
{
public readonly int p;
public readonly int q;
public readonly byte rd; // r-p
public readonly byte sd; // s-q
}
残念ながら改善せず。
Dictionaryのサイズ指定
ほとんどずるに近いが、MLEになるテストケースで必要なDictionary<(int, int), int>のCapacityをあらかじめ指定することでMLEを回避できた。
old
Dictionary<(int, int), int> dic = new Dictionary<(int, int), int>();
new
IDictionary<(int, int), int> dic = new Dictionary<(int, int), int>(995263); // IDictionaryな意味は特に無い
.NETのDictionary<(int, int), int>のCapacityは足りなくなるとおよそ2倍になるため、メモリがギリギリなケースではCapacityの指定でなんとかなることもある。
Discussion