ABC135-D DP 精進しよう / stack の大きさ

30分ほど考えてもTLEしない方針すら立たなかったため、解説を読んだ。が、眠い頭ではなかなかわからなかったのでとりあえず写経し、8ケースでバグったので最速正解者のコードに合わせて修正したら通った。

解法は動的計画法で、文字列を左から順番に見ていき、ある桁を見たときにその桁が i だったとして、その直前のすぐ左の桁までで構成される数字が n だったとすれば、単純に n * 10 + i を 13 で割った余りこそが、今見ている桁までで構成される数字を 13 で割った余り r となる。 d = n % 13 とすれば、すでに割り切れた部分を 10 倍してもどうせ 13 で割り切れるので、 r = (d * 10 + i) % 13 となる。この余りだけ足して 13 で割って、を最後まで続けると答えが求まる。

ちなみにバグの原因は main 関数内で配列を宣言したことによるサイズ不足だったと思われる。ローカル変数は stack に置かれるが、stack はあまり大きくないので大きな配列でおかしなことが起こるらしい。対策としては、関数外で宣言する、static つける、new や malloc で動的に宣言する、vector 使うなどがある。（参考リンク1、参考リンク2）

実際配列をグローバル変数として宣言したり static つけたりしたら通った。

バグったときに RE (runtime error) が返ってこなかったということは、配列のサイズが不足しても stack overflow にならないことがあるんだろうか。 vector 使うのが安全かなー。

ちなみに今夜のイカはナワバリのみでした。