AOJ2502: B: VOCAL ANDROID - kira924age’s note

問題

https://onlinejudge.u-aizu.ac.jp/problems/2502

解答例

解説

重さが可変 ( $s_i \leq x_i \leq l_i$ ) の品物から重さがちょうど $w_i$ になるときの価値の総和の最大値を求めると考えれば, 個数制限なしナップザック問題とほとんど同じ問題とみなすことができる.

ここでナップザック問題とこの問題における変数を対応付けると以下のようになる.

AOJ-2502 VOCAL ANDROID	ナップザック問題
フレーズの個数 $n$	品物の種類 $n$
i番目のメロディの長さ ( $s_i \leq x_i \leq l_i$ )	i番目の品物の重さ $w_i$
i番目のフレーズの得点 $p_i$	i番目の品物の価値 $v_i$
メロディの長さ $w_i$	ナップザックの容量 $W$

個数制限なしナップザック問題と同様に以下のような配列を考える.

$\text{dp[i][j]} := i番目までのフレーズを使って, メロディの長さの総和が j のとき, 得点の総和の最大値$

遷移は以下のようになる.

- 0番目までのフレーズを使って(何も使わず) メロディの長さの総和が0のときの得点の総和の最大値は0
- ただし $s_i \leq k \leq l_i$

最も長いメロディの長さを持つ配列を用意すれば良い.

なお, 実装上は上の漸化式における i に関する次元を減らすことができて, 配列を1次元で持ちメモリ消費を抑えることができる. (蟻本 p59-p60 参照) このような手法は配列再利用, in-place DP などと呼ばれることもあるらしい.

計算量は愚直にやると $O(n (\max{w_{i}})^{2})$ 程度になり, 十分間に合う.

SegmentTree などを使って, 区間MAX を対数時間で計算するようにすると, $O(n \max{w_{i}} \log{\max{w}} )$ に落とすことができる. (この問題を解く上では不要な高速化である)

Segment Tree は AC Library のものとほとんど同じ実装を用いた.

https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp

実装例

愚直な実装

// submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/2502/judge/5874423/C++11
// Time:  00.04 s 
// Memory: 3420 KB

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> s(n + 1), l(n + 1), p(n + 1);
  // 1-index でデータを保持
  for (int i = 1; i <= n; i++) {
    cin >> s[i] >> l[i] >> p[i];
  }

  int m;
  cin >> m;

  vector<int> w(m);
  for (int i = 0; i < m; i++) {
    cin >> w[i];
  }

  int W = *max_element(w.begin(), w.end());

  // dp[i][j] := i番目までのフレーズを使って長さがちょうどjとなるときの得点のMAX
  vector<vector<int>> dp(n + 1, vector<int>(W + 1, -1));
  dp[0][0] = 0;

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
      dp[i][j] = max(dp[i][j], dp[i - 1][j]);

      for (int k = s[i]; k <= l[i]; k++) {
        if (j - k >= 0) {
          dp[i][j] = max(dp[i][j], dp[i][j - k] + p[i]);
        }
      }
    }
  }

  vector<int> ans;

  for (int i = 0; i < m; i++) {
    if (dp[n][w[i]] == -1) {
      cout << -1 << "\n";
      return 0;
    }
    ans.push_back(dp[n][w[i]]);
  }

  for (auto a : ans) {
    cout << a << "\n";
  }

  return 0;
}

Segment Tree で高速化 + in-place DP でメモリ節約

// submission: https://onlinejudge.u-aizu.ac.jp/status/users/kira924age/submissions/1/2502/judge/5875259/C++11
// Time:  00.00 s 
// Memory: 3256 KB

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

using namespace std;

template <class S, S (*op)(S, S), S (*e)()> struct Segtree {
public:
  Segtree() : Segtree(0) {}
  Segtree(int n) : Segtree(std::vector<S>(n, e())) {}
  Segtree(const std::vector<S> &v) : _n(int(v.size())) {
    log = 0;
    while ((1U << log) < (unsigned int)(_n)) {
      log++;
    }
    size = 1 << log;
    d = std::vector<S>(2 * size, e());
    for (int i = 0; i < _n; i++)
      d[size + i] = v[i];
    for (int i = size - 1; i >= 1; i--) {
      update(i);
    }
  }

  void set(int p, S x) {
    assert(0 <= p && p < _n);
    p += size;
    d[p] = x;
    for (int i = 1; i <= log; i++)
      update(p >> i);
  }

  S get(int p) {
    assert(0 <= p && p < _n);
    return d[p + size];
  }

  S prod(int l, int r) {
    assert(0 <= l && l <= r && r <= _n);
    S sml = e(), smr = e();
    l += size;
    r += size;

    while (l < r) {
      if (l & 1)
        sml = op(sml, d[l++]);
      if (r & 1)
        smr = op(d[--r], smr);
      l >>= 1;
      r >>= 1;
    }
    return op(sml, smr);
  }

  S all_prod() { return d[1]; }

  template <bool (*f)(S)> int max_right(int l) {
    return max_right(l, [](S x) { return f(x); });
  }
  template <class F> int max_right(int l, F f) {
    assert(0 <= l && l <= _n);
    assert(f(e()));
    if (l == _n)
      return _n;
    l += size;
    S sm = e();
    do {
      while (l % 2 == 0)
        l >>= 1;
      if (!f(op(sm, d[l]))) {
        while (l < size) {
          l = (2 * l);
          if (f(op(sm, d[l]))) {
            sm = op(sm, d[l]);
            l++;
          }
        }
        return l - size;
      }
      sm = op(sm, d[l]);
      l++;
    } while ((l & -l) != l);
    return _n;
  }

  template <bool (*f)(S)> int min_left(int r) {
    return min_left(r, [](S x) { return f(x); });
  }
  template <class F> int min_left(int r, F f) {
    assert(0 <= r && r <= _n);
    assert(f(e()));
    if (r == 0)
      return 0;
    r += size;
    S sm = e();
    do {
      r--;
      while (r > 1 && (r % 2))
        r >>= 1;
      if (!f(op(d[r], sm))) {
        while (r < size) {
          r = (2 * r + 1);
          if (f(op(d[r], sm))) {
            sm = op(d[r], sm);
            r--;
          }
        }
        return r + 1 - size;
      }
      sm = op(d[r], sm);
    } while ((r & -r) != r);
    return 0;
  }

private:
  int _n, size, log;
  std::vector<S> d;

  void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

int op(int a, int b) { return max(a, b); }
int e() { return 0; }

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(false);

  int n;
  cin >> n;

  vector<int> s(n + 1), l(n + 1), p(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> s[i] >> l[i] >> p[i];
  }

  int m;
  cin >> m;

  vector<int> w(m);
  for (int i = 0; i < m; i++) {
    cin >> w[i];
  }

  int W = *max_element(w.begin(), w.end());

  vector<int> dp(W + 1, -1);
  dp[0] = 0;

  for (int i = 1; i <= n; i++) {
    Segtree<int, op, e> segtree(W + 1);

    for (int j = 0; j <= W; j++) {
      int L = max(0, j - l[i]);
      int R = max(0, j - s[i] + 1);

      if (L != R) {
        int tmp = segtree.prod(L, R);
        dp[j] = max(dp[j], tmp + p[i]);
      }

      segtree.set(j, dp[j]);
    }
  }

  vector<int> ans;

  for (int i = 0; i < m; i++) {
    if (dp[w[i]] == -1) {
      cout << -1 << "\n";
      return 0;
    }
    ans.push_back(dp[w[i]]);
  }

  for (auto a : ans) {
    cout << a << "\n";
  }

  return 0;
}

参考文献

蟻本