ABC372 B問題の解説（Python）

はじめに

この記事では、ABC372のB問題を解説していきます。

ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。

ABC372　B – 3^A

問題

問題

正整数Mを3の累乗の和で表す問題です。

制約

• \(1 \leqq M \leqq 10^5 \)
• \(1 \leqq 項数 \leqq 20 \)
• \(0 \leqq 各項の3の指数 \leqq 10 \)

思考の筋道

3進数がテーマの問題です。

Mをなるべく大きな3の累乗で引く操作を、Mが0になるまで繰り返せばよいでしょう。

「Mが0になるまでの繰り返し」にはwhile文を、「なるべく大きな3の累乗で引く」にはインデックスが10, 9, …, 0と下がっていくfor文を使用しました。

コード

M = int(input())

A = []

while M > 0:
  for i in range(10, -1, -1):
    if 3 ** i <= M:
      A.append(i)
      M -= 3 ** i
      break

print(len(A))
print(*A)

以上、ABC372のB問題の解説でした！

では、またね。

リンク