A. Marin and Photoshoot
Problem
https://codeforces.com/contest/1658/problem/A
Problem - A - Codeforces
codeforces.com
오늘 Marin은 코스프레 전시회에 와서 단체 사진 촬영을 준비 중이다.
단체 사진에서 코스플레이어들은 수평으로 줄을 선다. 만약 최소 2명의 코스플레이어로 이루어진 모든 연속된 세그먼트에서 남성의 수가 여성의 수를 넘지 않는다면, 단체 사진은 아름다운 것으로 간주된다.
현재, 줄에는 n명의 코스플레이어들이 있으며, 2진 문자열로 표현할 수 있다. i번째 코스플레이어는 $s_i=0$ 이면 남성, $s_i=1$ 이면 여성이다. 줄을 아름답게 하기 위해 당신은 어느 위치든 몇 명의 추가 코스플레이어들을(0명도 가능하다) 초대할 수 있다. 줄에 있던 어떠한 코스플레이어도 제거할 순 없다.
Marin은 단체 사진이 아름다울 수 있도록 초대해야 하는 최소 코스플레이어 수를 알고 싶어 한다. 그녀는 그녀 스스로 이를 할 수 없어 당신에게 도움을 요청하였다.
Input
첫째 줄에는 테스트 케이스 수를 나타내는 하나의 정수 t($1 \le t \le 10^3$)가 주어진다.
각 테스트 케이스의 첫째 줄에는 처음 줄에 있는 코스플레이어들의 수를 나타내는 양의 정수 n($1 \le n \le 100$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 길이가 n인 2진 문자열 s가 주어지며, 이는 기존에 줄에 있는 코스플레이어들을 나타낸다. 문자열의 각 문자는 남성을 의미하는 0 혹은 여성을 의미하는 1 중 하나이다.
n의 총합에 대한 제한은 없다.
Output
각 테스트 케이스에 대하여, 단체 사진이 아름답기 위해 추가해야 하는 최소 코스플레이어 수를 출력하여라.
Example
| input | output |
| 9 3 000 3 001 3 010 3 011 3 100 3 101 3 110 3 111 19 1010110000100000101 |
4 2 1 0 2 0 0 0 17 |
Note
첫 번째 테스트 케이스에서, 각각의 인접한 코스플레이어들 사이에 2명의 여성 코스플레이어들을 초대할 수 있다. 000 → 0110110.
세 번째 테스트 케이스에서, 2번째 코스플레이어 뒤에 여성 코스플레이어를 초대할 수 있다. 010 → 0110.
Tutorial
길이가 2 이상인 모든 세그먼트에 대하여 1의 개수가 0의 개수보다 많거나 같아야 된다. 이런 문제의 경우 길이가 제일 작은 세그먼트부터 생각해보면 쉽게 풀 수 있다.
우선 길이가 2인 모든 세그먼트에 대하여 1의 개수가 0의 개수보다 많거나 같으려면 0이 연속으로 나오면 안 된다는 것을 알 수 있다. 다음으로 길이가 3인 모든 세그먼트에 대해 생각해 보면, 앞서 0이 연속해서 나올 수 없기 때문에 단체 사진이 아름답지 않은 경우는 010 이 포함된 경우로 유일하며, 이 경우를 제거하기 위해서는 0과 0 사이에 최소 2개 이상의 1이 있어야 한다는 것을 알 수 있다. 0과 0 사이에 2개 이상의 1이 포함될 경우 4 이상의 길이에 대해서는 자연스럽게 1의 개수가 0의 개수보다 많거나 같아지게 된다.
위의 내용을 바탕으로 답을 구하는 과정은 아래와 같다.
- $\forall i \ge 2$ if $s_i$ = 0, then
- if $s_{i-1}$ = 0, then 여성 코스플레이어 2명 추가
- else if $s_{i-2}$ = 0, then 여성 코스플레이어 1명 추가
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t, n, i, ans;
string s;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
cin >> s;
ans = 0;
if(s[1] == '0' && s[0] == '0') ans = 2;
for(i=2; i<n; i++){
if(s[i] == '1') continue;
if(s[i-1] == '0') ans += 2;
else if(s[i-2] == '0') ans ++;
}
cout << ans << '\n';
}
return 0;
}
B. Marin and Anti-coprime Permutation
Problem
https://codeforces.com/contest/1658/problem/B
Problem - B - Codeforces
codeforces.com
Marin은 아름다운 순열의 개수를 세기를 원한다. 길이가 n인 순열이 다음의 성질을 가지면 아름다운 순열이라고 한다:
$gcd(1 \cdot p_1, 2 \cdot p_2, ..., n \cdot p_n) > 1,$
순열은 1부터 n까지 n개의 서로 다른 수들이 임의의 순서로 이루어진 수열이다. 예를 들어, [2, 3, 1, 5, 4]는 순열이지만, [1, 2, 2]는 순열이 아니고(2가 2번 나타났다), [1, 3, 4] 또한 순열이 아니다(n=3이지만 4가 있다).
Input
첫 번째 줄에는 테스트 케이스 개수를 나타내는 하나의 정수 t($1 \le t \le 10^3$) 가 주어진다.
각 테스트 케이스는 하나의 정수 n($1 \le n \le 10^3$) 을 포함하는 하나의 줄로 이루어져 있다.
Output
각 테스트 케이스에 대하여, 아름다운 순열의 개수를 나타내는 하나의 정수를 출력하여라. 답이 매우 클 수 있기 때문에, 답을 998 244 353으로 나눈 나머지를 출력하여라.
Example
| input | output |
| 7 1 2 3 4 5 6 1000 |
0 1 0 4 0 36 665702330 |
Note
첫 번째 테스트 케이스에서, 우리는 오직 하나의 순열 [1] 밖에 가질 수 없지만 $gcd(1 \cdot 1) = 1$ 이기 때문에 이는 아름답지 않다.
두 번째 테스트 케이스에서, $gcd(1 \cdot 2, 2 \cdot 1) = 2$ 이기 때문에 우리는 오직 하나의 아름다운 순열 [2, 1]을 가질 수 있다.
Tutorial
이번 문제는 n이 작고 n의 총합에 대한 제한이 없어 $O(N^2)$으로 전처리 후 답을 출력하는 문제인 줄 알았으며, 처음 DP로 접근해 시간을 많이 허비하였다 ㅜㅜ. DP로 한참을 헤매다 gcd 값을 기준으로 순열을 세는 방법으로 문제를 접근하였고, 풀이를 알아낼 수 있었다. 매우 무식한 방법으로 보이겠지만 gcd값이 2인 순열, 3인 순열, 4인 순열의 조건을 살펴보는 것으로 문제를 접근하기 시작했다.
목표는 1부터 n까지의 수들에 적절하게 1부터 n까지의 수들을 하나씩 곱하여 gcd 값이 x의 배수가 되도록 만드는 것이다. gcd 값을 2의 배수로 만들기 위한 조건은 무엇일까? 바로 모든 값들이 2의 배수여야 한다. 1부터 n까지의 수에는 2의 배수가 $\lfloor {n \over 2} \rfloor$개 있다. 2의 배수가 아닌 홀수들은 짝수들과 곱해져 2의 배수가 되어야 한다. 그러나 n이 홀수라면 1부터 n까지의 수에서 홀수의 개수가 짝수의 개수보다 많아 모든 홀수들에 짝수를 곱할 수 없게 된다. n이 짝수인 경우에는 홀수와 짝수를 곱하는 모든 순열이 답이 된다. gcd 값이 3의 배수이기 위한 조건은 무엇일까? 1부터 n까지의 수에는 3의 배수가 $\lfloor {n \over 3} \rfloor$개가 있다. 즉, $\lfloor {n \over 3} \rfloor$개의 수들은 어떤 수를 곱하는 3의 배수가 되지만 그 이외의 수들은 3의 배수와 곱해져야 3의 배수가 된다. 그러나 아쉽게도 1부터 n까지의 수들에는 3의 배수인 수들이 3의 배수가 아닌 수들보다 적다. 따라서 gcd가 3의 배수가 되도록 순열을 만들 수 없는 것이다. 이는 나머지 수들에서도 동일하며, 즉, 우리는 gcd를 최대 2까지 밖에 만들어내지 못한다.
그렇다면 앞서 말한 대로 n이 홀수이면 gcd를 2 이상으로 만드는 방법은 존재하지 않으며, n이 짝수인 경우 홀수와 짝수를 짝짓는 모든 순열이 가능하게 된다. 이러한 경우의 수는 모든 홀수에 짝수를 짝짓는 경우의 수가 ${n \over 2}!$, 모든 홀수에 짝수를 짝짓는 경우의 수가 ${n \over 2}!$로 최종 경우의 수는 $({n \over 2}!)^2$ 가 된다.
요약하면 아래와 같다.
- if n = 짝수, then $({n \over 2}!)^2$
- if n = 홀수, then 0
Solution
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
int main()
{
int t, n, i;
long long ans;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
if(n%2 == 1) cout << "0\n";
else{
ans = 1;
for(i=1; i<=n/2; i++) ans = (ans*i)%MOD;
cout << (ans*ans)%MOD << '\n';
}
}
return 0;
}
C. Shinju and the Lost Permutation
Problem
https://codeforces.com/contest/1658/problem/C
Problem - C - Codeforces
codeforces.com
Sinju는 순열을 매우 좋아한다! 오늘 Juju에게 순열을 가지고 놀기 위해 순열 p를 빌렸다.
순열 p의 i-th cyclic shift는 $p = [p_1, p_2, ..., p_n]$가 $p = [p_{n-i+1}, ..., p_n, p_1, p_2, ..., p_{n-i}]$로 바뀌는 순열 변환이다.
순열 p의 power를 순열의 prefix maximums array b에 있는 서로 다른 원소의 개수로 정의하자. prefix maximums array b는 $b_i = max(p_1, p_2, ..., p_i)$인 길이가 n인 배열이다. 예를 들어 [1, 2, 5, 4, 6, 3]의 power는 4이다. b = [1, 2, 5, 5, 6, 6]이며, b의 서로 다른 원소의 개수는 4개이기 때문이다.
불행히도, Shinju는 순열 p를 잃어버렸다! 그녀가 기억하고 있는 정보는 오직 $c_i$가 순열 p의 (i-1)-th cyclic shift의 power를 나타내는 배열 c이다. 또한 그녀는 그녀가 올바르게 기억하고 있는지 확신할 수 없어, 자신의 기억이 충분한지를 알고 싶어 한다.
배열 c가 주어졌을 때, c와 일치하는 순열 p가 존재하는지 판단하여라. 순열 p를 알아낼 필요는 없다.
순열은 임의의 순서로 1부터 n까지 서로 다른 n개의 수들을 가지고 있는 배열이다. 예를 들어, [2, 3, 1, 5, 4]는 순열이지만, [1, 2, 2]는 순열이 아니고(2가 2번 나타났다), [1, 3, 4]도 순열이 아니다(n=3이지만 4가 있다).
Input
입력은 여러 개의 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스를 나타내는 하나의 정수 t($1 \le t \le 5 \cdot 10^3$) 이 주어진다.
각 테스트 케이스의 첫째 줄에는 정수 n($1 \le n \le 10^5$) 이 주어진다.
각 테스트 케이스의 둘째 줄에는 n개의 정수 $c_1, c_2, ..., c_n (1 \le c_i \le n)$이 주어진다.
모든 테스트 케이스에 대하여 n의 합이 $10^5$을 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여, 배열 c를 만족하는 순열 p가 존재한다면 "YES"를 그렇지 않으면 "NO"를 출력하여라.
Example
| input | output |
| 6 1 1 2 1 2 2 2 2 6 1 2 4 6 3 5 6 2 3 1 2 3 4 3 3 2 1 |
YES YES NO NO YES NO |
Note
첫 번째 테스트 케이스에서, 순열 [1]이 배열 c를 만족한다.
두 번째 테스트 케이스에서, 순열 [2, 1]이 배열 c를 만족한다.
다섯 번째 테스트 케이스에서, 순열 [5, 1, 2, 4, 6, 3]이 배열 c를 만족한다. 왜 이것이 맞는지 보자.
- p의 0번째 cyclic shift은 [5, 1, 2, 4, 6, 3]이다. b = [5, 5, 5, 5, 6, 6]이고 5와 6, 2개의 서로 다른 원소가 있으므로, 이것의 power는 2이다.
- p의 첫 번째 cyclic shift는 [3, 5, 1, 2, 4, 6]이다. b = [3, 5, 5, 5, 5, 6]이며 power는 3이다.
- p의 두 번째 cyclic shift는 [6, 3, 5, 1, 2, 4]이다. b = [6, 6, 6, 6, 6, 6]이며 power는 1이다.
- p의 세 번째 cyclic shift는 [4, 6, 3, 5, 1, 2]이다. b = [4, 6, 6, 6, 6, 6]이며 power는 2이다.
- p의 네 번째 cyclic shift는 [2, 4, 6, 3, 5, 1]이다. b = [2, 4, 6, 6, 6, 6]이며 power는 3이다.
- p의 다섯 번째 cyclic shift는 [1, 2, 4, 6, 3, 5]이다. b = [1, 2, 4, 6, 6, 6]이며 power는 4이다.
그러므로, c는 [2, 3, 1, 2, 3, 4]이다.
세 번째, 네 번째, 여섯 번째 테스트 케이스에서는 배열 c를 만족하는 순열이 없음을 알 수 있다.
Tutorial
문제에서는 순열을 복원할 필요는 없다고 했지만, 복원할 수 있으면 순열 p가 존재하는지 알 수 있을 것이다. 따라서 순열 p를 복원하는 것을 1차 목표로 하였고, p를 복원하는 방법을 생각하는 과정에서 풀이를 알아낼 수 있었다.
우선 순열이기 때문에 가장 큰 n이 있을 것이고, 이 n이 맨 앞으로 오도록 하는 cyclic shift에서 power가 1이 될 것이며, 그렇지 않은 경우 power는 1보다 큰 값이 될 것이다. 즉, 배열 c에 1일 정확히 1개 존재해야 한다.
$c_i$가 1이면 (i-1)-th cyclic shift 시 n이 가장 앞에 온다는 것을 의미한다($p_{n-(i-1)}$은 n이 된다). 아는 $c_i$가 1인 i를 기준으로 살펴보았다. 그다음 cyclic shift에서는 새로운 수 x가 앞에 등장하고 2번째 수는 n일 것이다. 이 경우 b는 [x, n, n, ..., n] 일 것이며, $c_(i+1)=2$가 될 것이다. 그다음인 (i+1)-th cyclic shift에서는 또 새로운 수 y가 앞에 등장할 것이다. 이때, y가 x보다 크다면 b는 [y, y, n, n, ..., n]이 될 것이며, y가 x보다 작다면 b는 [y, x, n, n, ..., n]이 될 것이며, power는 1 증가하거나 작아질 것이다. 다음 cyclic shift를 생각해보더라도 항상 power는 1 증가하거나 작아지게 된다. 즉, $c_i$가 1인 i를 기준으로 배열 c를 순환할 때, 값이 작아지거나 정확히 1이 커지는 경우에만 순열 p가 존재하는 것을 알 수 있다.
Solution
#include <bits/stdc++.h>
using namespace std;
int c[100010];
int main()
{
int t, n, i, idx1, j, j_;
bool flag;
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> t;
while(t--){
cin >> n;
idx1 = -1;
for(i=0; i<n; i++){
cin >> c[i];
if(c[i] == 1) idx1 = i;
}
if(idx1 == -1){
cout << "NO\n";
continue;
}
flag = true;
for(i=1; i<n; i++){
j = (idx1+i)%n;
j_ = (j-1+n)%n;
if(c[j] == 1) flag = false;
if(c[j] > c[j_] && c[j] != c[j_]+1) flag = false;
}
if(flag) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
D. 388535
Problem
https://codeforces.com/contest/1658/problem/D1
Problem - D1 - Codeforces
codeforces.com
https://codeforces.com/contest/1658/problem/D2
Problem - D2 - 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
대회 당시 해당 문제는 풀지 못하였으며, 아래는 정해가 아닌 풀이이다. 풀이는 이 글(2022.03.29 - [Algorithm/Codeforces] - [Codeforces] 1658D - 388535)에서 확인할 수 있다.
이 문제는 보자마자 처음부터 끝까지 계산을 통해서 풀어내야겠다는 생각이 머릿속에서 떠나질 않았다.
XOR 연산 특성상 똑같은 수를 짝수번 XOR 연산하면 연산이 무의미해지며, 교환 법칙이 성립한다. 이를 이용하며 주어진 배열 a의 모든 원소를 XOR 시키게 되면 $a_1 \oplus a_2 \oplus ... \oplus a_n \oplus [x]$ 가 된다. 마지막에 [x]로 표현한 이유는 x가 있을 수도 있고 없을 수도 있다는 뜻이다. 정확히는 원소의 개수가 짝수이면 x가 없고 홀수이면 x가 있다는 뜻이다. 내가 포기하지 못하 부분이 바로 이 부분이었다. 홀수인 경우....
앞서 말한 특성으로 똑같은 수를 한번 더 XOR 시키면 그 값이 사라지기 때문에 원소의 개수가 홀수개인 경우 a의 모든 원소를 XOR 시키고 여기에 [l, l+1, ..., r] 배열의 원소들을 XOR 시키면 x가 바로 튀어나오게 된다. 짝수의 경우도 약간의 트릭을 준다면 이와 같은 방법으로 가능할 것이라고 생각하여 헤매다가 결국 풀어내지 못하였다 ㅜㅜ
마치며...
이번 대회는 모든 문제가 순조롭지 않았다. A번 문제도 풀이가 바로 떠오르지 않았으며, B번 문제는 n이 작아 $O(N^2)$으로 전처리를 한 후 푸는 문제라고 생각한 동시에 DP일 것이라고 생각하여 풀이를 떠올리는데 많은 시간을 허비했다. 오히려 이번 문제는 C번 풀이를 가장 빨리 떠올렸다. D번 문제는 암호 해독을 공부해서인지 연산을 통해 x를 알아낼 수 있다는 생각에 사로 잡혀 더 발전된 풀이를 생각해내지 못하였다.
최근 대회에서 술을 마시고 치를 때를 제외하고는 레이팅이 꾸준히 올라 퍼플을 갈 수 있을 것이라는 기대감과 함께 PS에 흥미를 붙이고 있었다. 그러나 저번 대회와 이번 대회에서 D를 풀어내는데 실패하면서 레이팅이 떨어지는 것을 보니 아쉬움과 함께 아직 퍼플 이상의 레이팅을 가진 사람들의 대단함을 다시 한번 느낄 수 있었다. 최근 대회에 온전히 집중할 수 없는 상태이기는 했으나 D번의 풀이를 끝내 생각해내지 못하는 것에서 부족함을 많이 느꼈고, 대회 이후에도 풀지 못한 문제들의 풀이를 보면서 공부해야겠다는 생각이 들었다.
'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] 1658D - 388535 (0) | 2022.03.29 |
