AtCoder ABC 269 C - Submask (3Q, 灰色, 300 点)

ビット全探索の要領で列挙できる。だが、実は、部分集合列挙には専用の書き方も存在する！

• 問題へのリンク

問題概要

非負整数 が与えられる。次の条件を満たす非負整数 を昇順にすべて出力せよ。

と をともに二進法で表すとき、 において値が 1 である桁については、 においても値が 1 である。

制約

• 
• を二進法表記したときに、1 の個数は 15 以下

考えたこと

特別な知識なしで解くには、次のようにすればよい。まず、 を二進法で表したときに、値が 1 であるような桁を としよう。

このとき、ビット全探索を用いて、集合 の部分集合をすべて列挙して、それを整数値に直して出力すればよい。

しかし、実は部分集合列挙はとても簡単な実装方法が存在する。整数値 で表される集合の部分集合を列挙するには、次のように書ける。次の for 文により、整数値 S は、N の部分集合を表す。注意点として、この書き方では空集合 ( のとき) は探索しない。

for (int S = N; S; S = (S - 1) & N) {

}

今回の問題でもこの書き方で AC できる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    
    vector<long long> res({0});
    for (long long S = N; S; S = (S - 1) & N) {
        res.push_back(S);
    }
    
    sort(res.begin(), res.end());
    for (auto v : res) cout << v << endl;
}