D1. 388535 (Easy Version)
Problem
https://codeforces.com/problemset/problem/1658/D1
Problem - 1658D1 - Codeforces
codeforces.com
https://codeforces.com/problemset/problem/1658/D2
Problem - 1658D2 - Codeforces
codeforces.com
이 문제는 easy version과 hard version으로 나뉜다. 두 문제는 빨간 글씨 부분이 다르다.
Marin과 Gojou는 배열에서 hide-and-seek 게임을 하고 있다.
Gojou는 처음에 다음과 같은 작업들을 한다:
- Gojou는 $l \le r$인 2개의 정수 l과 r을 고른다.
- 다음으로, Gojou는 배열 [l, l+1, ..., r]의 순열인 길이가 r-l+1인 배열 a를 만든다.
- 마지막으로, Gojou는 비밀의 정수 x를 고르고 모든 i에 대하여 $a_i$를 $a_i \oplus x$로 바꾼다($\oplus$는 bitwise XOR 연산이다).
그리고 Marin은 l과 r의 값과 최종 배열 a를 받는다. 그녀가 이기기 위해선 비밀의 정수 x를 찾아야 한다. 그녀를 도와줄 수 있는가?
Gojou가 고른 x가 여러 개일 수도 있다. Marin은 최종 값이 a가 나오도록 하는 아무 x나 찾으면 된다.
Input
첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 10^5$) 이 주어진다.
Easy version: 각 테스트 케이스의 첫째 줄에는 2개의 정수 l과 r이 주어진다. (0 = l $\le r < 2^{17}$)
Hard version: 각 테스트 케이스의 첫째 줄에는 2개의 정수 l과 r이 주어진다. (0 ≤ l $\le r < 2^{17}$)
각 테스트 케이스의 둘째 줄에는 r-l+1개의 정수 $a_1, a_2, ..., a_r-l+1 (0 \le a_i < 2^{17})$이 주어진다. a는 Gojou의 작업들로 만들어질 수 있음이 보장된다.
모든 테스트 케이스에 대하여 r-l+1의 합이 $2^{17}$을 넘지 않음이 보장된다.
Output
각각의 테스트 케이스에 대하여 정수 x를 출력하여라. 답이 여러 개라면 아무거나 출력해라.
Example
Easy version
| input | output |
| 3 0 3 3 2 1 0 0 3 4 7 6 5 0 2 1 2 3 |
0 4 3 |
Hard version
| input | output |
| 3 4 7 3 2 1 0 4 7 4 7 6 5 1 3 0 2 1 |
4 0 3 |
Note
Easy version
첫 번째 테스트 케이스에서, 기존 배열은 [3, 2, 1, 0]이다.
두 번째 테스트 케이스에서, 기존 배열은 [0, 3, 2, 1]이다.
세 번째 테스트 케이스에서, 기존 배열은 [2, 1, 0]이다.
Hard version
첫 번째 테스트 케이스에서, 기존 배열은 [7, 6, 5, 4]이다.
두 번째 테스트 케이스에서, 기존 배열은 [4, 7, 6, 5]이다.
세 번째 테스트 케이스에서, 기본 배열은 [3, 1, 2]이다.
Tutorial
이번 문제는 혼자서 해결하지 못하였으며, Codeforces에서 제공하는 풀이를 바탕으로 해결하였다. Hard version의 풀이를 읽다 나만의 풀이가 생각나 풀어보았지만 잘못된 풀이라는 것을 깨닫고 다시 제공된 풀이를 읽으며 풀었다.
Easy version
이 문제는 비트 문제이며, XOR 연산의 경우 다른 비트에 영향을 주지 않은 연산임을 이용하여 풀 수 있다.
l=0, r=5인 경우를 생각해보자. l부터 r까지 수들을 2진수로 나타내면 아래와 같다.
000, 001, 010, 011, 100, 101
여기서 2번째 자리의 비트만을 가져와보면 [0, 0, 1, 1, 0, 0]이 될 것이다. Easy version의 핵심은 각 자리의 0과 1의 개수이다. Easy version에서는 l이 항상 0이기 때문에 각 자리는 0부터 시작되며 1의 개수가 0의 개수보다 절대 많을 수 없게 된다. 그러나 주어진 a 배열에서는 i번째 자리의 1의 개수가 0의 개수보다 많을 수도 있다. 이는 x의 i번째 자리의 비트가 1이어서 XOR 연산 후 1의 개수와 0의 개수가 서로 바뀌었기 때문임을 알 수 있다. 이를 바탕으로 우리는 각 자리의 0의 개수와 1의 개수를 센 후, x의 i번째 자리의 비트를 1의 개수가 많으면 1로, 0의 개수가 많으면 0으로 설정해주면 된다.
그러나 아직 해결되지 않은 경우가 있다. 바로 1의 개수와 0의 개수가 같을 때이다. 이 경우 x의 i번째 자리는 0과 1 모두 가능하다(가능성이 있는 것이 아니라 실제로 둘 다 답이 된다). l=0이기 때문에 가능한 일인데, 0과 1의 개수가 같다는 것은 i번째 자리를 제외했을 때 나머지 부분이 같은 것이 정확히 2개씩 존재한다는 것을 의미한다. 따라서 x의 i번째 자리의 비트가 0이든 1이든 연산 결과가 동일하게 나오게 된다.
요약하면 아래와 같다.
- $\forall i, 1 \le i <17$
- if i번째 자리의 1의 개수 > i번째 자리의 0의 개수, then x의 i번째 자리의 비트 = 1
- else x의 i번째 자리의 비트 = 0
Hard version
이 문제의 핵심은 어떠한 두 수가 i번째 비트를 제외하고 모두 동일하다면 이 두 수의 결과는 x의 i번째 비트와 무관하다는 사실이다. 또한 l이 짝수이고, r이 홀수라면 모든 i에 대하여 $a_i$와 짝을 이루는 $a_i \oplus 1$가 존재한다는 것을 알 수 있다. 즉, x의 마지막 자리의 비트는 0과 1 모두 답이 될 수 있다. l이 짝수이고, r이 홀수이면 모든 값들을 2로 나눠 범위를 줄인 뒤, 위의 과정을 반복하여 x의 뒷부분을 유추해낼 수 있다. l이 짝수가 아니거나 r이 홀수가 아니라면, 짝을 맺지 못한 $a_i$ 값이 존재할 것이고, 이 값은 $l \oplus x$ 혹은 $r \oplus x$ 값 중 하나일 것이다. 즉, x는 $a_i \oplus l$ 혹은 $a_i \oplus r$ 값이며, 이는 모든 $a_i$ 들에 대해 $a_i \oplus x$ 의 값이 l과 r 사이에 있는지 확인을 통해 답이 맞는지를 확인할 수 있다.
Solution
Easy version
#include <bits/stdc++.h>
#define MAXN (1<<17)+10
using namespace std;
int a[MAXN], cnt[20];
int main()
{
int t, l, r, n, i, j, x;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> l >> r;
n = r-l+1;
for(i=0; i<n; i++){
cin >> a[i];
for(j=0; j<17; j++){
if(a[i] & (1<<j)) cnt[j]++;
else cnt[j]--;
}
}
x = 0;
for(i=0; i<17; i++){
if(cnt[i] > 0) x |= 1<<i;
cnt[i] = 0;
}
cout << x << '\n';
}
return 0;
}
Hard version
#include <bits/stdc++.h>
#define MAXN (1<<17)+10
using namespace std;
int a[MAXN];
set<int> s, s_;
int main()
{
int t, l, r, n, i, j, mul, unpair, x;
bool flag;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> l >> r;
n = r-l+1;
s.clear();
for(i=0; i<n; i++){
cin >> a[i];
s.insert(a[i]);
}
for(mul=1; l%2==0 && r%2==1; l>>=1, r>>=1, mul<<=1){
s_.clear();
for(auto it=s.begin(); it!=s.end(); it++) s_.insert((*it) >> 1);
swap(s, s_);
}
if(l%2 == 1) unpair = l;
else unpair = r;
for(auto it=s.begin(); it!=s.end(); it++){
if(s.find((*it)^1) == s.end()){
x = (*it) ^ unpair;
flag = true;
for(auto jt=s.begin(); jt!=s.end(); jt++){
if(((*jt)^x) < l || ((*jt)^x) > r) flag = false;
}
if(flag) break;
}
}
cout << x * mul << '\n';
}
return 0;
}
마치며...
풀이를 읽는 내내 앞선 글(2022.03.29 - [Algorithm/Codeforces] - Codeforces Round #779 (Div. 2))에서 떠올렸던 풀이가 머리에서 떠나질 않았다. 풀이를 개선해 r-l+1이 짝수인 경우에 대해서도 답을 구하는 방법을 떠올렸지만 끝내 TLE를 받아 실패하였다. 꽤 괜찮은 풀이라 생각하여 아쉬운 마음에 글을 마무리하며 생각한 풀이를 소개해볼까 한다.
기존에 생각한 방법은 r-l+1이 홀수인 경우 $a_1 \oplus a_2 \oplus ... \oplus a_{r-l+1}$이 $l \oplus (l+1) \oplus ... \oplus r \oplus x$가 된다는 사실이었다. 즉, $a_1 \oplus a_2 \oplus ... \oplus a_{r-l+1}$와 $l \oplus (l+1) \oplus ... \oplus r$ 값을 미리 구해놓는다면 x를 한 번의 연산으로 구해줄 수 있다.
문제는 r-l+1이 짝수인 경우인데, 이 경우 l을 제외하여 해결할 수 있다고 생각하였다. 그러나 여기서의 문제는 $a_i$ 중 어떤 값이 $l \oplus x$ 값인지 알 수 없다는 것이다. 여기서 내가 생각한 방법은 모든 $a_i$ 들에 대해 가능성을 열어두는 것이었다. $sum_a$를 $a_i$들을 XOR 한 값, $sum_{lr}$을 (l+1)부터 r까지의 수들을 XOR 한 값으로 정의하자. $a_i$가 $l \oplus x$라면 x는 $a_i \oplus x$와 $(sum_a \oplus a_i) \oplus sum_{lr}$을 동시에 만족해야 한다. 즉, 두 값을 계산한 결과가 같은 $a_i$만이 진정한 후보 값이 될 수 있는 것이다. 나는 이러한 x가 많지 않아 이후 모든 $a_i$에 대하여 x가 정답인지 확인하더라도 시간이 오래 걸리지 않을 것이라고 생각하였으나 아쉽게도 TLE를 맞게 되었다 ㅜㅜ
코드는 아래와 같다.
#include <bits/stdc++.h>
#define MAXN (1<<17)+10
using namespace std;
int a[MAXN];
int main()
{
int t, l, r, n, i, sum_a, sum_lr, x, x_, j;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> l >> r;
n = r-l+1;
sum_a = sum_lr = 0;
for(i=0; i<n; i++){
cin >> a[i];
sum_a ^= a[i];
}
for(i=l; i<=r; i++){
sum_lr ^= i;
}
if(n%2 == 1){
x = sum_a ^ sum_lr;
cout << x << '\n';
}
else{
sum_lr ^= l;
for(i=0; i<n; i++){
x = a[i]^l;
x_ = (sum_a ^ a[i]) ^ sum_lr;
if(x == x_){
for(j=0; j<n; j++){
x_ = a[j] ^ x;
if(x_ < l || x_ > r) break;
}
if(j == n) break;
}
}
cout << x << '\n';
}
}
return 0;
}'Algorithm > Codeforces' 카테고리의 다른 글
| Codeforces Round #781 (Div. 2) - D (0) | 2022.04.16 |
|---|---|
| Educational Codeforces Round 126 (Rated for Div. 2) (0) | 2022.04.12 |
| [Codeforces] Codeforces Round #781 (Div. 2) (0) | 2022.04.12 |
| [Codeforces] Codeforces Round #780 (Div. 3) - B (0) | 2022.04.08 |
| [Codeforces] Codeforces Round #779 (Div. 2) (0) | 2022.03.29 |
