🐛

[鉄則B13] Supermarket 2

2024/05/08に公開

Ruby

累積和＋しゃくとり法問題。

問題を要約する

品物が価格昇順で並んでいる
その順で連番がついている
品物を連番で選択して K 円以内で購入できるのは何通りか？

例1で問題を理解する

品物	0	1	2	3	4	5	6
価格	11	12	16	22	27	28	31

に対して最初は品物 0, 1, 2 が 50 円以下で購入できる。次にひとつずらして品物 1 からでは、品物 1 2 3 が 50 円以下で購入できる。これを繰り返すと、

	購入を試みる範囲	購入できた範囲	購入できた個数
0回目	0..6	0..2	3
1回目	1..6	1..3	3
2回目	2..6	2..3	2
3回目	3..6	3..4	2
4回目	4..6	4..4	1
5回目	5..6	5..5	1
6回目	6..6	6..6	1

となり、購入できた個数の合計 13 が答えになる。

全探索 (AC)

128 ms

N, K = gets.split.collect(&:to_i)  # => [7, 50]
A = gets.split.collect(&:to_i)     # => [11, 12, 16, 22, 27, 28, 31]
count = 0
N.times do |l|
  yen = 0
  # r が毎回 l から始まるので計算量が多くなる
  (l...N).each do |r|
    yen += A[r]                    # => 11, 23, 39, 61, 12, 28, 50, 77, 16, 38, 65, 22, 49, 77, 27, 55, 28, 59, 31
    if yen > K
      break
    end
    count += 1                     # => 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
  end
end
p count                            # => 13

テストケースがいまいちなのか普通に通った。

しゃくとり法 (AC)

129 ms

N, K = gets.split.collect(&:to_i)
A = gets.split.collect(&:to_i)

# 累積和
S = A.each_with_object([0]) { |e, m| m << m.last + e }  # => [0, 11, 23, 39, 61, 88, 116, 147]

# しゃくとり法
r = 0
count = (1..N).sum do |l|
  while r < N
    # l 番目から (r + 1) 番目まで購入する場合の金額
    yen = S[r + 1] - S[l - 1]                           # => 11, 23, 39, 61, 50, 77, 65, 49, 77, 55, 28, 59, 31
    if yen > K
      break
    end
    r += 1                                              # => 1, 2, 3, 4, 5, 6, 7
  end
  r - l + 1                                             # => 3, 3, 2, 2, 1, 1, 1
end
p count                                                 # => 13

累積和配列の添字が難しい。l からの場合、ひとつ前の位置からの差だから S[l - 1] となる。一方の S[r + 1] は、たんに次の品物を購入したときの金額も知りたい、という意味での + 1 になる。