ABC372 B - 3^Aを理解し忘れないようにする。

https://atcoder.jp/contests/abc372/tasks/abc372_b

問題概要

正整数$M$が与えられるので、以下のケースに合致する$N$と非負整数列$Ai$を１つ求めてください。
$\sum_{i=1}^{N} 3^{A_i} = M$、つまり　$3^{A_1} \times 3^{A_2} \times 3^{A_3} \times \dots \times 3^{A_N} = M$

自分で考えた方針

NはMaxで20なので、1...10を20回ネストしながらループを回せば良さそうだが可読性が悪い。
しかも、計算量は$O(AiN)$、つまり$10^{20}$でTLEになる。

vector<int> ans
for(a1 = 0...10) {
  for(a2 = 0...10) {
   for(a3 = 0..10) {
     20回やる
        if (3^a1 + 3^a2 + 3^a3 + .... 3^a20 == M) {
          ansにa1~a20を格納

解説見た

解法1 貪欲法

• 貪欲法を使う。Mから$3^{Ai}$の可能な限り大きい値を引いて、その後$Ai$を配列で管理して出力

参考

• 解説放送

https://algo-method.com/descriptions/95
貪欲法とは、計算量削減のために後先のことを考えず、その場その場での最善の選択を繰り返していく 考え方のこと