🧮

[ABC079 C] Train Ticket

2024/03/19に公開

Ruby

bit全探索向けの問題。

問題を理解する

4つの数字の間に符号を入れて合計が 7 になるときの数式は？

なので 1 2 2 2 なら 1+2+2+2=7 が答えになる。

自力で実装 (AC)

112 ms

ABCD = gets.strip.chars.collect(&:to_i)         # => [1, 2, 2, 2]
a, b, c, d = ABCD                               # => [1, 2, 2, 2]
expr = catch :break do
  [:+, :-].each do |x|
    [:+, :-].each do |y|
      [:+, :-].each do |z|
        r = a.send(x, b).send(y, c).send(z, d)  # => 7
        if r == 7
          throw :break, ABCD.zip([x, y, z]).join
        end
      end
    end
  end
end
expr = "#{expr}=7"                              # => "1+2+2+2=7"
puts expr

bit全探索で解けるというのを知っていたがbit全探索が何のことかわからずこうなってしまった。

リファクタリング後 (AC)

123 ms

ABCD = gets.strip.chars.collect(&:to_i)  # => [1, 2, 2, 2]
expr = nil
[:+, :-].repeated_permutation(3) do |x, y, z|
  expr = ABCD.zip([x, y, z]).join
  if eval(expr) == 7
    break
  end
end
expr = "#{expr}=7"                       # => "1+2+2+2=7"
puts expr

repeated_permutation に変更すると約 50 ms 速くなるが毎回数式を作って eval することで約 50 ms 遅くなるのであまり速度は変わらない。

bit全探索とは？

二つの値による組み合わせは次のように、

[0, 1].repeated_permutation(3).to_a.collect(&:join)  # => ["000", "001", "010", "011", "100", "101", "110", "111"]
0b1000.times.collect { |e| "%03b" % e }              # => ["000", "001", "010", "011", "100", "101", "110", "111"]

どちらでも表現できるので二進数の模様の方を利用しようということらしい。

bit全探索な実装 (AC)

それを踏まえると、

132 ms

ABCD = gets.strip.chars.collect(&:to_i)  # => [1, 2, 2, 2]
expr = nil
0b1000.times do |e|
  x = e.anybits?(1 << 0) ? :+ : :-
  y = e.anybits?(1 << 1) ? :+ : :-
  z = e.anybits?(1 << 2) ? :+ : :-
  expr = ABCD.zip([x, y, z]).join
  if eval(expr) == 7
    break
  end
end
expr = "#{expr}=7"                       # => "1+2+2+2=7"
puts expr

と書ける。

これがメリットなのかはわからないが多重ループを一次元のループに置き換えることができる。

ハードコーディングを避ける (AC)

116 ms

ABCD = gets.strip.chars.collect(&:to_i)  # => [1, 2, 2, 2]
X = 7
N = ABCD.size.pred
expr = nil
(1 << N).times do |i|
  expr = [ABCD.first]
  N.times do |j|
    expr << (i.anybits?(1 << j) ? :+ : :-)
    expr << ABCD[j.next]
  end
  expr = expr.join
  if eval(expr) == X
    break
  end
end
expr = "#{expr}=#{X}"                    # => "1+2+2+2=7"
puts expr

4つの数字に依存しないようにしたもの。