問題

合計が$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ケース辺り通りを計算することによってこの問題が解くことができる。

実際には最大で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;