G - Chicks and Cages

https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_g

解法

それぞれの籠に大きさを決める

aiをいれた際、全体の合計はai*籠の大きさ となるためaiが大きいものほど小さい籠に入れたいと分かる

よって籠の大きさを昇順であるとすると、aiを降順にソートしたものを並び替えず籠へ入れていっていいと分かる

籠iの後ろはi以上の大きさとなることから枝狩りできてlognになる

類題

https://atcoder.jp/contests/arc067/tasks/arc067_c

https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f

https://atcoder.jp/contests/code-festival-2018-final-open/submissions/4808565

void solve() {
    int M;
    cin >> n >> M;
    na(a, n);
    rsort(a);
    auto rui = ruic(a);
    vvi(dp, 2020, 2020, linf);
    dp[0][M] = 0;
    rep(i, n) {
        rer(m, M, 1) {
            rep(h, 1, n + 1) {
                if (i + m * h > n)break;
                chmi(dp[i + h][m - 1], dp[i][m] + rui(i, i + h) * h);
            }
        }
    }
    cout << dp[n][0] << endl;
}

初期解法

メモ化再帰で書いたため長くなった

dp[i][m] :=  これからi以降をm分割する状況　に持っていくまでの最小コスト

rec(i,m,s) //s := 前回の幅であり、今後使えるのはこれ以上の幅とする

lb[i][m] := 今までによばれたrec(i,m,s)におけるsの最小値

とし、rec(i,m,s)が呼ばれたら sからlb[i][m]までの幅を試すという風に遷移している

https://atcoder.jp/contests/code-festival-2018-final-open/submissions/4808004　

//渡された幅の値を覚えておく
//もしそれ以下の値が渡されたら必要な分だけ見る
void solve() {
    int M;
    cin >> n >> M;
    na(a, n);
    rsort(a);
    auto rui = ruic(a);
    vvi(rq, 2020, 2020);
    rep(i, n + 1) {
        rep(j, i + 1, n + 1) {
            rq[i][j] = rui(i, j) * (j - i);
        }
    }


    vvi(mem, 2020, 2020, linf);
    vvi(lb, 2020, 2020, M + 1);//lb以上の幅は求めてある
    //i番目以降をm組に分ける
    function<int(int, int, int)> rec = [&](int i, int m, int s) {
        if (i == n && m == 0)return 0ll;
        if (m == 0 || i == n) {
            return linf;
        }
        int lim = n + 1;
        if (mem[i][m] != linf) {
            //l以上は知ってるので 幅sからlまで
            if (lb[i][m] > s)chmi(lim, i + lb[i][m]);
            else return mem[i][m];
        }
        chmi(lb[i][m], s);
        //だめな幅
        //i + h * m > n  bad
        //
        int badh = ceil(n - i, m);
        if ((n - i) % m == 0)badh++;
        chmi(lim, i + badh);
        rep(j, i + s, lim) {
            chmi(mem[i][m], rq[i][j] + rec(j, m - 1, j - i));
        }
        return mem[i][m];
    };
    cout << rec(0, M, 1) << endl;
}