Official
H - その計算、合ってますか? Editorial by kaage
条件にあてはまる非負整数の有限多重集合が存在する必要条件を列挙してみましょう。 ただし、以降では、非負整数 \(X,Y\) の二進数表記において「\(X\) で立っているビットが \(Y\) でも必ず立っていること」を \(X\subset Y\) と表記します。
- \(B\subset A\)
- \(C\subset A\)
- \(B\subset C\) または \(B\cap C=\emptyset\)
一つ目・二つ目の条件は自明です。最後の条件は、集合の要素数が奇数のとき \(B\subset C\), 偶数の場合に \(B\cap C=\emptyset\) が成り立ちます。(これらを同時に満たす場合もあります)
ところで、この条件を \(A,B,C\) が満たしているとき、条件を満たす多重集合 \(S\) を次のように構成できます。
- \(B\subset C\) なら \(S=\{A,A,B,B,C\}\)
- \(B\cap C=\emptyset\) なら \(S=\{A,A,B,B+C\}\)
以上より、上に挙げた三つの条件が条件を満たす集合の存在の必要十分条件となることが示せたので、この問題を解くことができました。
#include <iostream>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using lint = long long int;
int main() {
int T;
lint A, B, C;
std::cin >> T;
rep(i, T) {
std::cin >> A >> B >> C;
if ((A & B) == B && ((B & C) == B || (B & C) == 0) && (A | C) == A)
puts("Yes");
else
puts("No");
}
return 0;
}
posted:
last update: