# 問題合計が$N$となる正整数の選び方であって、$S_i$が`o`であるような全ての$i$について、選んだ数のいくつかを取って合計したときに$i$にできるように、数字を選びたい。最小で何個選ぶ必要があるか？ [link](https://onlinejudge.u-aizu.ac.jp/services/ice/?problemId=1667) # 解法まず、答えの上界を考える。二進数表記の気持ちになると、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`の位置を事前に列挙しておくなどの定数倍高速化を行うことでこの問題が解ける。[提出コード](https://github.com/ardRiriy/cp-libs/blob/main/icpc/domestic_japan/2023/d.cpp) ```cpp string s; vector o_positions; bool dfs(int idx, int left, int last, bitset<101>& bs) { vector 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> 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; } } ```

ICPC Japan Domestic 2023 D