ABC056/D - No Need

https://beta.atcoder.jp/contests/abc056/tasks/arc070_b

考察

要素の順番は関係無いので、考えやすくするためにとりあえずa_iは昇順ソートされているものだとします。

まず、「カードiが必要であること」とはどういうことかと考えてみると、条件の否定を考えて「カードiを含むある集合が存在して、その集合からiを抜くと総和がK未満になってしまう」ということになります。

このことから「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」ということと同値だと分かります。もし作れるのなら、そこにカードiを加えた集合は良い集合になるのでカードiは必要だと分かるし、逆に[K - a_i, K)に含まれる数が作れないのならiを加えたところで良い集合になるものは存在しないと分かるからです。

なので、各iについて「カードiを除いた全ての数で[K - a_i, K)に含まれる数が作れるか」を調べていけばいいことになってこれを愚直に総当たり＋部分和DPでやるとO(N^2 * K)になってしまいます。これでもN = K = 400までの部分点は取れそうですが、N = K = 5000の満点は無理そうなのでもう少し計算量を落とす必要があります。

まず考えられるのは「愚直に全部見ていく必要はあるのか？」ということです。もし「iが必要である⇒i+1も必要である」というような単調性が成り立っていれば、真面目に全探索する必要はなく二分探索を使えばいいのでそうなっていないかと考えたくなります。a_iが昇順ソートされているものだと思うと、区間[K - a_i, K)はiが増えるごとに広がっていくので何となくそのような単調性がありそうだなと思います。

少し考えると実際に、このような単調性を示すことができます。

もし、iが必要であるとすると、iを除いた集合で[K - a_i, K)に含まれる整数が作れます。もしそれがi+1を含まないもので作れているとすると、i+1を除いた集合でも明らかに作れて、それは[K - a_{i+1}, K)にも明らかに含まれるので良いです。
問題はi+1を使って作っている場合ですが、このとき、i+1をiに置き換えて作った整数はいくらか小さくはなりますが[K - a_{i+1}, K)に含まれていることは分かります。小さくなった分だけ区間が広がっているからです。

こうやって二分探索が使えることが分かると、計算量はO(N * K * log(N))に落とすことができます。それでも、最大ケースでは3 * 10^8程度になるっぽいのでこれは想定解じゃないのかな……と思いましたが、１つの想定解であったそうです。
実際これをやってみるとそんなに無理なく通すことができました。

そしてO(N*K)の想定解もあったようで、こちらは前の方から部分和DPをやって後ろの方から部分和DPをやると、{0, ..., i-1}で作れる整数と{i + 1, ..., N - 1}で作れる整数が分かるので、これらの結果をtwo-pointersでいい感じにやるとO(N*K)で出来るみたいな感じでした。（本当は解説にはtwo-pointersじゃなくて「累積和を使う」と書いてあるのですが、よく分かりませんでした）

ソースコード

ソースコードはテンプレートとか適当に省略しています。

二分探索

void main() {
    int n, k;
    int[] a;

    scan(n, k);
    a = readln.split.to!(int[]);

    a.sort();

    bool check(int mid) {
        if (a[mid] >= k) {
            return true;
        }
        
        auto dp = new bool[](k + 1);
        dp[0] = 1;

        foreach (i ; 0 .. n) {
            if (i == mid) continue;
            foreach_reverse (j ; a[i] .. k + 1) {
                dp[j] |= dp[j - a[i]];
            }
        }

        foreach (i ; max(0, k - a[mid]) .. k) {
            if (dp[i]) {
                return true;
            }
        }

        return false;
    }


    int btm = -1, top = n;

    while (top - btm > 1) {
        int mid = (top + btm) / 2;

        if (check(mid)) {
            top = mid;
        }
        else {
            btm = mid;
        }
    }

    writeln(btm + 1);
}

前/後ろDP + two-pointers

void main() {
    int n, k;
    int[] a;

    scan(n, k);
    a = readln.split.to!(int[]);

    auto dp1 = new bool[][](n + 1, k);
    dp1[0][0] = 1;

    foreach (i ; 1 .. n + 1) {
        foreach (j ; 0 .. k) {
            dp1[i][j] = dp1[i-1][j];
            if (j - a[i-1] >= 0) dp1[i][j] |= dp1[i-1][j-a[i-1]];
        }
    }

    auto dp2 = new bool[][](n + 1, k);
    dp2[n][0] = 1;

    foreach_reverse (i ; 0 .. n) {
        foreach (j ; 0 .. k) {
            dp2[i][j] = dp2[i+1][j];
            if (j - a[i] >= 0) dp2[i][j] |= dp2[i+1][j-a[i]];
        }
    }

    int ans;

    foreach (i ; 0 .. n) {
        int mv;

        for (int l = 0, r = k-1; l < k; l++) {
            if (!dp1[i][l]) continue;
            for (; r >= 0; r--) {
                if (dp2[i+1][r] && l + r < k) {
                    mv = max(mv, l + r);
                    break;
                }
            }
        }

        if (mv < k - a[i]) ans++;
    }

    writeln(ans);
}