Problem 254 めも

取り敢えず,解いた.

しかし,少し遅い.約20秒 (Core 2 Duo E8500).

もうすこし工夫して下限を求めるか,

探索方法を工夫するか,

の二択なのか?

追記 #1

ad hoc な工夫をして,約3秒になった.

しかし,もう少し綺麗な改良の方法はないのか?

追記 #2

C++ で配列使ったアルゴリズムで実装したら,約0.2秒になった.

計算結果の再利用をしまくって,かなり速くなった.

教訓

配列のサイズが大きすぎると,スタックにのらずに,セグフォになるらしい.

そういときは,newで動的に確保するべし,ってどっかで読んだ.

例えば,二次元配列の場合

int (* a)[10] = new int[N][10];

とすれば,動的に確保できるらしい.