Codeforces Global Round 21
A. NIT orz!
Problem
Problem - A - Codeforces
codeforces.com
번호가 1부터 부여된 n개의 정수로 이루어진 배열 a와 하나의 정수 z가 주어진다. 너는 다음 작업을 몇 번이든(0번도 가능) 할 수 있다:
- $1 \le i \le n$인 양의 정수 i를 고른다. 동시에 $a_i$를 ($a_i \, or \, z$)로, $z$를 ($a_i \, and \, z$)로 바꾼다. 다시 말해 현재 $a_i$와 $z$의 값이 $x$, $y$라고 하면, $a_i$는 ($x \, or \, y$)로, z는 ($x \, and \, y$)로 바꾼다.
여기서 or와 and는 비트연산을 의미한다.
여러(0번도 가능) 작업을 수행한 후 배열 a의 최댓값으로 가능한 최댓값을 구하여라.
Input
각 테스트는 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 수를 의미하는 t($1 \le t \le 100$) 이 주어진다. 테스트 케이스에 대한 설명은 다음에 나온다.
각 테스트 케이스의 첫째 줄에는 두개의 정수 n과 z($1 \le n \le 2000, 0 \le z < 2^{30}$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 n개의 정수 $a_1, a_2, ..., a_n (0 \le a_i < 2^{30})$이 주어진다.
전체 테스트 케이스의 n의 합이 $10^4$을 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여, 문제의 정답을 의미하는 하나의 정수를 출력하여라.
Example
| input | output |
| 5 2 3 3 4 5 5 0 2 4 6 8 1 9 10 5 7 7 15 30 29 27 3 39548743 10293834 10284344 13635445 |
7 13 11 31 48234367 |
Note
예제의 첫번째 테스트 케이스에서, 최적의 작업 순서 중 하나는 다음과 같다:
- i=1 작업을 한다. 이제 $a_1$은 (3 or 3) = 3이고, $z$는 (3 and 3) = 3이다.
- i=2 작업을 한다. 이제 $a_2$는 (4 or 3) = 7이고, $z$는 (4 and 3) = 0이다.
- i=1 작업을 한다. 이제 $a_1$은 (3 or 0) = 3이고, $z$는 (3 and 0) = 0이다.
이 작업 이후, 수열 a는 [3, 7]이 되고, 이것의 최댓값은 7이다. 우리는 a에서의 최댓값이 7을 넘지 않음을 보일 수 있으며, 그래서 답은 7이다.
예제의 네번째 테스트 케이스에서, 최적의 작업 순서 중 하나는 다음과 같다:
- i=1 작업을 한다. 이제 $a_1$은 (7 or 7) = 7이고, $z$는 (7 and 7) = 7이다.
- i=3 작업을 한다. 이제 $a_3$은 (30 or 7) = 31이고, $z$는 (30 and 7) = 6이다.
- i=5 작업을 한다. 이제 $a_5$는 (27 or 6) = 31이고, $z$는 (27 and 6) = 2이다.
Tutorial
비트연산의 특성을 이용한 문제이다.
z는 계속해서 and 연산을 하기 때문에 절대로 커지지 않는다. 따라서 몇 번의 작업 후, $a_i$가 답이 된다면 처음부터 $a_i \, or \, z$를 한 값보다 크지 않다는 것을 알 수 있다. 또한 우리는 $a_i$가 답이라고 가정했으므로, 그 값은 $a_i \, or \, z$일 것이다.
즉, 우리는 초기 a와 z에 대하여 $a_i \, or \, z$의 최댓값을 구해주면 된다.
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, z, i, a, maxi;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n >> z;
maxi = 0;
for(i=0; i<n; i++){
cin >> a;
maxi = max(maxi, a | z);
}
cout << maxi << '\n';
}
return 0;
}
B. NIT Destroys the Universe
Problem
Problem - B - Codeforces
codeforces.com
정수 집합 S에서, $mex(S)$를 S에 나타나지 않은 음이 아닌 가장 작은 정수로 정의하자.
NIT는 세계를 파괴하기로 결정했다. 그는 타노스처럼 강하지 않기에 그는 손가락을 여러 번 튕겨 세계를 파괴할 수 있다.
세계는 번호가 1번부터 붙은 길이가 n인 배열 a로 표현할 수 있다. NIT가 그의 손가락을 튕기면, 그는 배열에 다음의 작업을 할 수 있다.
- 그는 $1 \le l \le r \le n$을 만족하는 양의 정수 l과 r을 고른다. $w = mex({a_l, a_{l+1}, ..., a_r})$이라고 하자. 모든 $l \le i \le r$에 대하여, $a_i$를 $w$로 바꾼다.
모든 $1 \le i \le n$에 대하여, $a_i = 0$이면 세계는 파괴되었다고 말한다.
NIT가 세계를 파괴하기 위하여 그의 손가락을 튕겨야 하는 최소 횟수를 구하여라. 이는 배열의 모든 원소를 0으로 바꾸기 위해 필요한 NIT의 작업의 최소 횟수를 구하라는 말이다.
Input
각 테스트는 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 수 t($1 \le t \le 10^4$)이 주어진다. 테스트 케이스들의 설명은 다음에 나온다.
각 테스트 케이스의 첫째 줄에는 하나의 정수 n($1 \le n \le 10^5$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 n개의 정수 $a_1, a_2, ..., a_n (0 \le a_i \le 10^9)$이 주어진다.
모든 테스트 케이스에서 n의 합은 $2 \cdot 10^5$을 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여, 문제의 답을 의미하는 하나의 정수를 출력하여라.
Example
| input | output |
| 4 4 0 0 0 0 5 0 1 2 3 4 7 0 2 3 0 1 2 0 1 1000000000 |
0 1 2 1 |
Note
첫번째 테스트 케이스에서, 우리는 0번의 작업을 한다. 배열의 모든 원소는 이미 0이다.
두번째 테스트 케이스에서, 최적의 방법 중 하나는 l=2, r=5인 작업을 하는 것이다.
세번째 테스트 케이스에서, 최적의 방법 중 하나는 2번의 작업을 하는 것이고, 각각 l=4, r=4와 l=2, r=6이다.
네번째 테스트 케이스에서, 최적의 방법 중 하나는 l=1, r=1인 작업을 하는 것이다.
Tutorial
우린 다음과 같은 성질을 통해 문제를 해결할 수 있다.
- 수열 ${a_l, a_{l+1}, ..., a_r}$에 0이 없다면 한 번의 작업으로 수열 ${a_l, a_{l+1}, ..., a_r}$은 모두 0이 된다.
- 수열 ${a_l, a_{l+1}, ..., a_r}$에 0이 있다면 한 번의 작업으로 수열 ${a_l, a_{l+1}, ..., a_r}$은 하나의 숫자로 동일하게 바뀌며, 작업을 한번 더 수행하면 모두 0으로 바뀐다.
우리는 최소한으로 모든 수열의 값을 0으로 만드는 것이 목표이기 때문에 1번 성질을 이용한다면, 0이 아닌 원소들을 최대한 모아서 한 번에 작업을 하는 게 효율적일 것이다. 즉, 연속한 0이 아닌 원소들의 집합이 몇 개인지를 구해 답을 구해줄 수 있다.
그러나 우리에겐 2번의 성질도 있다. 어떤 수열이든 두번의 작업이면 0으로 만들 수 있다는 것이다. 즉, 앞선 방법으로 0번이나 1번의 작업으로 가능하다고 판단이 된다면 0 혹은 1을 출력하면 되고, 그렇지 않으면 2를 출력하면 된다.
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, i, a, cnt;
bool flag;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
cnt = flag = 0;
for(i=0; i<n; i++){
cin >> a;
if(a == 0){
cnt += flag;
flag = 0;
}
else{
flag = true;
}
}
cout << min(2, cnt+flag) << '\n';
}
return 0;
}
C. Fishingprince Plays With Array
Problem
C. Fishingprince Plays With Array
Problem - C - Codeforces
codeforces.com
Fishingprince는 배열 $[a_1, a_2, ..., a_n]$을 가지고 놀고 있다. 또한 그는 마법의 수 m을 가지고 있다. 그는 다음 2가지 작업을 할 수 있다:
- $a_i$가 m으로 나누어지는 $1 \le i \le n$을 고른다. $a_i$를 m개의 ${a_i} \over {m}$로 바꾼다. 다른 원소들의 순서는 바뀌지 않는다. 예를 들어 m=2이고 a=[2, 3], i=1일 때, a는 [1, 1, 3]으로 바뀐다.
- $a_i = a_{i+1} = ... = a_{i+m-1}$인 $1 \le i \le n - m + 1$을 고른다. 이 m개의 원소들을 하나의 $m \cdot a_i$로 바꾼다. 다른 원소들의 순서는 바뀌지 않는다. 예를 들어 m=2이고 a=[3, 2, 2, 3], i=2일 때, a는 [3, 4, 3]으로 바뀐다.
작업을 하는 동안 배열의 길이가 바뀔 수 있음에 주의하여라. 그동안 n의 값은 현재 배열의 길이로 정의된다. (입력으로 주어진 n과 다를 수 있다.)
Fishingprince는 다른 배열 $[b_1, b_2, ..., b_k]$를 갖고 있다. 그가 몇 번의(0번도 가능) 작업을 통해 a를 b로 바꿀 수 있는지 판단하여라.
Input
각 테스트는 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 수를 나타내는 t($1 \le t \le 10^4$)이 주어진다. 테스트 케이스의 설명은 다음에 나온다.
각 테스트 케이스의 첫째 줄에는 두개의 정수 n과 m($1 \le n \le 5 \cdot 10^4, 2 \le m \le 10^9$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 n개의 정수 $a_1, a_2, ..., a_n (1 \le a_i \le 10^9)$이 주어진다.
각 테스트 케이스의 셋째 줄에는 하나의 정수 k($1 \le k \le 5 \cdot 10^4$)가 주어진다.
각 테스트 케이스의 넷째 줄에는 k개의 정수 $b_1, b_2, ..., b_k (1 \le b_i \le 10^9)$가 주어진다.
모든 테스트 케이스에서 n+k의 합이 $2 \cdot 10^5$을 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여, a를 b로 바꾸는 것이 가능하면 Yes를, 그렇지 않으면 No를 출력하여라. 글자를 어떤 형식으로든 출력할 수 있다. (대문자 혹은 소문자로)
Example
| input | output |
| 5 5 2 1 2 2 4 2 4 1 4 4 2 6 2 1 2 2 8 2 2 2 1 16 8 3 3 3 3 3 3 3 3 3 4 6 6 6 6 8 3 3 9 6 3 12 12 36 12 16 9 3 2 2 2 3 4 12 4 12 4 12 4 12 4 4 8 3 3 9 6 3 12 12 36 12 7 12 2 4 3 4 12 56 |
Yes Yes No Yes No |
Note
예제의 첫번째 테스트 케이스에서, 우리는 i=2에서 두 번째 작업을 할 수 있다.
[1, 2, 2, 4, 2] → [1, 4, 4, 2].
예제의 두번째 테스트 케이스에서, 우리는 다음과 같이 할 수 있다:
- i=2에서 두번째 작업: [1, 2, 2, 8, 2, 2] → [1, 4, 8, 2, 2].
- i=4에서 두번째 작업: [1, 4, 8, 2, 2] → [1, 4, 8, 4].
- i=3에서 첫번째 작업: [1, 4, 8, 4] → [1, 4, 4, 4, 4].
- i=2에서 두번째 작업: [1, 4, 4, 4, 4] → [1, 8, 4, 4].
- i=3에서 두번째 작업: [1, 8, 4, 4] → [1, 8, 8].
- i=2에서 두번째 작업: [1, 8, 8] → [1, 16].
Tutorial
좀 더 직관적으로 풀이를 설명하기 위해 첫 번째 작업을 분해 작업, 두 번째 작업을 병합 작업이라고 하겠다.
우리는 분해 작업과 병합 작업이 역함수 관계라는 것을 알 수 있다. 배열 A를 분해 작업을 통해 배열 B로 만들 수 있다면, 배열 B를 병합 작업을 통해 배열 A로 만들 수 있고, 그 반대도 가능하다.
배열 a를 적절한 작업을 통해 배열 b로 만들 수 있는지를 알아내는 것은 쉬운 일이 아니다. 그러나 어떠한 배열 c가 있을 때, 배열 a와 b를 분해 작업을 통해서만 배열 c로 만들 수 있는지 알아내는 것은 비교적 쉬운 일이다. 분해 작업만을 이용해 배열 a, b를 배열 c로 만들 수 있다면, 위에서 알아낸 성질을 통해 배열 a를 배열 b로 바꿀 수 있다고 말할 수 있다.
그렇다면 배열 c는 무엇으로 잡는게 좋을까? 처음에는 가능한 작은 원소로 배열 a와 b를 나누는 것을 생각해봤다. 그러나 배열에 따라 최종 배열의 원소가 무수히 많아질 수 있기에 이 방법은 좋은 방법이 아니라고 판단하였다.
다음으로 생각한 방법은 적절히 나누는 것인데, 적절히의 기준은 배열 a와 b에서 현재 살펴보고 있는 위치의 값이 다른 경우, 큰 원소를 나누는 것이다. 앞에서부터 살펴볼 때 원소의 값이 같으면 분해 작업이 가능하다고 해도 결국 같은 원소들로 분해될 것이기에 분해를 할 필요가 없기 때문이다. 그러나 이 경우도 문제는 발생한다. m이 최대 $10^9$이기에 최악의 경우 원소 하나를 분해하더라도 $10^9$개의 원소가 생기기 때문에 이를 모두 큐(deque를 사용했다)에 넣는다면 이마저도 TLE가 걸릴 것이기 때문이다.
그래서 다음으로 생각한 방법은 큐에 단순히 원소의 값만 넣는 것이 아니라 원소의 값과 개수를 같이 넣는 것이다. 시간 복잡도를 계산하지는 않았지만 합리적인 시간이 나올 것이라는 믿음으로 코드를 짰고 Accept를 맞을 수 있었다. (시간이 얼마나 걸리는지 아시는 분은 알려주세요...)
Solution
#include <bits/stdc++.h>
using namespace std;
deque<int> a, b;
int main()
{
int t, n, m, k, i, x, y;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n >> m;
while(n--){
cin >> x;
a.push_back(x);
a.push_back(1);
}
cin >> k;
while(k--){
cin >> x;
b.push_back(x);
b.push_back(1);
}
while(!a.empty() && !b.empty()){
//cout << a.front() << ' ' << b.front() << ' ' << a.size() << ' ' << b.size() << '\n';
if(a.front() == b.front()){
x = a.front();
a.pop_front();
b.pop_front();
if(a.front() == b.front()){
a.pop_front();
b.pop_front();
}
else if(a.front() > b.front()){
y = a.front() - b.front();
a.pop_front();
b.pop_front();
a.push_front(y);
a.push_front(x);
}
else{
y = b.front() - a.front();
a.pop_front();
b.pop_front();
b.push_front(y);
b.push_front(x);
}
}
else if(a.front() > b.front()){
x = a.front();
a.pop_front();
if(a.front() == 1) a.pop_front();
else{
y = a.front();
a.pop_front();
a.push_front(y-1);
a.push_front(x);
}
if(x%m != 0) break;
a.push_front(m);
a.push_front(x/m);
}
else{
x = b.front();
b.pop_front();
if(b.front() == 1) b.pop_front();
else{
y = b.front();
b.pop_front();
b.push_front(y-1);
b.push_front(x);
}
if(x%m != 0) break;
b.push_front(m);
b.push_front(x/m);
}
}
if(a.empty() && b.empty()) cout << "Yes\n";
else cout << "No\n";
while(!a.empty()) a.pop_front();
while(!b.empty()) b.pop_front();
}
return 0;
}
마치며...
최근에 6시 기상 11시 취침을 목표로 하고 있어 의도치 않게 코포를 제시간에 본 적이 없었다. 이게 정해진 시간에 코포를 안 치르니 자연스레 코포 문제를 안 풀게 되었다. 이번에도 캘린더에서 확인도 했고 당일 아침에만 해도 코포 봐야지 생각하고 있었는데 저녁이 되니 잠이 몰려오고 코포를 잊은 채 잠에 들어버렸다.
최근 1일 1커밋을 하고 있는데 코포를 안 하니 백준의 쉬운 문제들로만 1일 1 커밋을 하고 있는 나를 발견할 수 있었고, 점점 머리가 굳어가는 느낌이 들어 오랜만에 코포 문제를 풀어봤다. 오랜만에 푸니 문제가 안 읽히는 거 같기도 하고...