🔍
[鉄則B14] Another Subset Sum
半分全列挙の応用問題。
問題を要約する
- N 枚から 0 枚以上を選んだとき合計が K になることはあるか？
例1で問題を理解する
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 5 | 1 | 18 | 7 | 2 | 9 |
5, 18, 7 を選んだとき K(30) になる。
解き方
- A を半分にする → X, Y
- X, Y 内で総当たり足し算を行う → P, Q
- P + Q = K になるか調べる
最後は Q = K - P と考えて Q の中に K - P があるかを探す。最初に半分に分けるのは適当でいい。X, Y のサイズは異なっていてもいい。
はまりポイント
0 枚以上のカードを選ぶ。つまり選ばないのときもある。
例1のシミュレーション
A の、
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| A | 5 | 1 | 18 | 7 | 2 | 9 |
を半分にして、
| 半分 | |
|---|---|
| X | 5 1 18 |
| Y | 7 2 9 |
総当たりで足し算し、
| 結果 | |
|---|---|
| P | 0 5 1 18 6 23 19 24 |
| Q | 0 2 7 9 9 11 16 18 |
30 - 0 の 30 が Q に含まれるか探す。線形探索だと遅いので二分探索を行う。しかし 30 はなかったので次に進む。これを繰り返すと 23 のときに 30 - 23 で 7 が Q に見つかる。
全探索 (TLE)
N, K = gets.split.collect(&:to_i) # => [6, 30]
A = gets.split.collect(&:to_i) # => [5, 1, 18, 7, 2, 9]
ans = (0..N).any? do |max|
A.combination(max).any? do |e|
e.sum == K
end
end
puts ans ? "Yes" : "No"
半分全列挙 (AC)
124 ms
N, K = gets.split.collect(&:to_i) # => [6, 30]
A = gets.split.collect(&:to_i) # => [5, 1, 18, 7, 2, 9]
X = A.take(N / 2) # => [5, 1, 18]
Y = A.drop(N / 2) # => [7, 2, 9]
P = (0..X.size).flat_map { |max| X.combination(max).collect(&:sum) }
Q = (0..Y.size).flat_map { |max| Y.combination(max).collect(&:sum) }.sort
P # => [0, 5, 1, 18, 6, 23, 19, 24]
Q # => [0, 2, 7, 9, 9, 11, 16, 18]
ans = P.any? { |e| Q.bsearch { |q| (K - e) - q } } # => true
puts ans ? "Yes" : "No"
bsearch は find の高速版としたいので find-any モードにする。
Discussion