0. はじめに
AtcoderのEducational DP Contestをやっていて、愚直に書くより『C:Vaction』のメモリや速度を節約できたので、アイディアを忘れないために書いておくものです。
1. 前提
- 最近Atcoderをやり始めた初心者です。なので有識者の方には常識かと存じます。
- 使用言語はPython
2. 問題
上記の記事を参考に、Educational DP Contestを順番にやっていました。
A、Bと順調に解いていて、Cも楽勝だろーと思っていたら、TLE（時間制限）に引っかかってRejectされました。
3. 解決策
大きく2つの修正によって改善しました。
3.1. 言語の変更
Python(Cython）をPython(PyPy）に変更しました。
基本的にはPyPyを使うほうが高速ですが、再帰処理を行うときだけは遅くなることに注意です。
より詳しくは↓の方の記事がためになりました。
https://qiita.com/y-oksaku/items/f0c5c4681bc30dddf7f4
3.2. 保持するDP値を最低限に減らす
実は、「3.1. 言語の変更」だけで、問題は解決していました。
ただ、保持するDP値を減らすとメモリと速度が改善したので、別の問題にも使えそうだなと思いました。
「C：Vacation」は、N日後の最大幸福度を探索する問題です。
愚直にやるならば、1日目から順番に幸福度の総和を求めていくでしょう。
※ 入力例3の場合
ただ、K日目（1 $\leq$ K $\leq$ N)の幸福度は K-1日目の幸福度と行動さえ分かればいいので、N日分のDP値を保持する必要はなく、以下のように前日分と当日分されあれば十分です。
改善前
改善後
実行時間、メモリともに改善できています。
