[yukicoder] No. 0939 and or
問題
方針
\( X, Y \) を \( 2 \) 進数で表現したときの \( i \) 番目のビットを \( x_i, y_i \) とします。同様に \( A, B \) についても \( a_i, b_i \) とします。条件より、\( x_i \wedge y_i = a_i \) かつ \( x_i \vee y_i = b_i \) となります。
\( a_i = 1 \wedge b_i = 0 \) を満たす \( x_i. y_i \) は存在しません。これは、\( x_i \wedge y_i = 1 \) のとき、\( x_i = 1 \wedge y_i = 1 \) であり、このとき、\( x_i \vee y_i = 1 \) となるからです。つぎに、\( a_i = 0 \wedge b_i = 0 \) のときは、\( x_i = 0 \wedge y_i = 0 \) となります。つぎに、つぎに、\( a_i = 1 \wedge b_i = 1 \) のときは、\( x_i = 1 \wedge y_i = 1 \) となります。
最後に、\( a_i = 0 \wedge b_i = 1 \) のとき、\( x_i = 1 \wedge y_i = 0 \) または \( x_i = 0 \wedge y_i = 1 \) の \( 2 \) 通りあります。この条件を満たすビットの数を \( c \) とすると、答えは、\( \max(1, \ 2^{c – 1} ) \) となります。 \( 2^{c – 1} \) となっているのは、\( X \leq Y \) という条件から、\( a_i = 0 \wedge b_i = 1 \) を満たす最大の \( i \) について、\( x_i = 0 \wedge y_i = 1 \) となっていなければならないからです。
また、自然数 \( n \) の \( i \) 番目のビットが \( 0 \) かどうかは、\( n \wedge 2^{i} = 0 \) であることを確かめれば良いです。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll A, B; cin >> A >> B; ll t = 1; ll ans = 0; for (int i = 0; i < 31; i++) { ll u = A & t; ll v = B & t; if (u != 0 && v == 0) { cout << 0 << "\n"; return 0; } else if (u == 0 && v != 0) { ans++; } t *= 2; } ans = max(ans, 1ll); cout << (1<<(ans - 1)) << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません