AtCoder Beginner Contest 104

D(計算が合わなくて後回し)→C→B→A→D(再訪)、で4完
Dからやって計算合わないとめっちゃ焦る。

D - We Love ABC

DPでいいと思うんだけど
（Aまで来た数、ABまで来た数、ABCまで来た数）
サンプルケース3の計算合わない…
（一旦後回し）
あ
A（あるいは?）が来たとき、そのインクリメントは1ではなくて3^n (nはそれまでに出た？の数）だ
（Aまで来てない数、という項目を設けて利用すればよい）
そこだけ修正して
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2958129

C - All Green

ボーナスの取り方全2^D(≦1024)通り試す方向で
→AC
https://beta.atcoder.jp/contests/abc104/submissions/2956917

おまけ

ボーナス得点の累計に高速ゼータ変換を使って書いてみたやつ

// 略
int solve(int D,int G,vi& p,vi& c) {
    int P = 1 << D;
    vector<int> bonus(P, 0), bonus_k(P, 0);
    for (int i=0,b=1; i<D; ++i,b<<=1) {
        bonus[b] = (i+1)*100 * p[i] + c[i];
        bonus_k[b] = p[i];
    }
    // zeta
    for (int i=0,b=1; i<D; ++i,b<<=1) {
        for (int j=0; j<P; ++j) {
            if (j & b) bonus[j] += bonus[j ^ b];
            if (j & b) bonus_k[j] += bonus_k[j ^ b];  // ← if (j & b) を2回やってるのは行ごとコピペしたから
        }
    }

    int best = INT_MAX;
    for (int j=0; j<P; ++j) {
        int rest = G - bonus[j], bk = bonus_k[j];
        if (rest <= 0) {
            best = min(best, bk);
        } else {
            for (int i=D-1,b=1<<(D-1); i>=0; --i,b>>=1) {
                if (!(j & b)) {
                    int u = (i+1)*100, k = max(0, (rest+u-1)/u);
                    if (k <= p[i]) {
                        best = min(best, bk+k);
                    }
                }
            }
        }
    }
    return best;
}

https://beta.atcoder.jp/contests/abc104/submissions/2961389