😊

【競プロ】C#でJOI問題を解く|DNAの合成-2010年 日本情報オリンピック春合宿OJ

2021/02/05に公開

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

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

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

https://atcoder.jp/contests/joisc2010/tasks/joisc2010_dna

MLEへの対処

Trieを配列で実装

Trieを用いて解いた。

通常はTrie<TValue>の実装は汎用性のためにDictionary<TKey, Trie<TValue>>で遷移を定義しているが、メモリを浪費してしまうのでTrie<TValue>[]に変更した。

取りうる値が少ないときに有効な対処。

GitHubで編集を提案

Discussion