会津合宿 2017 2 日目 G : Picnic

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=G

解法

ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。

さらに、町の集合を の 2 つに分け、各集合のうちの部分集合を回った時に得られる幸福度を、個数制約付きナップサック問題をといて求める。

すると、 の部分集合と の部分集合を組み合わせることで、ある部分集合の最大値を求めることができる。

コード

import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val in = new Scanner(System.in)
    val N = in.nextInt()
    val X = in.nextInt()
    val Y = in.nextInt()
    val foods = (for (_ <- 0 until N) yield {
      val K = in.nextInt()
      (for (_ <- 0 until K) yield {
        val a = in.nextInt()
        val b = in.nextInt()
        val c = in.nextInt()
        (a, b, c)
      }).toArray
    }).toArray

    val dist = (for (_ <- 0 until N) yield (for (_ <- 0 until N) yield in.nextInt()).toArray).toArray
    for {
      k <- 0 until N
      i <- 0 until N
      j <- 0 until N
    } dist(i)(j) = math.min(dist(i)(j), dist(i)(k) + dist(k)(j))

    val cost = Array.fill(1 << (N + 1), N + 1)(Int.MaxValue / 2)
    cost(1)(0) = 0
    for {
      mask <- 0 until (1 << N)
      current <- 0 until N
      next <- 1 until (N + 1)
      if (mask & (1 << current)) != 0
      if (mask & (1 << next)) == 0
    } {
      val nextMask = mask | (1 << next)
      cost(nextMask)(next) = math.min(cost(nextMask)(next), cost(mask)(current) + dist(current)(next % N))
    }

    val bottom = N / 2
    val top = N - bottom

    val deq = new Array[Int](1000000)
    val deqv = new Array[Int](1000000)

    def knapsack(mask: Int, dp: Array[Int]): Unit = {
      dp(0) = 0
      for {
        i <- 0 until N
        if (mask & (1 << i)) != 0
        (price, value, remain) <- foods(i)
        a <- 0 until price
      } {
        var s = 0
        var t = 0

        var num = 0
        while (num * price <= (Y - a)) {
          val v = dp(num * price + a) - num * value
          while (s < t && deqv(t - 1) <= v) {
            t -= 1
          }
          deq(t) = num
          deqv(t) = v
          t += 1

          dp(num * price + a) = deqv(s) + num * value
          if (deq(s) == num - remain) {
            s += 1
          }

          num += 1
        }
      }

      for {
        i <- 1 to Y
      } {
        dp(i) = math.max(dp(i), dp(i - 1))
      }
    }

    val bottomDp = Array.fill[Int](1 << bottom, Y + 1)(-1)
    val topDp = Array.fill[Int](1 << top, Y + 1)(-1)
    for (mask <- 0 until (1 << bottom)) {
      knapsack(mask, bottomDp(mask))
    }
    for (mask <- 0 until (1 << top)) {
      knapsack(mask << bottom, topDp(mask))
    }

    var max = 0
    for {
      mask <- 0 until (1 << N)
    } {
      val moveCost = cost(mask | (1 << N))(N)
      val budget = math.min(Y, X - moveCost)
      val bottomMask = mask & ((1 << bottom) - 1)
      val topMask = mask >> bottom

      if (budget > 0) {
        for {
          bottomBudget <- 0 to budget
        } {
          max = math.max(max, bottomDp(bottomMask)(bottomBudget) + topDp(topMask)(budget - bottomBudget))
        }
      }
    }
    println(max)
  }
}