ICPC Japan Domestic 2023 D

#上界・下界 #DP #全探索

問題

合計が \(N\) となる正整数の選び方であって、 \(S_i\) が o であるような全ての \(i\) について、選んだ数のいくつかを取って合計したときに \(i\) にできるように、数字を選びたい。最小で何個選ぶ必要があるか？
link

解法

まず、答えの上界を考える。二進数表記の気持ちになると、1, 2, 4, 8, ...というように2の累乗点のセットを用意してあげれば、条件を達成することができる。 \(N\leq100\) であり、 \(2^7>100\) であるため、多くとも7問用意すれば条件を満たすことが可能である。
よって、少ない方から順に、 \(x\) 問用意して条件を達成できるか？を判定していけば良い。和が \(N\) である、という制約に注意すると(適当な \(x-1\) 個を用意すると残りの一つは勝手に決まるので)用意する問題セットとしてあり得る組は \({}_{100}C_{x-1}\) 通りとなり、最悪で1ケース辺り \(\sum_{x=1}^6 {}_{100}C_{x-1}=79375496\) 通りを計算することによってこの問題が解くことができる。
実際には最大で100ケースありこのまま解くには定数倍が厳しいが、
- bitset高速化をする
- 選ぶ際に、小さい方から選ぶという条件をつけることで重複を省く
- DPをオンラインに計算する
- \(S\) に含まれる o の位置を事前に列挙しておく
などの定数倍高速化を行うことでこの問題が解ける。 提出コード

string s;
vector<int> o_positions;

bool dfs(int idx, int left, int last, bitset<101>& bs) {
    vector<int> updated; 

    if(idx==0) {
        per(j, s.size()-left) {
            if(!bs[j] || bs[left+j]) continue;
            bs[left+j] = true;
            updated.push_back(left+j);
        }
        
        bool res = true;
        for(auto i: o_positions) res = res && bs[i];

        for(auto pos : updated) {
            bs[pos] = false;
        }

        return res;
    }

    bool res = false;

    rep2(i,last,left+1) {
        if(left-i<i) break;
        per(j, s.size() - i) {
            if(!bs[j] || bs[i+j]) continue;
            bs[i+j] = true;
            updated.push_back(i+j);
        }

        res = dfs(idx-1, left-i, i, bs);
        if(res) break;
        
        for(auto pos : updated) {
            bs[pos] = false;
        }
        updated.clear();
    }
    return res;
}

void solve(int n) {
    cin >> s;
    o_positions.clear();
    rep(i, s.size()) if(s[i]=='o') o_positions.push_back(i);

    bitset<101> bs;
    bs[0] = true;
    rep(i,6){
        auto ret = dfs(i, n, 1, bs);
        if(ret) {
            cout << i+1 << '\n';
            return;
        }
    }
    cout << "7\n";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while(n) {
        solve(n);
        cin >> n;
    }
}