D - Simple Knapsack (arc073_b)

Quiz

https://atcoder.jp/contests/abc060/tasks/arc073_b

Submit

https://atcoder.jp/contests/abc060/submissions/3924457

今回の盲点

• wの範囲が異常に狭いので戦略が変わる
• 累積和の元の配列の長さが0だとエラーになる（下記コードの場合）

    Ac0[0] = V0[0];
    FOR(i, 1, n0){
        Ac0[i] = Ac0[i-1] + V0[i];
    }

• なのでこうする（下記）

    if(n0>0) Ac0[0] = V0[0];
    FOR(i, 1, n0){
        Ac0[i] = Ac0[i-1] + V0[i];
    }

• w, w+1, w+2, w+3 の重さの個数を求める際

    ll value_max = 0;
    FOR(i, 0, n0+1){
        FOR(j, 0, n1+1){
            FOR(k, 0, n2+1){
                FOR(l, 0, n3+1){

• こうするのが良い
• 最初、l = N - i - j - k としていたが間違い
  • N個選ぶ必要は無いため

最後に

• こうやって盲点を消していくのだ

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?