🧮

[ABC085 C] Otoshidama

2024/03/16に公開

Ruby

簡単そうに見えるが時間内で解くには工夫が必要な問題。

問題を理解する

合計 N 枚のお札で Y 円になるときの各枚数は？

なので

N = 3
Y = 12000

なら 1 0 2 が答えになる。

自力解答 (TLE)

2208 ms

N, Y = gets.split.collect(&:to_i)            # => [9, 45000]
ans = [-1, -1, -1]
catch :break do
  0.upto(Y / 10000) do |x|
    0.upto(Y / 5000) do |y|
      0.upto(Y / 1000) do |z|
        n = x + y + z                        # => 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2, 3, 4, 5, 6, 7, 8, 9, 10, 3, 4, 5, 6, 7, 8, 9, 10, 4, 5, 6, 7, 8, 9, 10, 5, 6, 7, 8, 9, 10, 6, 7, 8, 9, 10, 7, 8, 9, 10, 8, 9, 10, 9
        s = 10000 * x + 5000 * y + 1000 * z  # => 0, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000, 18000, 15000, 16000, 17000, 18000, 19000, 20000, 21000, 22000, 20000, 21000, 22000, 23000, 24000, 25000, 26000, 25000, 26000, 27000, 28000, 29000, 30000, 30000, 31000, 32000, 33000, 34000, 35000, 36000, 37000, 38000, 40000, 41000, 42000, 45000
        if n == N && s == Y
          ans = [x, y, z]
          throw :break
        end
        if n > N || s > Y
          break
        end
      end
    end
  end
end
ans                                          # => [0, 9, 0]
puts ans * " "

C 問題ぐらいは自力で解きたかったが無理だった。

[最適化1] 3つめのループは不要 (AC)

311 ms

N, Y = gets.split.collect(&:to_i)            # => [9, 45000]
ans = [-1, -1, -1]
catch :break do
  0.upto(Y / 10000) do |x|
    0.upto(Y / 5000) do |y|
      z = N - (x + y)                        # => 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
      if z >= 0
        n = x + y + z                        # => 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
        s = 10000 * x + 5000 * y + 1000 * z  # => 9000, 13000, 17000, 21000, 25000, 29000, 33000, 37000, 41000, 45000
        if n == N && s == Y
          ans = [x, y, z]
          throw :break
        end
        if n > N || s > Y
          break
        end
      end
    end
  end
end
ans                                          # => [0, 9, 0]
puts ans * " "

x と y がわかれば z は自明なのだった。そこに気づけたら通る。ついでに書くと z >= 0 のあとの x y z の合計は N と決まっているのだから合計が N と一致するかの判定には意味がない。

[最適化2] y のループ数を減らすことができる (AC)

132 ms

N, Y = gets.split.collect(&:to_i)            # => [9, 45000]
ans = [-1, -1, -1]
catch :break do
  (0..N).each do |x|
    (0..(N - x)).each do |y|
      z = N - (x + y)                        # => 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
      if z >= 0
        s = 10000 * x + 5000 * y + 1000 * z  # => 9000, 13000, 17000, 21000, 25000, 29000, 33000, 37000, 41000, 45000
        if s == Y
          ans = [x, y, z]                    # => [0, 9, 0]
          throw :break
        end
      end
    end
  end
end
ans                                          # => [0, 9, 0]
puts ans * " "

x + y は N を超えないので、y のループ回数は N - x + 1 回でよい。これで 179 ms 速くなる。

[番外] repeated_permutation を使う (AC)

319 ms

N, Y = gets.split.collect(&:to_i)        # => [9, 45000]
ans = [-1, -1, -1]
[*0..N].repeated_permutation(2) do |x, y|
  z = N - (x + y)                        # => 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
  if z >= 0
    s = 10000 * x + 5000 * y + 1000 * z  # => 9000, 13000, 17000, 21000, 25000, 29000, 33000, 37000, 41000, 45000
    if s == Y
      ans = [x, y, z]
      break
    end
  end
end
ans                                      # => [0, 9, 0]
puts ans * " "

二重ループは九九のような組み合わせとも言えるので repeated_permutation(2) で代用できる。ただし無駄な組み合わせが多いので最適とは言えない。