🐢

[ABC372 B] 3^A

2024/11/22に公開

Ruby

3進数な問題。

問題を要約する

3を累乗したときの結果の合計が M のときその指数の並びは？

例1で問題を理解する

M が 6 なので、

3**1  # => 3
3**1  # => 3

で合計が 6 になるので 1 1 が答え。

最初に書いたもの

M = gets.to_i    # => 6
def f(sum, a)
  (1..10).each do |i|
    sum += 3**i  # => 3, 6, 15, 12
    if sum == M
      a << i     # => [1, 1]
    elsif sum < M
      a << i
      f(sum, a)
    else
      break
    end
  end
  a
end
ans = f(0, [])   # => [1, 1]
puts ans.size
puts ans * " "

これは例2でフリーズした。

ちゃんと考える

M = gets.to_i  # => 100

なんとなくだけど 100 からはいきなり 81 を引きたい。3 の累乗の大きいものかつ100以下の値を順に引いていきたい。

3の累乗は、

(1..10).collect { |i| 3**i }  # => [3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049]

なので大きい値から引いていくと、

3**4  # => 81
3**2  # => 9
3**2  # => 9
3**0  # => 1

とすればちょうど 100 になって、

[81, 9, 9, 1].sum  # => 100

指数の並び 4 2 2 0 が答えになる。それを自動的に出すには、

r = M
a = 10.downto(0).find { |i| r >= 3**i }  # => 4
r -= 3**a
a = 10.downto(0).find { |i| r >= 3**i }  # => 2
r -= 3**a
a = 10.downto(0).find { |i| r >= 3**i }  # => 2
r -= 3**a
a = 10.downto(0).find { |i| r >= 3**i }  # => 0
r -= 3**a

とすればよくて 0 になったら終わるところまで自動化して、

r = M
ans = []
while r != 0
  a = 10.downto(0).find { |i| r >= 3**i }  # => 4, 2, 2, 0
  r -= 3**a                                # => 19, 10, 1, 0
  ans << a
end
ans                                        # => [4, 2, 2, 0]

なんとか AC。

解説の模範解答

M = gets.to_i  # => 100
ans = []
m = M
(0..10).each do |k|
  m, r = m.divmod(3)
  ans += [k] * r
end
ans            # => [0, 2, 2, 4]
puts ans.size
puts ans * " "

ところが模範解答は自分の考察とまったく違っていて、桁のインデックスを3進数化した分を並べていくだけだった。「大きい方から引いていく」とかぜんぜん関係なかった。

リファクタリング

122 ms

M = gets.to_i                                             # => 100
ans = M.digits(3).flat_map.with_index { |e, i| [i] * e }  # => [0, 2, 2, 4]
puts ans.size
puts ans * " "

N 進数は digits で求めることができる。分かりやすさで言えば、このようにしてN進数化と配列化を分けて考えるのもよいかもしれない。