ACM-ICPC国内予選に参加しました & D問題

ACM-ICPC国内予選にboTechというチームで参加しました。結果は5完で11位でした。東大は闇なのでアジア予選には進出できないと思いますが正直こんなに上位争いに食い込めるとは思ってなかったので素直にうれしいです。また来年も参加したいですね。

担当したのはA, B, D問題です(前の模擬国内予選で一問も解けなかったのでA問題はやらせてとねだった)。とりあえずD問題の解法を貼っておきたいと思います。前と同様に多分AOJではTLEします。Twitter見てTLEの取り除き方も分かった気がするのでそこまで紹介します。

問題

500円玉をなるべく集めたいおじさんがいて,このおじさんは1000円札は大量に持っている。
今,買うかもしれない商品が時系列順に与えられている。これらの商品は買っても買わなくてもよいが,とにかくおつりでもらう500円玉の枚数をできるだけ多くしたい。
500円玉をできるだけ多く得ることのできるような商品の買い方のなかで支払う料金の合計が最小になるようなものはいくらか。

解法

dpで解きます。本番は
dp[n][num][yen] = n番目の商品を買うか買わないか決めようとしている時点で500円玉をnum枚持っていておつりでもらったお金はyen円である時,支払う料金の最小値
として解きました。
状態数を考えると,商品の数は100, 1回の商品購入で得られる500円玉はたかだか1枚であり得られるお釣りはたかだか500円なのでnumは100, yenは500*100とすれば状態をすべて記述できます。

よって状態数は100*100*500*100です。…ちょっと多すぎですが実行時間は1つのケースにつき5秒もあれば間に合いそうなので国内予選のルールでは問題ありません。

dpの更新の仕方は以下のとおりです。
n番目の商品を買ったときに500円玉をもらうために最低限必要なお金は,n番目の商品の値段をp[n]として

need = (p[n]+500) % 1000

となります。例えば1800円の商品を買う時500円もらうためには300円あると嬉しいわけです(2000円は無尽蔵の1000円札から払える)。

他の場合はとりあえずお金を払って小銭を稼ぐか払わないで次の商品を見に行くかのどちらかです。
小銭を稼ぐ場合にはちょっと注意が必要で,例えば300円払うと700円もらえるわけですがこの時は200円だけ小銭を稼いで500円をゲットしています。

で,計算量を抑える方法ですがよく考えると上で定義したnumは必要ないです。

dp[n][yen] = n番目の商品を買うか買わないか決めようとしている時点でおつりでもらったお金はyen円である時,得られる500円玉の最大枚数および支払う料金の最小値のペア

と考えればほとんど同じ考え方でいける(はず)です。確かめてはないです。

const int INF = 1<<25;
int dp[2][110][50000];
int p[110];
int n;

void solve() {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 110; j++) {
            for (int k = 0; k < 50000; k++) {
                dp[i][j][k] = INF;
            }
        }
    }
    dp[0][0][0] = 0;
    for (int i = 0; i < n; i++) {
        int cur = i%2;
        int tar = 1-cur;
        for (int j = 0; j < 110; j++) for (int k = 0; k < 50000; k++) {
            dp[tar][j][k] = dp[cur][j][k];
        }
        int need = (p[i]+500) % 1000;
        for (int j = 0; j < 110; j++) {
            for (int k = 0; k < 50000; k++) {
                if (dp[cur][j][k] == INF) continue;
                if (k >= need) {
                    dp[tar][j+1][k-need] = min(dp[cur][j][k]+p[i], dp[tar][j+1][k-need]);
                }
                // そのまま
                dp[tar][j][k] = min(dp[tar][j][k], dp[cur][j][k]);
                // 買う
                int get = 1000-(p[i]%1000);
                if (get == 1000) get = 0;
                int next = j;
                if (get >= 500) {
                    next++;
                    get -= 500;
                }
                dp[tar][next][k+get] = min(dp[tar][next][k+get], dp[cur][j][k]+p[i]);
            }
        }
    }
    {
        int tmp = (n%2);
        int ans = INF;
        for (int i = 0; i < 110; i++) {
            int hai = INF;
            for (int j = 0; j < 50000; j++) {
                hai = min(hai, dp[tmp][i][j]);
            }
            if (hai == INF) {
                cout << i-1 << " " << ans << endl;
                return;
            } else {
                ans = hai;
            }
        }
    }
}

int main() {
    while (cin >> n) {
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }
        solve();
    }
}