https://atcoder.jp/contests/abc014/tasks/abc014_2
int sum = 0;
// n個の商品について
for(int i = 0; i < n; i++){
// bit xのi桁目は1かどうか -> bit xにi個目の商品は含んでいるか
if((x >> i) & 1) sum += a[i];
}
cout << sum << endl;
https://atcoder.jp/contests/abc079/tasks/abc079_c
一番簡単な $2^N$ のNが定数のBit全探索。op1,op2,op3の状態は+か-の2通りなので、全パターンは $2^3 = 8$通り。折角なのでBit全探索で探索する。
3個のopの+/−のbit集合を全探索
for(int bit = 0; bit < (1 << 3); bit++){
/* bitで表した集合に対して、処理 */
}
3個のopについて
もし、集合bitのi桁目が1なら+、0なら-かを調べるため全探索。配列opはi番目のopが+か-かを表す
vector<char> op(3);]
for(int i = 0; i < 3; i++){
// bitのi桁目は1かどうか -> bitのopのi番目は+か
if((bit >> i) & 1){
op[i] = '+'; // 1なら+
}else{
op[i] = '-'; // 0なら-
}
}
配列opを用いて、値を計算する
int calc = s[0] - '0'; // calcに予めs[0]を入れる
for(int i = 0; i < 3; i++){
if(op[i] == '+'){
calc += (s[i + 1] - '0');
}else{
calc -= (s[i + 1] - '0');
}
}
// opの+/-についてbit全探索
// bit: opの+/-の集合を表す
for(int bit = 0; bit < (1 << 3); bit++){
vector<char> op(3);
for(int i = 0; i < 3; i++){
// bitのi桁目は1かどうか -> bitのopのi番目は+か
if((bit >> i) & 1){
op[i] = '+'; // 1なら+
}else{
op[i] = '-'; // 0なら-
}
}
int calc = s[0] - '0'; // calcに予めs[0]を入れる
for(int i = 0; i < 3; i++){
if(op[i] == '+'){
calc += (s[i + 1] - '0');
}else{
calc -= (s[i + 1] - '0');
}
}
if(calc == 7){
cout << s[0] << op[0] << s[1] << op[1] << s[2] << op[2] << s[3] << "=7" << endl;
return 0;
}
}