POJ 3260 The Fewest Coins

蟻本のスライド最小値のところの練習問題。簡単そうに見えますが意外とクセのある問題です。
3260 -- The Fewest Coins

問題概要

ある通貨体系で使われているコインの種類（金額）と、ジョンが持っているコインの枚数が与えられる。
ジョンがT円のものを買うとき、ジョンが払うコインの枚数＋お釣りの枚数　の最小値を求めろ。
構成できないなら-1を出力しろ。

解法

まず、
dp[i][j] := i枚目までのコインで、合計j円になるように構成するときの最小値
としましょう。こうすると個数制限つきナップサック問題とほぼ同じなので、蟻本と同様スライド最小値か、コインの枚数をコイン1, 1 << 1, 1 << 2, ..., 1 << k, a 枚分の金額・枚数を持つコインに分割すると考えて01ナップサック、で解けます。

お釣りの方は個数制限なしナップサックですね。

ところがこの問題N <= 100, vi <= 120, ci<= 10000ですから価値の合計は最大120000000とかになってこんな配列取れないし時間内に終わらん、となります。

ですがT <= 1000だし、途中で打ち切って良さそう？

と考えると 共通の硬貨を一枚ずつ引ける場合があれば当然無駄です。

1100円払ったら100円お釣りで帰ってきた、みたいな場合ですね。

というわけで適当にループの上界を決めてみましょう。

ためしにaがmaxVの倍数になるように構成してみます。このとき、お釣りの枚数の最小はa / maxV　枚です。
てきとーにT + hogeくらいからはじめて、なにか足すと%maxVが最低でも1ずれて、%maxVを最大(maxV - 1)個ずらせばいいので……と考えると、%maxVをいくつかずらすような構成を最大maxV個足すあいだに一致しなかったらもうその先では一致しない、ということになりT + maxV * maxV個くらいが最大かなあ、という感じがします。

なんか書いたのはいいんだけど証明がガバガバすぎて泣けてきた。中国語のサイトのはことごとく「鳩ノ巣原理」と書いてあったからなんか違う気もします（しかし内容は解読できていない）。んーmod120(maxV)とかを鳩ノ巣の部屋にしてダブってる！っていえばいいのかな？

あと、これはとても重要なことですが、適当にT * 2とかを上界にしても通ります。

スライド最小値解法　上界はガバガバ
600msくらいかかった。
dequeのメモリ確保が原因か？

typedef pair<int, int> pint;
const int INF = 1e9;
int v[100], c[100];
const int MAX_V = 12000;
int dp[MAX_V + 1];
int dp2[MAX_V + 1];
int main() {
    int N, T;
    scanf("%d%d", &N, &T);
    rep(i, N) scanf("%d", v + i);
    rep(i, N) scanf("%d", c + i);
    
    fill_n(dp, MAX_V + 1, INF);
    dp[0] = 0;
    rep(i, N) rep(a, v[i]) {
        deque<pint> deq;
        for(int j = 0; j * v[i] + a <= MAX_V; ++j) {
            int val = dp[j * v[i] + a] - j;
            while(!deq.empty() && deq.back().second >= val) deq.pop_back();
            deq.push_back(pint(j, val));
            dp[j * v[i] + a] = deq.front().second + j;
            if(deq.front().first == j - c[i]) deq.pop_front();
        }
    }
    
    fill_n(dp2, MAX_V + 1, INF);
    dp2[0] = 0;
    rep(i, N) for(int j = v[i]; j <= MAX_V; ++j)
      dp2[j] = min(dp2[j], dp2[j - v[i]] + 1);

    int ans = INF;
    REP(i, T, MAX_V + 1) if(dp[i] < INF)
      ans = min(ans, dp[i] + dp2[i - T]);
    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}

1 + 2^1 + 2^2 + ... に構成し直す解法
上界は一応大丈夫っぽい？
120msくらいで通る。

onst int INF = 1e9;
int v[100], c[100];
const int MAX_V = 24500;
int dp[MAX_V + 1];
int dp2[MAX_V + 1];
int main() {
    int N, T;
    scanf("%d%d", &N, &T);
    rep(i, N) scanf("%d", v + i);
    rep(i, N) scanf("%d", c + i);

    int maxLoop = T + 120 * 120;
    
    fill_n(dp, MAX_V + 1, INF);
    dp[0] = 0;
    rep(i, N) {
        int num = c[i];
        for(int k = 1; num > 0; k <<= 1) {
            int mul = min(k, num);
            for(int j = maxLoop; j >= mul * v[i]; --j)
              dp[j] = min(dp[j], dp[j - mul * v[i]] + mul);
            num -= mul;
        }
    }
    
    fill_n(dp2, MAX_V + 1, INF);
    dp2[0] = 0;
    rep(i, N) for(int j = v[i]; j <= maxLoop; ++j)
      dp2[j] = min(dp2[j], dp2[j - v[i]] + 1);

    int ans = INF;
    REP(i, T, maxLoop + 1) if(dp[i] < INF)
      ans = min(ans, dp[i] + dp2[i - T]);
    printf("%d\n", ans == INF ? -1 : ans);
    return 0;
}