AtCoder ABC 238 D,E

재밌는 문제들입니다.

 

 

D. 

https://atcoder.jp/contests/abc238/tasks/abc238_d

D - AND and SUM

 

x & y = a , x+y=s인 (x,y)가 존재하는지 O(1)에 판정해봅시다.

x & y = a이므로, x>=a, y>=a 입니다. 

x=x1+a, y=y1+a라고 두면, x1 & y1 = 0입니다.

이제 x1 & y1 = 0이고, x1+y1=s-2a인 x1,y1이 존재하는지 알아봅시다.

x1과 y1을 이진법으로 썼을 때, a를 이진법으로 나타냈을 때 1의 위치를 제외한 부분만

겹치지 않게 채워집니다. 따라서 x1+y1은 a의 1의 위치를 제외한 위치들의 부분집합입니다.

따라서 s-2a & a = 0이면 항상 존재하게 만들어줄 수 있습니다. 

따라서 종합하면 s>=2a 이면서 (s-2a)&a=0이면 됩니다. 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tc; cin >> tc;
	while (tc--) {
		ll a, s; cin >> a >> s;
		ll diff = s - 2 * a;
		if (diff >= 0) {
			if (!(diff & a)) {
				cout << "Yes\n";
				continue;
			}
		}
		cout << "No\n";
	}
}

 

 

 

E.

https://atcoder.jp/contests/abc238/tasks/abc238_e

E - Range Sums

 

식을 누적합배열로 바꾸면, p(r)-p(l-1)이 주어질 때 p(n)-p(0)을 알 수 있는지 묻는 문제입니다.

N이 20만이므로 NlogN에 해결해야 합니다. 문제를 그래프로 모델링하는게 포인트입니다.

p(r)-p(l-1)이 주어지면 점 l-1 과 점 r 을 이어줍시다. 그럼 이어준 점들끼리는 p(y)-p(x) 꼴을 항상

만들어줄 수 있음을 관찰할 수 있습니다. 3개, 4개에 대해서만 해보면 그 이상의 점들은 3,4개씩

모아서 압축해줄 수 있기 때문에 전부 가능함을 알 수 있습니다.

따라서 결론은 Q개의 연결 쿼리가 들어오면, 마지막에 0과 N이 연결되었는지 확인해주면 됩니다.

확인과정은 union-find로 NlogN에 처리할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
int n, q, l, r, par[200005];

int find(int x) {
	return (!~par[x]) ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
	x = find(x), y = find(y);
	if (x ^ y) par[y] = x;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> q;
	memset(par, -1, sizeof(par));
	while (q--) {
		cin >> l >> r;
		uni(l - 1, r);
	}
	cout << (find(0) == find(n) ? "Yes" : "No");
}