この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 12 日目の記事です。
問題リンク
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2337 (1000 点)
問題概要
$N_a$ 匹のオスのネコ、 $N_b$ 匹のメスのネコがいて、各猫には固有の重さとかわいさが定まっている。
重さの和が $W$ を超えないようにオスのネコを $1$ 匹以上選ぶ。メスのネコについても同様に選ぶ。 このとき、$\mathrm{max}( |$選んだオスのネコの重さの和 - 選んだメスのネコの重さの和$|,$ 選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値$)$ を最小化せよ。
制約
- $1 \leq N_A,N_B \leq 500$
- $1 \leq W \leq 10^ 4 $
- $1 \leq$ 各ネコの重さ $ \leq 10^ 4 $
- $1 \leq$ 各ネコのかわいさ $ \leq 10^ 9 $
解法
まず、重さが $W$ より大きいネコが入力に含まれうる（非本質。。）のでそのようなネコを捨てます。
次に、目的関数の第二項、すなわち (選んだネコの可愛さの最大値 - 選んだネコの可愛さの最小値) の取り得る最小値を求めます。これは適当に全探索しても十分間に合いますし、ソートすればより高速です。
第二項の最小値が $W-1$ 以上のとき、第一項は $W-1$ 以下であることからそれを答えとして出力すればよいです。
以下そうでない場合を解きます。最大値の最小化なので二分探索をします。答えを $x$ 以下に出来るかという判定問題について考えます。
愚直な解法として、ネコの可愛さの最小値を決め打つと、使えるネコの集合が決まるので、部分和問題を解くことで判定問題に答えられます。しかしこの解法は $\mathrm{O}(N ^ 2 W) $ かかります。(昔の問題なので bitset 高速化でこの解法も通ってしまうようです)
ここではより計算量のよい解法で解きます。ネコをかわいさでソートしておき、尺取り法のように部分和 DP を更新することを考えます。この際、使えなくなったネコによる遷移を打ち消す（戻す DP)必要性が生じます。
「部分集合であって重さ w を達成できるか？」という bool を管理する DP は戻すことが難しいですが、 boolを持つのでなく、かわりに「部分集合であって重さ w を達成できるものは何通りか $\text{mod}$ 適当な数」という個数を管理する DP にすることで、戻す DP が可能となり尺取り法のような DP 更新が可能となります。
以上でこの問題を $\mathrm{O}(NW \log W) $ で解くことが出来ました。
実装例 (c++)
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define rep(i, x) for(int i = 0; i < (x); i++) #define rng(i, l, r) for(int i = (l); i < (r); i++) #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() constexpr int mod = 1000000007; struct mint { ll v; mint(ll x = 0) { v = x % mod; if(v < 0) v += mod; } mint operator+(mint a) { return v + a.v; } mint operator-(mint a) { return v - a.v; } mint operator*(mint a) { return v * a.v; } }; using fps = vector<mint>; // f *= (1 + x^d) void multiply(fps &f, int d) { for(int i = sz(f) - 1 - d; i >= 0; i--) f[i + d] = f[i + d] + f[i]; } // f /= (1 + x^d) void divide(fps &f, int d) { rep(i, sz(f) - d) f[i + d] = f[i + d] - f[i]; } int main() { int na, nb, w; cin >> na >> nb >> w; using T = tuple<int, int, int>; vector<T> ctm; rep(i, na) { int m, c; cin >> m >> c; if(m > w) continue; ctm.push_back({c, 0, m}); } rep(i, nb) { int m, c; cin >> m >> c; if(m > w) continue; ctm.push_back({c, 1, m}); } sort(all(ctm)); int term2_min = 1 << 30; rep(i, sz(ctm) - 1) { if(get<1>(ctm[i]) != get<1>(ctm[i + 1])) { term2_min = min(term2_min, get<0>(ctm[i + 1]) - get<0>(ctm[i])); } } if(term2_min >= w - 1) { cout << term2_min << endl; return 0; } auto f = [&](int x) -> bool { vector<fps> fs(2, fps(w + 1)); fs[0][0] = fs[1][0] = 1; queue<T> que; for(auto [c, t, m] : ctm) { while(!que.empty() and c - get<0>(que.front()) > x) { auto [oc, ot, om] = que.front(); que.pop(); divide(fs[ot], om); } que.push(T{c, t, m}); multiply(fs[t], m); pii bef = {-(1 << 30), 0}; rng(i, 1, w + 1) { rep(j, 2) { if(fs[j][i].v != 0) { if(i - bef.first <= x and bef.second != j) return true; bef = {i, j}; } } } } return false; }; int ok = w, ng = -1, mid; while(mid = (ok + ng) >> 1, ok - ng > 1) (f(mid) ? ok : ng) = mid; cout << ok << endl; }
感想
AOJ-ICPC では 1000 点が付いていますが、特に難しい考察もなく、実装も平易なので 1000 点初 AC を狙いたい人にはお勧めかもしれません。
