Help us understand the problem. What is going on with this article?

bit全探索って何?

ビット全探索とは

二進数ビットを用いて、ある集合の部分集合を全列挙するアルゴリズムの事を言う。

例えばABCという集合ならば、
{},{A},{B},{C},{AB},{AC},{BC},{ABC}という8個の部分集合に分けられる!
これをC++でプログラムを書くと...

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

int main(){
    string t="ABC";
    for (int bit=0; bit<(1<<3); bit++){
        string s="";
        for (int i=0; i<3; i++){
            if (bit&(1<<i)) s+=t[i];
        }
        cout << "{" << s << "}" << endl;
    }
}
#出力結果
{}
{A}
{B}
{AB}
{C}
{AC}
{BC}
{ABC}

問題と提出コード

以下の問題はbit全探索に慣れるためにそれを用いて記述しました。そのためこれらの問題には、より簡単な解法が存在します。

第一問 C - Train Ticket

問題概要

4桁の番号が与えられる。番号と番号の間全てに+か-を挿入してその演算結果が7になるものを出力せよ。

解法

'+'か'-'の2通りを全探索すれば良いことが問題文から見て取れます。高々2^3回のループなので全探索で問題ありません。

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

int main(){
        string s,t;
        cin >> s;
        t=s[0];
        int sum=0;
        //2^3回ループ
        for (int bit=0; bit<(1<<3); bit++){
                int a;
                //文字列をintに変換
                sum=s[0]-'0';
                t=s[0];
                for (int i=0; i<3; i++){
                        a=s[i+1]-'0';
                        //bitが立ってたら+
                        if(bit & (1<<i)) {
                                sum+=a;
                                t=t+'+'+s[i+1];
                        }else{  //bitが立っていなかったら-
                                sum-=a;
                                t=t+'-'+s[i+1];
                        }
                }
                //和が7なら文字列を出力
                if(sum==7) {
                        cout << t << "=7" << endl;
                        break;
                }
        }
        return 0;
}

まとめ

①全ての部分集合をbitで0と1のみで表す!

②集合を一つずつ分ける

ex)ABC→'A','B','C'
そのあと、if文で一文字ずつあるか無いかを確かめれば、if,else含めて、全てを参照することができる!

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away