をやってて、bitで組み合わせの全探索できるなみたな感じには思えたけど実装がわからなかったので覚え書き程度に書く。

bit全探索

ビットを仕切りに見立てて、ビットを全探索することで部分集合などを求める探索

今回の場合ようは、

という文字列があったとき

というビットを用いて

1234|5|67

のように分割されているとみなすことができる。

計算量は2ⁿ

コード

以下提出したコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
using namespace std;
 
int main(){
  string s;
  cin >> s;
  vector<string> nums;
  for (int i=0; i<s.length(); i++) nums.push_back(s.substr(i, 1));
 
  long res = 0;
  long tmp;
  long digit;
  long sum = 0;
  string ssum = "";
  for (int i=0; i< (1 << (nums.size() - 1)); i++) { // bit演算なので条件
    sum = 0;
    tmp = 0;
    digit = 1;
    ssum = nums[0];
    for (int k=0; k<nums.size()-1; k++) {
      if (i & (1 << k)) { // 見てるbitと現在見てる桁に+がついているとき
        sum +=  stol(ssum);
        ssum = "";
      }
      ssum += nums[k+1];
    }
    sum += stol(ssum);
    res += sum;
  }
 
  cout << res << endl;
}

前にビットを使ったとき、アホなので"00000"みたいな文字列作って頑張ってた気がします

bitsetを使えばもっと綺麗にかけそうな気がしないでもない

whileD'iary

日記とか

bit全探索

bit全探索

コード