< hamamuさんのAI生成コード置き場

部分和判定

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

//generated by GPT-5.2-Codex, modified by hamamu
vector<bool> subsetSum(const vector<long long>& Ws,long long S) {
    using ll  = long long;
    using ull = unsigned long long;

    // --- 同じ重みをまとめて 2ベキ分解する ---
    // 1) Ws をソート
    // 2) 連続区間ごとに個数を数える
    // 3) 個数 c を 1,2,4,...,残り に分解して重み w*take を作る
    vector<ll> items;
    {
        vector<ll> W = Ws;
        sort(W.begin(),W.end());

        for (ll i = 0; i < (ll)W.size(); ) {
            ll w = W[i];
            ll j = i;
            while (j < (ll)W.size() && W[j] == w) ++j;
            ll c = j - i; // w の個数

            if (w > 0 && w <= S) { // 非正や S 超えは寄与しない
                for (ll k = 1; c > 0; k <<= 1) {
                    ll take = min(k,c);
                    if (w*take > S) break; //既にw*(take-1)まで実現可能→break
                    items.push_back(w * take);
                    c -= take;
                }
            }

            i = j;
        }
    }

    // --- ビット配列の準備 ---
    ll blocks = S / 64 + 1; //64ビットブロック数  S+1ビット必要
    vector<ull> dp(blocks); //dp[i]の第jビットが1 ⇔ 和(64*i+j)が実現可能
    dp[0] = 1; // 和0は常に実現可能

    // --- 各重み w について dp |= (dp << w) を実行 ---
    for (ll w : items) {
        ll wblock = w / 64;       // ブロック単位のシフト量
        int wbit  = (int)(w % 64);// ブロック内ビット単位のシフト量

        // 上位ブロックから更新（下位からだと上書きで壊れる）
        for (ll i = blocks - 1; i >= 0; --i) {
            // srcSameBlock: wblock個下のブロックから来る主要部分
            ull srcSameBlock = (i >= wblock) ? dp[i - wblock] : 0;
            ull shiftedMain = srcSameBlock<<wbit; //更にビット単位シフト

            // srcPrevBlock: さらに1つ下から溢れてくる部分
            ull srcPrevBlock = (i >= wblock + 1) ? dp[i - wblock - 1] : 0;
            ull shiftedCarry = wbit ? (srcPrevBlock >> (64-wbit)) : 0; //溢れ分を下位bitに
            // ↑wbit==0 のとき rshift=64 となり未定義動作なので、
            // 三項演算子でシフト自体をスキップする

            dp[i] |= shiftedMain | shiftedCarry;
        }
    }

    // --- ビット配列から vector<bool> へ変換 ---
    vector<bool> can(S + 1,false);
    for (ll s = 0; s <= S; ++s) {
        ll bi = s / 64;         // ブロック番号
        int bj = (int)(s % 64); // ブロック内ビット位置
        if (dp[bi] & (1ULL << bj)) can[s] = true;
    }
    return can;
}
/*
- ------ 部分和判定 ------
- ナップザックDP＋bit演算で解く
- 同じ重みを2ベキずつまとめて高速化

vector<bool> can=subsetSum(Ws,S);
.             ↑           ↑ └和の上限
. can[s] true:和sが可能    └ 重み集合 vll{3,1,4,5}
.     s=0~S
*/