7K12 blog

猫でも分かるアルゴリズム解説

ABC161 D - Lunlun Number

f:id:tkr987:20200624083922p:plain

https://atcoder.jp/contests/abc161/submissions/14393212

  • bit全探索より柔軟な再帰全探索に慣れる
  • サンプル4がヒントで最大で3234566667しかないので10桁まで全列挙すれば良い
  • 隣接桁の絶対値が1以下だけ処理するので O(10^{10})より遥かに少ない計算量になる

f:id:tkr987:20200624084608p:plain

再帰関数はプログラミング初心者の壁になりやすい。個人的に、再帰関数を呼び出す=再帰関数の中身をコピペすることに等しい、と暗記すると理解しやすいと思っている。したがって、for文がある再帰関数をn回呼び出すのは、n重ループのfor文をコピペして書くのと同じ。n重ループfor文が一番内側のネストから処理していくことを思い出せば、再帰関数の動作も追いやすい。

 

以下のリンクも参考になる

https://drken1215.hatenablog.com/entry/2020/05/04/190252