Codeforces Round #829 (Div. 2)
A. Technical Support
Problem
Problem - A - Codeforces
codeforces.com
당신은 큰 회사의 기술 지원의 품질 관리 부서에서 일하고 있다. 당신의 일은 모든 고객 문제가 해결되었는지 확인하는 것이다.
오늘 당신은 고객과 기술 지원 관리자 사이의 대화 내용을 확인해야 한다. 업무 규칙에 따라, 각 고객의 메시지는 지원 관리자의 대답에 해당하는 하나 혹은 여러 개의 메시지가 따라 나와야 한다. 그러나 가끔 고객들은 너무 빨리 질문을 해서 이전 질문들에 대한 몇몇 관리자의 답변들은 고객들이 요청한 새로운 질문 뒤에 나타나기도 한다.
보안 정책에 때문에, 메시지의 전체 내용은 당신에게 보여주지 않고, 오로지 메시지 타입과 순서만 보인다. 메시지의 타입은 고객의 질문 혹은 기술 지원 관리자의 응답으로 이루어져 있다. 대화 기록은 고객의 질문으로 시작된다는 것이 보장된다.
당신은 이 대화 기록이 위에서 서술한 업무 규칙에 부합하는지 규칙을 위반하는지 판단해야 한다.
Input
각 테스트는 여러 개의 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스를 나타내는 하나의 정수 t($1 \leq t \leq 500$) 가 주어진다.
각 테스트 케이스의 첫째 줄에는 대화 기록에서 메시지의 총 개수를 의미하는 하나의 정수 n($1 \leq n \leq 100$) 이 주어진다.
각 테스트 케이스의 둘째 줄에는 "Q"와 "A'로 이루어진 n개의 문자들이 주어진다. 각 문자는 대화 기록에서 발생 순서에 따라 메시지의 종류를 나타낸다. 문자 "Q"는 고객의 질문을 의미하는 메시지이며, 문자 "A"는 기술 지원 관리자의 답변을 의미하는 메시지이다. 첫 번째 문자는 "Q"임이 보장된다.
Output
각 테스트 케이스에 대하여 만약 대화 기록이 업무 규칙을 만족한다면 "Yes"(큰 따옴표 없이)를 출력하고, 그렇지 않으면 "No"(큰 따옴표 없이)를 출력하여라.
Example
| input | output |
| 5 4 QQAA 4 QQAQ 3 QAA 1 Q 14 QAQQAQAAQQQAAA |
Yes No Yes No Yes |
Note
첫번째 테스트 케이스에서는 고객의 두 질문에 대하여 두 전문가의 답변이 따라 나온다. 따라서 이 대화 기록은 업무 규칙을 만족한다.
두번째 테스트 케이스에서는 처음 두 질문 중 하나가 답변을 받지 못하였다.
세번째 테스트 케이스에서는 기술 지원 관리자가 한 질문에 대한 답변으로 두 개의 메시지를 보냈다.
Tutorial
"one or several"을 굵은 글씨로 강조를 해줬음에도 불구하고 처음에 문제를 대충 읽어 하나의 질문에 하나의 답변이 왔는지 판단하는 문제로 오인해버렸다 ㅜㅜ
하나의 질문에 대해 여러개의 답변이 올 수는 있지만 하나의 질문에 대해 답변이 오지 않으면 안 된다. 또한 여러 질문이 온 후, 답변이 나와도 되기 때문에 우리는 최대한 모든 답변들이 답변하지 않은 질문들 중 가장 처음에 해당하는 답변이라 가정을 하고, 해당 질문에 대한 답변은 완료됐다고 생각하면 문제를 쉽게 풀 수 있다.
변수 하나를 만들어 매 순간 답변하지 않은 질문들의 개수로 정의해준다. 그러면 "Q" 문자가 들어오면 1이 증가할 것이고, "A" 문자가 들어오면 1이 감소할 것이다. 그러나 답변하지 않은 질문의 개수이기 때문에 음수가 될 수는 없다. 따라서 매순간 메시지를 처리하다가 답변의 개수가 더 많아 변수가 음수가 되더라도 0 밑으로 떨어뜨리지는 않는다.
모든 대화를 살펴본 이후 해당 변수가 0으로 모든 질문에 답변을 했다면 "Yes"를, 그렇지 않으면 "No"를 출력해주면 된다.
Solution
#include <iostream>
#include <string>
using namespace std;
int main()
{
int t, n, i, q;
string str;
cin >> t;
while(t--){
cin >> n;
cin >> str;
q = 0;
for(i=0; i<str.size(); i++){
if(str[i] == 'Q') q++;
if(str[i] == 'A') q--;
if(q < 0) q = 0;
}
if(q == 0) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
B. Kevin and Permutation
Problem
Problem - B - Codeforces
codeforces.com
Kevin의 생일을 맞아 그는 1, 2, 3, ..., n 번호가 붙은 선물들을 받았다.
그는 이 숫자들을 연속된 두 수의 차에 대한 절댓값의 최솟값이 최대가 되도록 재배열하고자 한다. 더 공식화해보면, 그가 숫자의 순서를 $p_1, p_2, ..., p_n$으로 배열했다면, 그는 다음의 값을 최대화하기를 원한다.
$\underset{i=1}{\overset{n-1}{min}}|p_{i+1} - p_i|$,
|x|는 x의 절댓값을 의미한다.
Kevin을 도와주자.
Input
각 테스트는 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \leq t \leq 100$) 이 주어진다.
각 테스트 케이스는 선물들의 개수를 나타내는 하나의 정수 n($2 \leq n \leq 1000$)을 포함하는 하나의 줄로 이루어져 있다.
Output
각 테스트 케이스에 대하여 연속한 원소의 차의 최솟값이 최대가 되도록 배열한 서로 다른 n개의 정수 $p_1, p_2, ..., p_n ( 1 \leq p_i \leq n)$을 포함하는 하나의 줄을 출력하여라.
공식화해보면, $\underset{i=1}{\overset{n-1}{min}}|p_{i+1} - p_i|$ 의 값이 최대가 되는 순열 p를 출력해야 한다.
만약 최적의 답이 여러개라면, 아무거나 출력하여라.
Example
| input | output |
| 2 4 3 |
2 4 1 3 1 2 3 |
Note
첫번째 테스트 케이스에서 연속한 두 원소의 차의 최솟값은 min{|4-2|, |1-4|, |3-1|} = min{2, 3, 2} = 2이다. 이 답이 최적이라는 것은 쉽게 증명할 수 있다.
두번째 테스트 케이스에서 1, 2, 3으로 이루어진 순열은 최적의 답이다. 연속한 원소의 차의 최솟값은 1이다.
Tutorial
아마 이 문제를 보면 대충 n/2 정도씩 떨어뜨려서 배열하면 되는 쉬운 문제라는 생각이 들 것이다. 그러나 아무 생각 없이 1부터 배열하고자 하면 n=4와 같이 짝수인 경우 최적의 답을 찾기 어려울 수 있다.
대충 n/2 정도씩 떨어뜨려야겠다는 것을 생각해 냈다면, 이후 문제의 핵심은 중간값부터 시작해야 한다는 것이다. $\lfloor {n+1 \over 2} \rfloor$부터 시작해서 $\lfloor {n \over 2} \rfloor$을 더하고 $\lfloor {n \over 2} \rfloor + 1$을 빼는 것을 반복하면 문제를 쉽게 풀 수 있다.
Solution
#include <iostream>
using namespace std;
int ans[1010];
int main()
{
int t, n, i, j;
cin >> t;
while(t--){
cin >> n;
j = (n+1)/2;
for(i=0; i<n; i++){
ans[i] = j;
if(j <= (n+1)/2) j += n/2;
else j -= n/2+1;
}
for(i=0; i<n; i++) cout << ans[i] << ' ';
cout << '\n';
}
return 0;
}
C. Make Nonzero Sum
Problem
C1. Make Nonzero Sum (easy version)
C2. Make Nonzero Sum (hard version)
이 문제는 쉬운 버전과 어려운 버전으로 나뉜다. 쉬운 버전에서는 배열에 0이 포함되어 있지 않으며, 어려운 버전에서는 배열에 0이 포함될 수 있다.
-1, 0, 1을 포함하는 배열 $[a_1, a_2, ..., a_n]$이 주어진다. 당신은 이 배열을 다음 규칙에 맞게 $[l_1, r_1], [l_2, r_2], ..., [l_k, r_k]$ 세그먼트로 나누어야 한다.
- i번째 세그먼트의 교차 합 $s_i$는 다음과 같이 정의된다: $s_i = a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} ... \plusminus a_{r_i}$. 예를 들어 배열 [1, 0, -1, 1, 1] 배열에서 세그먼트 [2, 4]의 교차 합은 0 - (-1) + 1 = 2이다.
- 모든 세그먼트의 $s_i$의 합은 0이 되어야 한다.
각 $s_i$는 0이 될 필요는 없고, 모든 세그먼트의 $s_i$ 합만 0이 되면 된다.
세그먼트 $[l_1, r_1], [l_2, r_2], ..., [l_k, r_k]$는 $1 = ㅣ_1 \leq r_1, l_2 \leq r_2, ..., l_k \leq r_k = n$과 모든 $i = 1, 2, ..., k-1$에 대하여 $r_i+1 = l_{i+1}$을 만족시켜야 한다. 다시 말해 배열의 모든 원소들은 정확히 하나의 세그먼트에 들어가야 한다.
당신은 주어진 배열을 위에서 말한 규칙에 맞게 세그먼트를 나누거나 나눌 수 없다고 판단해야 한다.
세그먼트의 개수를 최소화 할 필요는 없다.
Input
각 테스트는 여러개의 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 개수를 나타내는 하나의 정수 t($1 \leq t \leq 10000)가 주어진다.
각 테스트 케이스의 첫째 줄에는 배열 a의 길이를 나타내는 하나의 정수 n($1 \leq n \leq 200000$)이 주어진다.
각 테스스 케이스의 둘째 줄에는 배열의 원소를 나타내는 n개의 정수 $a_1, a_2, ..., a_n$($a_i$는 -1, 0 혹은 1이다)이 주어진다.
모든 테스트 케이스에 대하여 n의 총합은 200000을 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여 세그먼트의 개수에 해당하는 하나의 정수 k를 출력하여라. 만약 세그먼트를 만들 수 없다면, -1을 출력하여라.
세그먼트를 만들 수 있다면, 다음 k개의 줄의 i번째 줄에 i번째 세그먼트를 나타내는 $l_i$와 $r_i$를 출력하여라. 다음 조건들을 항상 만족해야 한다:
- 1부터 k까지 각 i들에 대하여 $l_i \leq r_i$.
- 1부터 (k-1)까지 각 i들에 대하여 $l_{i+1} = r_i + 1$.
- $l_1 = 1, r_k = n$.
만약 만족하는 답이 여러개라면 아무거나 출력하여라.
Example
| input | output |
| 5 4 0 0 0 0 7 -1 1 0 1 0 1 0 5 0 -1 1 0 1 3 1 0 1 1 1 |
4 1 1 2 2 3 3 4 4 4 1 1 2 2 3 5 6 7 -1 2 1 1 2 3 -1 |
Note
첫번째 테스트 케이스에서 각각이 0 하나만 원소로 가지도록 4개의 세그먼트로 나눌 수 있다. 그러면 합은 0 + 0 + 0 + 0 = 0이다.
두 번째 테스트 케이스에서 4개의 세그먼트로 나눌 수 있다. 첫번째 세그먼트의 교차합은 -1, 두번째 세그먼트의 교차합은 1, 세 번째 세그먼트의 교차합은 0 - 1 + 0 = -1, 네번째 세그번트의 교차합은 1 - 0 = 1이다. 교차합들의 합은 -1 + 1 - 1 + 1 = 0이다.
세번째 테스트 케이스에서 만족하는 세그먼트는 존재하지 않는다는 것을 알 수 있다.
Tutorial
나는 쉬운 버전에서 아이디어를 떠올린 후, 어려운 버전에서 풀이를 확장시켰다. 어려운 버전으로 풀이를 확장시키는데 시간이 많이 오래 걸리지 않았기에 어려운 버전에 대한 코드 작성 후, 쉬운 버전과 어려운 버전에 모두 제출하였다.
우선 불가능한 경우에 대해 생각해보자. 결국 각 원소들은 그대로 더해지거나 '-1'이 곱해져서 더해진다. 음수인 상태로 더해지는 경우는 뺀다고 생각해 줄 수 있으며 '-1'을 곱하더라도 홀짝 성은 바뀌지 않는다. 즉, 처음부터 1과 -1의 개수가 홀수개라면 불가능하다는 것이다. 때문에 가장 먼저 입력을 받으면서 원소의 총합이 홀수인지 짝수인지 판별해준다.
가능한 경우라고 판단이 된다면 이제 적절히 세그먼트를 나눠줘야 한다. 이때 문제에서 세그먼트의 개수가 최소일 필요는 없다고 했으므로 최대한 0을 만들어버리면 편할 것이라는 생각을 하였다. 쉬운 버전에서는 0이 나타나지 않는다고 했으며, 앞서 가능한 경우는 1과 -1의 개수가 짝수개라고 했으므로, 원소들을 2개씩 짝지어 줄 수 있다. 짝지어진 원소는 두 원소가 같은 경우와 다른 경우로 나누어줄 수 있다. 같은 경우라면 이 둘을 하나의 세그먼트로 둘 경우, 뒤에 있는 원소의 부호가 바뀌어 교차합이 0이 될 것이며, 두 원소가 다른 경우는 이 둘을 따로 세그먼트로 만들어주면 교차합은 각 원소가 되고, 이 둘의 교차합을 더하면 0이 된다. 즉, 모든 쌍들은 교차합 혹은 교차 합의 합을 0으로 만들 수 있다는 것이다.
바로 어려운 버전으로 풀이를 확장시켜보자. 가능한 경우라고 판단을 했다면 결국 1과 -1들을 2개씩 짝지어 줄 수 있을 것이다. 0이 짝지어진 두 원소 사이에 있는 경우에는 살짝 복잡해지지만 그 밖에 있는 경우는 0 자체를 하나의 세그먼트로 둘 수 있다. 예를 들어 배열 [1, -1, 0, 1, 0, -1]에서 첫 번째 원소와 두 번째 원소, 4번째 원소와 6번째 원소가 짝지어질 것이다. 3번째 원소의 0은 짝지어진 원소들 사이에 있지 않기 바로 하나의 세그먼트로 만들어 줄 수 있으나, 5번째 원소의 0은 4번째 원소와 6번째 원소 사이에 있기 때문에 바로 하나의 세그먼트로 분리해줄 수 없다.
0이 들어갔다고 겁먹을 필요는 없다. 짝지어진 두 원소 사이에 있는 0을 뒤에 있는 원소와 같은 세그먼트로 놓는다고 하면 0의 개수만큼 뒤에 있는 원소의 부호가 바뀌는 것과 같은 효과가 있다는 것을 알 수 있다. 이를 이용하면 결국 쉬운 버전과 같은 문제가 된다. 짝지어진 두 원소의 위치를 s와 e라고 한다면, 이 두 원소를 같은 세그먼트에 넣어야겠다고 판단이 된다면 [s, e] 세그먼트로, 그렇지 않으면 [s, s]와 [s+1, e] 세그먼트로 나누어주면 된다.
Solution
#include <iostream>
#include <queue>
using namespace std;
int a[200010];
queue<int> que;
int main()
{
int t, n, i, sum, s, e, cnt;
bool flag;
cin >> t;
while(t--){
cin >> n;
sum = 0;
for(i=1; i<=n; i++){
cin >> a[i];
sum += a[i];
}
if(abs(sum)%2 == 1){
cout << "-1\n";
continue;
}
cnt = 0;
flag = false;
for(i=1; i<=n; i++){
if(!flag){
if(a[i] == 0){
cnt++;
que.push(i);
que.push(i);
}
else{
s = i;
flag = true;
}
}
else{
if(a[i] == 0) continue;
else{
e = i;
flag = false;
if(((e-s)%2 == 1) ^ (a[s] != a[e])){
cnt++;
que.push(s);
que.push(e);
}
else{
cnt+=2;
que.push(s);
que.push(s);
que.push(s+1);
que.push(e);
}
}
}
}
cout << cnt << '\n';
while(!que.empty()){
cout << que.front() << ' ';
que.pop();
cout << que.front() << '\n';
que.pop();
}
}
return 0;
}
D. Factorial Divisibility
Problem
하나의 정수 x와 하나의 정수 배열 $a_1, a_2, ..., a_n$이 주어진다. $a_1! + a_2! + ... + a_n!$이 $x!$로 나누어지는지 판단하여라.
$k!$은 k이하의 모든 양의 정수의 곱을 나타내는 k 팩토리얼을 의미한다. 예를 들어, $3! = 1 \cdot 2 \cdot 3 =6, 5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$이다.
Input
첫째 줄에는 두 정수 n과 x($1 \leq n \leq 500000, 1 \leq x \leq 500000$)가 주어진다.
둘째 줄에는 배열의 원소를 나타내는 n개의 정수 $a_1, a_2, ..., a_n(1 \leq a_i \leq x)가 주어진다.
Output
하나의 줄에 만약 $a_1! + a_2! + ... + a_n!$이 $x!$로 나누어진다면 "Yes"(큰따옴표 없이)를 출력하고, 그렇지 않으면 "No"(큰따옴표 없이)를 출력하여라.
Example
| input | output |
| 6 4 3 2 2 2 3 3 |
Yes |
| 8 3 3 2 2 2 2 2 1 1 |
Yes |
| 7 8 7 7 7 7 7 7 7 |
No |
| 10 5 4 3 2 1 4 3 2 4 3 4 |
No |
| 2 500000 499999 499999 |
No |
Note
첫 번째 예제에서 3! + 2! + 2! + 2! + 3! + 3! = 6 + 2 + 2 + 2 + 6 + 6 = 24. 24는 4! = 24로 나누어진다.
두 번째 예제에서 3! + 2! + 2! + 2! + 2! + 2! + 1! + 1! = 18, 이는 3! = 6으로 나누어진다.
세 번째 예제에서 7! + 7! + 7! + 7! + 7! + 7! + 7! = 7 $\cdot$ 7!. 이는 8!로 나누어지지 않음을 쉽게 알 수 있다.
Tutorial
문제를 블로그에 정리하면서 $a_i$의 조건을 처음 봤다. (ㅋㅋㅋ) 그 정도로 '$a_i \leq x$' 조건이 중요하지는 않다는 것이다.
배열의 원소 중 가장 작은 수를 m이라고 한다면 팩토리얼의 합은 m! 으로는 나누어진다는 것은 쉽게 알 수 있을 것이다. 그렇다면 우리는 우선 (m+1)!로 팩토리얼의 합이 나누어지는지 확인해야 그 이후 (m+2)!, (m+3)!, ..., x!로도 나누어지는지 알 수 있을 것이다. 그렇다면 (m+1)!로 나누어지는지는 어떻게 알 수 있을까? 배열의 원소들을 모두 m!으로 나눈 후, 원소들의 합이 (m+1)로 나뉘는지 확인하면 될 것이다. 그렇다면 이건 또 어떻게 할까? 기존의 배열은 m인 원소와 m보다 큰 원소로 나누어줄 수 있다(m이 원소들 중 가장 작은 값이라고 했으므로). 그렇다 m!로 각 원소로 나누면 1과 (m+1)의 배수들로 원소가 나뉜다. 이때 (m+1)의 배수들의 합은 이미 (m+1)의 배수이기 때문에 1들의 합이 (m+1)의 배수가 되어야 한다.
(m+1)!으로 나뉘는지 확인하는 것에 성공하였다! 그러나 (m+2)!, (m+3)!, ..., x! ... 아직 갈 길이 멀다 ㅜㅜ. 그러나 그리 어렵지 않다! (m+1)!로 나뉜다는 것을 확인했다면 우리는 m! 이 (m+1)의 배수 개 있다는 것을 안 것이다. 즉, m! 들을 (m+1) 개씩 묶어 (m+1)!으로 만들어버리면 된다. 이제 (m+1)!으로 나누어지는지 확인한 것과 같이 (m+2)!으로 나누어지는지 확인하고 이후 x! 까지 확인해주면 된다.
마치 큰 자릿수 연산할 때 배열에서 자리올림 하는 것과 비슷한 방식이다.
Solution
#include <iostream>
#include <algorithm>
using namespace std;
int cnt[500010];
int main()
{
int n, x, i, a;
bool flag;
cin >> n >> x;
for(i=0; i<n; i++){
cin >> a;
cnt[a]++;
}
for(i=1; i<x; i++){
if(cnt[i] == 0) continue;
if(cnt[i] % (i+1)) break;
cnt[i+1] += cnt[i]/(i+1);
}
if(i < x) cout << "NO";
else cout << "YES";
return 0;
}
E. Wish I Knew How to Sort
Problem
길이가 n인 이진 배열 a(배열은 모든 원소는 0 또는 1)가 주어진다. 당신은 이 배열을 정렬하기를 원한다. 그러나 불행히도 당신의 알고리즘 선생님은 정렬 알고리즘을 알려주는 것을 까먹었다. 따라서 당신은 배열 a가 정렬이 될 때까지 다음의 작업을 수행할 것이다:
- 임의로 i < j를 만족하는 두 인덱스 i와 j를 고른다. $1 \leq i < j \leq n$을 만족하는 모든 인덱스 쌍 (i, j)를 고를 확률은 동일하다.
- 만약 $a_i > a_j$라면, 두 원소 $a_i$와 $a_j$를 바꾼다.
배열이 정렬되기까지 당신이 수행해야 하는 작업 회수의 기댓값은 얼마인가?
답은 p, q가 정수이며, $q \not\equiv 0 \pmod{998244353}$를 만족하는 기약분수 $p \over q$로 표현할 수 있다. $p \cdot q^{-1} \,\bmod\, 998244353$인 하나의 정수를 출력하여라. 다시말해 $0 \leq x < 998244353$와 $x \cdot q \equiv p \pmod{998244353}$를 만족하는 정수 x를 출력하여라.
Input
각 테스트는 여러 개의 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스를 나타내는 하나의 정수 t($1 \leq t \leq 10^5$)가 주어진다.
각 테스트 케이스의 첫째 줄에는 이진 배열의 원소 개수를 나타내는 하나의 정수 n($1 \leq n \leq 200000$)이 주어진다.
각 테스트 케이스의 둘째 줄에는 배열의 원소를 나타내는 n개의 정수 $a_1, a_2, ..., a_n (a_i \in {0, 1})$이 주어진다.
모든 테스트 케이스에 대하여 n의 총합은 200000이 넘지 않음이 보장된다.
Output
각 테스트 케이스에 대하여 $p \cdot q^{-1} \,\bmod\, 998244353$의 값에 해당하는 하나의 정수를 출력하여라.
Example
| input | output |
| 3 3 0 1 0 5 0 0 1 1 1 6 1 1 1 0 0 1 |
3 0 249561107 |
Note
Tutorial
수학 문제의 끝판왕급의 문제라고 생각한다. 사실 (너무 길어 번역하진 않았지만) Note에서 너무나도 큰 힌트를 줬기 때문에 문제 자체는 어렵지 않았다. 그러나 세운 수식들을 풀어내는 과정에서 난이도가 훌쩍 뛰었다고 생각하며, 사실 수학을 다 까먹은 나는 wolfram alpha 사이트의 큰 도움과 구글링을 통해 문제를 해결했다...
한번 차근차근 풀어보자. 우선 우리는 주어진 배열에서 바꿔야 하는 원소가 몇 개인지 알아야 한다. 이는 0의 개수를 센 후, 앞에서부터 0의 개수만큼의 원소를 봤을 때, 1의 개수를 세주면 된다. 이 개수를 w라고 하면, 주어진 배열에는 w개의 1과 w개의 0이 잘못된 위치에 있다고 표현할 수 있다.
우리의 1차 목표는 잘못된 w개의 1중 하나와 잘못된 w개의 0 중 하나를 바꿔 잘못된 1과 0의 개수가 각각 w-1개가 되도록 하는 것이다. 그렇다면 우선 잘못된 1과 0의 쌍을 고를 확률부터 구해줘야 한다. n개의 수 중 2개를 순서 없이 고르는 경우의 수는 $_{n}\mathrm{C}_{2}$이며, 잘못된 1과 0의 쌍을 고르는 경우의 수는 w(잘못된 1의 개수) $\times$ w(잘못된 0의 개수)이다. 즉, 잘못된 1과 0의 쌍을 고를 확률은 ${w \times w} \over {_{n}\mathrm{C}_{2}}$ 이다. 편의를 위해 $x := _{n}\mathrm{C}_{2}, y := w \times w$ 라고 하자. 그러면 잘못된 쌍을 고를 확률은 $y \over x$, 그렇지 않은 확률은 ${x-y} \over x$이다. 우리는 결국 잘못된 쌍을 고르는 것이 목표이며, 그렇지 못한 경우 잘못된 쌍을 고를 때까지 임의의 인덱스 쌍을 골라야 한다. 이때의 기댓값은 문제의 Note에서도 알 수 있듯이, $\sum_{i=1}^{\infty} ({y \over x})^{i-1} \cdot {x-y \over x} \cdot i$이다. 그리고 이는 정리하면 아름답게도 $x \over y$가 된다. 다시말해 잘못된 1과 0의 개수가 w개씩 있다면 이를 하나씩 줄이는데 걸리는 작업 횟수의 기댓값은 ${_{n}\mathrm{C}_{2} \over w \times w}$라는 것이다.
우리는 잘못된 1과 0들을 하나씩 줄여 잘못된 1과 0들을 없애는 것이 목표다. 즉, ${_{n}\mathrm{C}_{2} \over w \times w} + {_{n}\mathrm{C}_{2} \over (w-1) \times (w-1)} + ... + {_{n}\mathrm{C}_{2} \over 1 \times 1}$를 구하는 것이 목표이며, 출력 형식인 $p \cdot q^{-1} \,\bmod\, 998244353$ 형태로 출력하고자 한다면 $_{n}\mathrm{C}_{2} \cdot (w \times w)^{-1} + _{n}\mathrm{C}_{2} \cdot ((w-1) \times (w-1))^{-1} + ... + _{n}\mathrm{C}_{2} \cdot (1 \times 1)^{-1} \,\bmod\, 998244353$을 구하면 된다.
다행히도 분수를 모듈러에서 역원을 곱하는 형태로 바꿔버리면 분수가 기약 분수가 아니라더라도 같은 값을 나타내며, 두 분수의 합을 모듈러에서 표현할 때에도 굳이 통분하여 하나의 분수로 바꿀 필요가 없다는 것이다. 그리고 더욱 다행인 것은 998244353이 소수이기 때문에 우리는 역원을 구할 때 998244353-2=998244351번 곱하여 역원을 구할 수 있다. (사실 이것도 기억이 안 나 구글링 해서 겨우 알아냈다 ㅜㅜ)
Solution
#include <iostream>
#define MAX 998244353
#define MAXN 200000
using namespace std;
int a[MAXN+10];
long long power(long long x, long long y)
{
long long ret;
if(y == 0) return 1;
ret = power(x, y/2);
ret = (ret*ret) % MAX;
if(y%2 == 1) ret = (ret * x) % MAX;
return ret;
}
int main()
{
long long t, n, cnt0, wrong, nC2, ans, i;
cin >> t;
while(t--){
cin >> n;
cnt0 = 0;
for(i=0; i<n; i++){
cin >> a[i];
cnt0 += 1-a[i];
}
wrong = 0;
for(i=0; i<cnt0; i++) wrong += a[i];
nC2 = (n*(n-1)/2) % MAX;
ans = 0;
for(i=wrong; i>0; i--){
// ans += nC2 / (i^2)
ans += (nC2 * power((i*i)%MAX, MAX-2)) % MAX;
ans %= MAX;
}
cout << ans << '\n';
}
return 0;
}
마치며...
wolfram alpha와 구글링을 좀 하긴 했지만 이번에 역대급으로 잘 봐버렸다. 너무 많아서 마지막 문제인 F는 풀이를 적지 않았지만(그리고 사실 이후에 채점해서 틀리긴 했다) F 문제도 시간이 조금만 더 있었으면 풀었을 것 같다. (아무리 생각해도 정해를 생각한 거 같다 ㅋㅋㅋㅋ)
사실 내 생각에 이번 문제가 Div. 2 치고는 많이 쉬웠던 것 같다. C 문제도 왜 굳이 easy version과 hard version으로 나눴는지도 의문이 들 정도로 어렵지 않았고, 원래는 C까지 풀면 1시간, D까지 풀면 1시간 40분쯤이었는데 이번엔 D까지 1시간이 채 걸리지 않았다. 그리고 E번도 Note에서 이미 식을 거의 알려주었기에 식을 세우는데 큰 시간이 걸리지 않아 난이도가 확 낮아 보였다. 물론 그 식을 스스로 풀었다면 또 난이도가 확 올라갔겠지만...
E를 풀면서 수학이 너무 약해졌다는 것을 깨달았다. 수식을 세웠지만 그 수식을 어떻게 풀어내야 할지 하나도 감이 잡히지 않았다. 극한을 진짜 다 까먹었다. 그리고 모듈러에서 오일러 공식도 까먹고... 더욱 수학의 필요성을 느끼게 되는 시험이었다.
그리고 이제 문제 해석은 그만 써야겠다. 내 풀이를 정리해서 올리는 게 목표였는데 문제 해석에 너무 많은 시간이 걸려 코포 대회 하나를 정리하면 하루가 훌쩍 가버리는 느낌이다 ㅜㅜ (배보다 배꼽이 더 큰 기분...)
최근에 앞선 대회들도 몇 번 치렀는데 귀찮아서 블로그로 정리하지는 않았지만 최근 코포에서 정말 좋은 문제들이 많이 나온 것 같아 재밌었다.
또 사실 이 대회 뒤에 연속으로 Div. 2 대회가 있어 그 대회도 치렀다. 그러나 이번 대회를 너무 잘 봐 무조건 레이팅이 1900을 넘길 것이라 생각했으며, 따라서 다음 대회의 결과가 무시될 것이라고 생각하고 문제가 풀리지 않자 포기해버렸다. 그러나 대회를 치르는 당시 레이팅이 1900을 넘지 않으면 레이팅에 영향을 주는 것이었으며, 때문에 이번에 잘 봐서 레이팅이 88점이나 올랐음에도 뒤의 대회에서 레이팅이 136점이나 떨어져 버렸다 ㅜㅜ