atcoder ABC147 C問題(ビット全探索の問題)についての質問
解決したいこと
Atcoder ABC147 C - HonestOrUnkind2
ビット演算についての質問
発生している問題
ビット表記のi番目のフラグが立っているかを調べる際、以下の表記について同じ働きをすると認識しているのですが、上で記述するとWA、下で記述するとACになります。
この表記の違いを教えてほしいです。
誤)
if(bit & 1 << x[i][j])
正）
if(bit >> x[i][j] & 1)
以下にソースコード全文載せます。(56行目辺りです)
該当するソースコード
#include <atcoder/all>
#include <bits/stdc++.h>
#include <string>
using namespace std;
using namespace atcoder;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++) // 単純なfor文
#define reps(i, m, n) for (int i = (int)(m); i < (int)(n); i++) // 指定for文
#define pb push_back
#define eb emplace_back
//--------------------------------------------------//
//--------------------------------------------------//
int main() {
//---------------text temprate--------------------//
ifstream in("in.txt");
if (in.is_open()) {
cin.rdbuf(in.rdbuf());
}
//---------------text temprate--------------------//
//------------------------------------------------//
//---------------koko kara kizyutu----------------//
int n;
cin >> n;
vector<int> a(n);
vector<vector<int>> x(n), y(n);
rep(i, n) {
cin >> a[i];
rep(j, a[i]) {
int u, t;
cin >> u >> t;
u--;
x[i].pb(u);
y[i].pb(t);
}
}
bool hantei;
int ans = 0;
rep(bit, 1 << n) {
hantei = true;
rep(i, n) {
if (!(bit & (1 << i)))
continue;
//該当箇所ここです
rep(j, a[i]) {
if ((bit & (1 << x[i][j])) ^ y[i][j])
hantei = false;
}
}
if (hantei)
ans = max(ans, __builtin_popcount(bit));
}
cout << ans << endl;
//---------------koko made kizyutu----------------//
//------------------------------------------------//
}
自分で試したこと
調べたところ、前者は1をiだけシフトした後すべてのビットをチェックするのに対して、後者はシフトした後1ビット目のみを比較するため2つの式が異なる結果を返す可能性があるそうです。
この説明でなんとなくわかったような気がしたのですが、それであればすべてのビットを比較する前者を使うメリットが全く分かりません。
お聞きしたいこと
①上で記述した2つのコードの働きの違いについて
②「自分で試したこと」で書いた2つのコードの違いの仮説が正しかった場合、なぜ色々なサイトや記事で前者のコードが多く使われているのか。
最後に
初学者なので頓珍漢な事しているかもしれませんが、教えていただけると嬉しいです。T^T
0
