😊
【競プロ】C#でJOI問題を解く|戦国時代-2010年 日本情報オリンピック春合宿OJ
AtCoderにてJOI(日本情報オリンピック)の問題をC#で埋めている。
AtCoderで出される問題と異なり、制約が厳しく普通に解いただけでもメモリ制限エラー(MLE)となることが多い。
今回は、「2010年 日本情報オリンピック春合宿OJ」の「戦国時代」について記載する。
TLEへの対処
制約が750msとかなり厳しい。
HashSet<int>
を使わず、List<int>
にしてDistinct()
すると多少速くなった。
MLEへの対処
O(n) の計算を O(log(n)) にする
あらかじめ
二分探索で値を取得できるように書き換えると高速化・省メモリ化を達成できた
Discussion