🧮

[ABC051 B] Sum of Three Integers

2024/03/18に公開

Ruby

AtCoder

競プロ

tech

計算量を減らす工夫が必要な問題。

問題を要約する

x, y, z それぞれが 0..K
x, y, z の合計が S になる回数は？

計算量を一段階減らす考え方

たとえば 10 個のうち 4 個がわかっているなら残りは 6 だとすぐにわかる。4 個がわかっているのに残りを 1..10 まで順番に試す必要はないということ。

普通に実装 (TLE)

K, S = gets.split.collect(&:to_i)  # => [2, 2]
R = 0..K                           # => 0..2
count = R.sum do |x|
  R.sum do |y|
    R.count do |z|
      x + y + z == S
    end
  end
end
p count                            # => 6

三重ループしているので遅い。

最適化 (AC)

K, S = gets.split.collect(&:to_i)  # => [2, 2]
R = 0..K                           # => 0..2
count = R.sum do |x|
  R.count do |y|
    R.cover?(S - x - y)
  end
end
p count                            # => 6

応用問題 ABC085 - C Otoshidama の方を先にやってしまったせいで、多重ループの最後のループは外せるというネタを知っていたのだけど、なぜか 0..K でよかったものを 0..S に変えてしまいめちゃくちゃはまった。