2-4-5.py がMLEエラーになります

[LittleWat]

ソースコードのgithubでの公開ありがとうございます。

ご参考までに、2-4-5.py がそのままですと、MLEエラーになりました。

pythonを使っているため起きていると思いますが、ここのdpの行列の持ち方の縦横を反転させるとMLEエラーが解消されました

pastbook-2-source-code/python/chapter2/2-4-5.py

Line 13 in e1aceba

dp = [[0] * R for i in range(1 << R)]

pythonの内部構造がわかってないですが、pythonは縦に長い行列より、横に長い行列の方がメモリ使用量が少なくて済むということでしょうか... 🤔

[tsutaj]

@LittleWat （Cc: @drken1215）

ご報告ありがとうございます。
出版当時は PyPy で通っていたのですが、言語アップデートの影響で、同じコードでも今は AC できないようです。ご不便おかけして申し訳ありません。

pythonの内部構造がわかってないですが、pythonは縦に長い行列より、横に長い行列の方がメモリ使用量が少なくて済むということでしょうか... 🤔

これは PyPy がどういう最適化を施すかによるので、なんとも言えないところです・・・

私のほうで少し試してみたところ、インデックス変換用の関数を用意し、DP 配列を 1 次元にして書いても通るようです。（次元の入れ替えは必要ありませんでした）
提出：https://atcoder.jp/contests/tdpc/submissions/58277473

また、Garbage Collector を呼ぶのも有効なようです。こちらのほうが手軽かもしれません。
提出：https://atcoder.jp/contests/tdpc/submissions/58277742

古い問題では Memory Limit が厳しいことがあり、この問題もそのひとつです。
上記のようなややテクニカルな対処が必要であることをご容赦ください。