😊

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

2021/02/05に公開

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

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

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

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

TLEへの対処

制約が750msとかなり厳しい。

HashSet<int>を使わず、List<int>にしてDistinct()すると多少速くなった。

MLEへの対処

O(n) の計算を O(log(n)) にする

あらかじめ O(L) の計算を済ませておけば、O(1) で値を取得できる。しかし、その分メモリを多く消費してしまうし、O(L)が大きいので時間もかかってしまう。

二分探索で値を取得できるように書き換えると高速化・省メモリ化を達成できた

GitHubで編集を提案

Discussion