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

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

• 1 個なら 4$
• 3 個まとめて買うと 10$
• 20 個まとめて買うと 48$

だったとします．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 回チャレンジをうけました．チャレンジで使用された入力は

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

その後, 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．

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

• [5 秒から 10 秒の間は，10 m/s 以上スピードを出してはいけない ]
• [15 秒から 20 秒の間は，15 m/s 以上スピードを出してはいけない ]
• [30 秒から 40 秒の間は，5 m/s 以上スピードを出してはいけない ]

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

• レーシングカーの加速度 a (m / s^2 ) (減速度(?) も兼ねています．）
• 試験走行の時間 (duratation) が与えられます.

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

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

結果

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

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

今日の教訓

• DP をちゃんとマスターしておく