🐡

【競プロ】C#でJOI問題を解く|ドラゴン-2011年 日本情報オリンピック春合宿OJ

2021/02/05に公開

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

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

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

https://atcoder.jp/contests/joisc2011/tasks/joisc2011_dragon

MLEへの対処

HashSetの代わりにSortedSet, Dictionaryの代わりにSortedDictionaryを使う

HashSet, DictionaryはハッシュマップでDictionary, SortedDictionaryは赤黒木なので後者は余計なメモリを確保しない。
差し替えたところギリギリながらもアクセプト。

GitHubで編集を提案

Discussion