U - Grouping (Educational DP Contest / DP まとめコンテスト)

Quiz

https://atcoder.jp/contests/dp/tasks/dp_u

AC

https://atcoder.jp/contests/dp/submissions/8803874

参考にした解説

https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_3

部分集合から部分集合を選ぶ全列挙

http://perogram.hateblo.jp/entry/2019/12/06/021400

無限ループでRE

f:id:peroon:20191206031217p:plain

  • rec関数で無限ループに入る箇所があり、REが起きていた
  • return code 139なので、いつもの配列の範囲外アクセスだと思いこみ、配列をvectorに書き直して、アクセスを[]から.at()に書き換えていくも直らず
  • 原因は、部分集合の中の部分集合列挙時、空集合を作ってしまうと同じrecを呼んでしまうからだった
  • 画像をよく見ると、max memory: 11MBと表示されており、これは配列のエラーでは出ない
  • この表示の場合は同じrecを呼び続けたスタックオーバーフローだろう