問題へのリンク
D - AND and SUM
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
考察
Step1:問題文をちょっとわかりやすくします
“X AND Y = a“を満たすという事は
- aを表現する為に必要なbitのみX,Yの両方で立つ
- aを表現する為に不必要なbitは、{立てない, X,Yのどちらかでのみ立てる}の2通りの選択肢がある
そのため問題文は、
“最大桁のbitから順番に見ていった際に、aで使われていないbitを{立てるか, 立てないか}を選ぶことで、和をsにできるか?”
という意味になります
Step2:実際に上位桁から順に立てていきます
注意点として、和(sum)は最初からa * 2という値を持っています。
理由は、X and Y = aとなるためには、必ずX, Yがそれぞれaという値を持つためです
入力が a, s = 1, 8の場合
a, s = 1, 8
最初の状態
a = 1とするために必ず立てる必要がある
↓
0001
sum = 2
(sum + 2^3) > 8なので立てない
↓
0001
sum = 2
(sum + 2^2) <= 8なので立てる
↓
0101
sum = 6
(sum + 2^1) <= 8なので立てる
↓
0111
sum = 8
元から立っているので飛ばす
↓
0111
sum = 8
終了
sum == sとなっているのでYes
つまづきそうな所の解説
0111でsum = 8???
となった方、
X 0111
+
Y 0001
で8ですよっACしたコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int t;
cin >> t;
for (int t_i = 0; t_i < t; t_i++) {
ll a, s;
cin >> a >> s;
/*
aの立っていないbitをうまく立てることで、和をsと一致させられるか?
->上位桁から順に立てるか立てないかを決めていけば良い
*/
//注意: 和は&を達成する為に、a*2を必ず持っている所から始める
ll sum = a * 2;
for (int i = 60; i >= 0; i--) {
//aの方で、立っている場合は飛ばす(これ以上使えない)
if (a & (1LL << i)) continue;
//立てても和がsを超えないなら足す
if (sum + (1LL << i) <= s) sum += (1LL << i);
}
cout << (sum == s ? "Yes" : "No") << endl;
}
}
コメント