🐸

[鉄則A23] All Free (ビットDP)

2024/04/11に公開

Ruby

ビットDP問題。

問題を要約する

すべての敵を倒すのに必要なエナジーは？

地味な問題は身近な問題に置き換える。元の問題は「すべての品物を貰うのに必要な無料クーポンの数は？」だったため興味をそそられなかった。しかし、この見方を少し変えてみると、RPGの戦闘などで無意識に考えている身近な問題だと気づいた。

例1のシミュレーション

	火属性の敵	水属性の敵	木属性の敵
火攻撃			○
木攻撃		○
水攻撃	○
範囲攻撃	○	○

三体の敵を全滅させるには、

行動	エナジー消費
火・木・水攻撃	3
火攻撃・範囲攻撃	2

の二通りがあり、最小の 2 が答えになる。

全探索 (TLE)

N, H = gets.split.collect(&:to_i)                   # => [3, 4]
A = H.times.collect { gets.split.collect(&:to_i) }  # => [[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0]]
A.collect! { |e| e.collect.with_index { |e, i| e.nonzero? ? i : nil }.compact }
A                                                   # => [[2], [1], [0], [0, 1]]
ALL = N.times.to_a                                  # => [0, 1, 2]
counts = []
(1..H).each do |max|
  A.combination(max) do |actions|
    if actions.inject(:union).sort == ALL
      counts << actions.count
    end
  end
end
p counts.min || -1                                  # => 2

0 と 1 のテーブルを扱いやすいように敵番号に変換する。たとえば「火と水の敵を倒せる」という情報 [1, 1, 0] は [0, 1] (1がある桁のインデックスの配列) に変換する。あとはすべての行動パターンでエナジー消費量の最小値を求める。

解説の模範解答 (AC)

172 ms

N, H = gets.split.collect(&:to_i)                   # => [3, 4]
A = H.times.collect { gets.split.collect(&:to_i) }  # => [[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0]]
W = 1 << N                                          # => 8
dp = Array.new(H.next) { Array.new(W, Float::INFINITY) }
dp[0][0] = 0
(1..H).each do |y|              # y: それぞれの攻撃
  W.times do |x|                # x: 倒した敵のビットパターン
    # x (整数) から 0 1 の並びに変換する
    already = []
    N.times do |i|
      already[i] = x.anybits?(1 << i)
    end
    # y 番目の攻撃によって倒せる敵を、この時点の倒せる敵たちのビットパターンに追加する
    v = 0
    N.times do |i|
      if already[i] || A[y - 1][i] == 1
        v |= 1 << i
      end
    end
    v                                               # => 4, 5, 6, 7, 4, 5, 6, 7, 2, 3, 2, 3, 6, 7, 6, 7, 1, 1, 3, 3, 5, 5, 7, 7, 3, 3, 3, 3, 7, 7, 7, 7
    dp[y][x] = [dp[y][x], dp[y - 1][x]].min     # 今と上の小さい方を取る
    dp[y][v] = [dp[y][v], dp[y - 1][x] + 1].min # y 番目の攻撃で倒した場合のセルのエナジー消費数を +1 する
  end
end
p dp[H][W.pred].then { |e| e.infinite? ? -1 : e }   # => 2

出来上がった dp は次のようになっているが、

	1	2	3	4	5	6	7
0	INF	INF	INF	INF	INF	INF	INF
1	INF	INF	INF	1	INF	INF	INF
2	INF	1	INF	1	INF	2	INF
3	1	1	2	1	2	2	3
4	1	1	1	1	2	2	2

横軸 → 倒した敵のビットパターン
縦軸 → 使用した攻撃

なので、わかりやすくすると、

	○××	×○×	○○×	××○	○×○	×○○	○○○
攻撃なし
火攻撃				1
木攻撃		1		1		2
水攻撃	1	1	2	1	2	2	3
範囲攻撃	1	1	1	1	2	2	2

になる。

dp[水攻撃][○○×] ではそれまでにエナジー 2 を消費しているのに、その下の dp[範囲攻撃][○○×] で 1 に下がっているのは、同じ効果でも範囲攻撃の方がエナジー消費量が少なかったことを表す。

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

64 ms

N, H = gets.split.collect(&:to_i)                   # => [3, 4]
A = H.times.collect { gets.split.collect(&:to_i) }  # => [[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0]]
A.collect! { |e| e.reverse.join.to_i(2) }           # => [4, 2, 1, 3]
W = 1 << N                                          # => 8
dp = Array.new(H.next) { Array.new(W, Float::INFINITY) }
dp[0][0] = 0
(1..H).each do |y|              # y: それぞれの攻撃
  W.times do |x|                # x: 倒した敵のビットパターン
    v = x | A[y - 1]                                # => 4, 5, 6, 7, 4, 5, 6, 7, 2, 3, 2, 3, 6, 7, 6, 7, 1, 1, 3, 3, 5, 5, 7, 7, 3, 3, 3, 3, 7, 7, 7, 7
    dp[y][x] = [dp[y][x], dp[y - 1][x]].min     # 今と上の小さい方を取る
    dp[y][v] = [dp[y][v], dp[y - 1][x] + 1].min # y 番目の攻撃で倒した場合のセルのエナジー消費数を +1 する
  end
end
p dp[H][W.pred].then { |e| e.infinite? ? -1 : e }   # => 2

ループ内で毎回 already を作り、その already を参照しつつ v を作る部分は、最初に A の要素を整数化しておくと x と A[y - 1] の論理和で済む。