はまやんはまやんはまやん

hamayanhamayan's blog

Unpacking [SRM726 Div1 Easy]

N個の箱がある。
i番目の箱には赤飴a[i]個、青飴b[i]個入っており、値段はcost[i]である。
箱に入っている飴の量は増減する可能性があり、

  • 赤a[i]個、青b[i]個
  • 赤a[i] + 1個、青b[i] - 1個
  • 赤a[i] - 1個、青b[i] + 1個

の3状態ありえる。
N個の箱のうち、いくつかを適切に選んで、どんな状態で飴が入っていても、「K≦赤飴の総数またはK≦青飴の総数」となるようにしたい。
かかる値段の最小値は?

解法

scidylanpnoさんの解法とkoyumeishi‏さんのツイートを参考にした。
「solve(v,cost,K) := コストcost[i]でv[i]が得られるときに、合計がK以上となるための最小コスト」
これを使って、3種類の問題を解く。
1. solve(a[i]-1, cost, K)
2. solve(b[i]-1, cost, K)
3. solve(a[i]+b[i], cost, K*2-1)
これの最小値が答えになる。
 
どうやってこれを導くかであるが、「マンハッタン距離」の考え方が役に立つ。
(赤飴の個数,青飴の個数)として2次元座標で考えてみよう。
例えば、箱を3つ選んで赤の総和が6,青の総和が7だったとする。
すると、箱の増減によって、(6,7)以外にも(3,10),(4,9),(5,8),(7,6),(8,5),(9,4)の可能性もある。
この全ての点に関して原点からのマンハッタン距離を見ると、全て13になっている。
つまり、n個の箱を選んで赤の総和がr,青の総和がbであれば、(r-n,b+n)~(r+n,b-n)の間のマンハッタン距離がa+bである点が取りうる座標ということになる。
この取りうる座標の全てで、K≦max(x,y)を満たせば大丈夫となる。
これを元に3種類の問題を解くことで元の問題が解けることを示そう。
 
問題1はa[i]-1を足して行くので、取りうる座標のうち最も左の座標のx座標だけを考えていく感じになる。
K≦smを満たせば、全ての取りうる座標のx座標はK以上ということになるので条件を満たす。
 
問題2はb[i]-1を足していくので、取りうる座標のうち最も右の座標のy座標だけを考えていく感じになる。
K≦smを満たせば、全ての取りうる座標のy座標はK以上ということになるので条件を満たす。
 
問題3はa[i]+b[i]を足していくので、取りうる座標のマンハッタン距離だけを考えていく感じになる。
取りうる座標のマンハッタン距離がsmである時、max(x,y)の最小値は(floor(sm/2),ceil(sm/2))であることは明らかだろう。
K≦max(x,y)である必要があるため、K≦ceil(sm/2)となる必要がある。
これは言い換えるとK*2-1≦smである必要があると言える。
よって、K*2-1≦smを満たせば、全ての取りうる座標のmin(x,y)はK以上ということになるので条件を満たす。

#define INF INT_MAX/2
int dp[51][40101];
struct Unpacking {
    int n;
    int solve(vector<int> &v, vector<int> &cost, int K) {
        rep(i, 0, n + 1) rep(j, 0, 40101) dp[i][j] = INF;
        dp[0][0] = 0;

        int res = INF;
        rep(i, 0, n) rep(k, 0, K) if(dp[i][k] < INF) {
            dp[i + 1][k] = min(dp[i + 1][k], dp[i][k]);
            dp[i + 1][k + v[i]] = min(dp[i + 1][k + v[i]], dp[i][k] + cost[i]);
            if (K <= k + v[i]) res = min(res, dp[i + 1][k + v[i]]);
        }
        return res;
    }

    int getcost(vector <int> a, vector <int> b, vector <int> cost, int K) {
        n = a.size();
        vector<int> v(n);

        int ans = INF;
        rep(i, 0, n) v[i] = a[i] - 1;
        ans = min(ans, solve(v, cost, K));

        rep(i, 0, n) v[i] = b[i] - 1;
        ans = min(ans, solve(v, cost, K));

        rep(i, 0, n) v[i] = a[i] + b[i];
        ans = min(ans, solve(v, cost, K * 2 - 1));

        if (ans == INF) ans = -1;
        return ans;
    }
};