😸

【競プロ】C#でJOI問題を解く|ナイルドットコム-2008年日本情報オリンピック春合宿OJ

2021/02/05に公開

.NET

競技プログラミング

AtCoder

tech

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

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

今回は、「2008年日本情報オリンピック春合宿OJ」の「ナイルドットコム」について記載する。

MLEへの対処

動的計画法で必要な部分のみを確保

動的計画法で $D$ 回の遷移が発生するような記述をしていた。

old

var dp = new int[D][N][2]; // 本当はこんな書き方はできないが便宜上

しかし、遷移に必要なのは前日の結果のみなので $D$ 日分を確保する必要はない。

new

var dpP = new int[N][2]; // 前回の結果
var dp = new int[N][2];
for (int d = 1; d < D; d++)
{
    // dpP を用いて dp を更新
    (dp, dpP) = (dpP, dp); // メモリを使い回す
}

確保されるメモリは sizeof(int)が4バイトなので、変更前は $4 \times 365 \times 3000 \times 2 = 8 760 000$ 、変更後は $4 \times 2 \times 3000 \times 2 = 48 000$ となった。

GC.Collect()

メモリの解放のタイミングを考えてGC.Collect()するのも重要。

適当に入れるのではなく、回収してくれる見込みがある箇所で入れる必要がある。

GitHubで編集を提案

MLEへの対処

動的計画法で必要な部分のみを確保

GC.Collect()

Discussion