SRM276 - お買い物は楽しく DP で

Hayato Ito

SRM276 に挑戦．かなーり，眠かったので，スルーしようかと思ったのですが，挑戦しました．

VolumeDiscount (code)

250 点問題． お買い物です．たとえば，

だったとします．50 個，買いたいとします．最低何$ですむか？という問題です. この例だと

20 個 x 2 + 3 個 x 3 + 1 個 x 1= 50 個 (48$ x 2 + 10$ x 3 + 4$ x 1 = 130$)

がベストな買い方で，答えは 130 です．しかし，50 個ではなく，55 個買いたいとすると，ベストな買い方は

20 個 x 2 + 3 個 x 5 = 55 個 (48$ x 2 + 10$ x 5 = 146$)

ではなく

20 個 x 3 = 60 個 ( 48$ x 3 = 144$)

です．答えは，144 になります． SRM 中は，入力条件が緩いので Brute-Force で十分いけると思って Submit しました．チャレンジタイムでは，Memoization なしの Brute-Force ではタイムアウトすると思われたのか, 2 回チャレンジをうけました．チャレンジで使用された入力は

SRM276 Challenge

と明らかに 2 秒タイムオーバー狙いです．チャレンジタイム後に，チャレンジしてきた人に質問されました． 2 秒以内に終わったのが，信じられなかったようです.

SRM276 Chat

その後, HiltonLange さんには，さらに

{"51 1","1 99"}, 99 だと，失敗するんじゃない？

と指摘されました．そのとおりです．この入力だと 51 個 x2=101 個，2 ドルが正解ですが，Submit した Code では

for (int i = 0; q + i * unit[n] < 100; i++) {

このように上限を 100 にしていたため，51 x 1 + 99 * 48 = 4803 ドルを出力していまいます． 上限は，最低 200 じゃないと．System Test に落ちますね．．．

for (int i = 0; q + i * unit[n] < 200; i++) {

このように上限 200 にしておくと，2 秒近くかかりますが，なんとか System Test に通っていました．それでも無駄だらけなので，無駄をなくすと共に，Memoization を併用すれば，劇的に早くなります．以下のようになります．

int go(int q, int n) {
   if (n == N) {
       if (q < quantity) return 1000000;
       return 0;
   }
   if (cache[q][n] != 0) return cache[q][n];
   int min = Integer.MAX_VALUE;
   for (int i = 0;; i++) {
       min = Math.min(min, cost[n] * i + go(q + unit[n] * i, n+1));
       if (q + i * unit[n] >= quantity) break;
   }
   return cache[q][n] = min;
}

この手の問題は，やはり DP(Dynamic Programming)を使うのが常套手段でしたね． SRM 後に書いてみました.

public int bestDeal(String[] priceList, int quantity) {
    int N = priceList.length;
    int[] unit = new int[N];
    int[] cost = new int[N];
    for (int i = 0; i < N; i++) {
        unit[i] = Integer.parseInt(priceList[i].split(" ")[0]);
        cost[i] = Integer.parseInt(priceList[i].split(" ")[1]);
    }

    int[] best = new int[300];
    Arrays.fill(best, Integer.MAX_VALUE);
    best[0] = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < quantity; j++) {
            if (best[j] != Integer.MAX_VALUE) {
                if (best[j] + cost[i] < best[j + unit[i]]) {
                    best[j+unit[i]] = best[j] + cost[i];
                }
            }
        }
    }

    int min = Integer.MAX_VALUE;
    for (int i = quantity; i < quantity + 100; i++) {
        min = Math.min(min, best[i]);
    }
    return min;
}

ほとんどの人は，さくっと躊躇することなく DP を使用していました．さすが，Division1．

TestingCar

500 点問題． レーシングカーの試験走行をします．ただし，時間帯により制限速度の条件がいくつか与えられます.

というふうにです． 入力として

この条件のもとで，レーシングカーが出せる最高速度はいくつになるかという問題です. SRM 中は，途中で方針が間違っていたことことにきずき，お手上げでした．（つぎのつぎの制限速度の変更を考慮していなかったため減速が間に合わない．）

ForceTest

1000 点問題． Open しませんでした．

結果

System Test の結果です． ( Room Statistics )

Room Statistics

レーティングは低下．今日は，敗北感が強いな．．

今日の教訓