🧮
[ARC061 A] たくさんの数式
bit全探索で解く問題。
問題を理解する
- 数字の間に
+を挟んでもよい - その数式の計算結果の合計を表示する
なので 12 だと 12 と 1+2 なので 12 + 3 = 15 になる。
普通に実装 (AC)
S = gets.strip.chars # => ["1", "2", "5"]
total = ["+", ""].repeated_permutation(S.size.pred).sum do |e|
expr = S.zip(e).join # => "1+2+5", "1+25", "12+5", "125"
eval(expr) # => 8, 26, 17, 125
end
p total # => 176
特に難しいところはないが想定解とは違うようだ。
bit全探索な実装 (AC)
S = gets.strip.chars # => ["1", "2", "5"]
N = S.size.pred # => 2
total = (1 << N).times.sum do |i|
expr = [S.first]
N.times do |j|
expr << (i.anybits?(1 << j) ? "+" : "")
expr << S[j.next]
end
expr = expr.join # => "125", "1+25", "12+5", "1+2+5"
eval(expr) # => 125, 26, 17, 8
end
p total # => 176
二進数の模様を利用して多重ループを一次元のループに置き換える。こちらが想定解と思われる。
類題
Discussion