問題

合計が$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 << '
';
            return;
        }
    }
    cout << "7
";
}

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