BOJ 30871 ChatGPT의 역작

문제 링크입니다.

문제 요약

아래의 주어진 함수 $f : {\Bbb Z} \rightarrow { 0,1 }$과 길이가 $N$이고 각 원소가 $10^{18}$ 이하의 음이 아닌 정수인 두 수열 $L, R$에 대해 $f(x) = 0$이고 $f(x+1)=1$인 $x$를 구하세요.

f(x):
	value = x
	for i = 1 to N
		l = L[i]
		r = R[i]
		if l ≤ x ≤ r
		   value = value^(((x|l)+(x&r)*(l^r)) mod (2**64))
	return (value >= 0x0123456789ABCDEF)

풀이

함수가 좀 많이 복잡합니다. 일단 몇 가지 특이값을 넣어보면서 관찰합시다.

$x$가 충분히 작거나, 충분히 큰 값이라면, if l ≤ x ≤ r 조건이 항상 불만족되므로, $f(x) = x \ge C$ $(C$는 주어진 상수$)$가 됨을 알 수 있습니다.

따라서 $f(0) = 0, f(10^{18}+1) = 1$입니다.

주어진 함수의 공역이 ${0,1}$이므로 이 함수는 주어진 범위 내에서 $f(c) = 0$이고 $f(c+1) = 1$인 어떤 $c$를 $L, R$의 구성에 관계없이 항상 갖습니다. 나아가, 어떤 구간의 왼쪽 끝 값을 넣었을 때의 함숫값이 $0$, 오른쪽 끝 값을 넣었을 때의 함숫값이 $1$이라면 구간의 길이에 상관없이 그 구간 안에서 필요한 $c$를 찾을 수 있습니다.

구간의 양 끝 값을 제외한 다른 어떤 값을 적당히 $f$에 넣고 결과를 확인합시다. 만약 $0$이라면 오른쪽 절반에 해당하는 구간이 기존의 구간처럼 왼쪽이 $0$, 오른쪽이 $1$로 유지되고, $1$이라면 왼쪽 절반이 같은 조건을 만족합니다. 따라서 이분 탐색을 이용해 구간의 길이를 줄여나가면 ${\cal O}(N \lg (\max L))$의 시간 복잡도에 전체 문제를 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using ull = unsigned long long;

vector<ull> L, R;

bool f(ll x){
	ull ret = x;
	for(int i = 0; i < L.size(); i++) if(L[i] <= x && x <= R[i]) ret = ret^((x|L[i])+(x&R[i])*(L[i]^R[i]));
	return ret >= 0x0123456789ABCDEFLL;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; L.resize(n); R.resize(n);
	for(auto& i : L) cin >> i; for(auto& i : R) cin >> i;
	ll l = 0, r = 1'000'000'000'000'000'001LL;
	while(l < r){
		ll mid = l+r>>1;
		if(f(mid)) r = mid;
		else l = mid+1;
	}
	cout << l-1;
}