[Codeforces] Codeforces Round #781 (Div. 2)

Algorithm/Codeforces

[Codeforces] Codeforces Round #781 (Div. 2)

이유섭 2022. 4. 12. 17:50

A. GCD vs LCM

Problem

https://codeforces.com/contest/1665/problem/A

Problem - A - Codeforces

codeforces.com

양의 정수 n이 주어진다. 다음을 만족하는 4개의 양의 정수를 찾아라.

a + b + c + d = n,
gcd(a, b) = lcm(c,d)

만약 답이 여러개라면 아무거나 출력하면 도니다. 답은 항상 존재함이 보장된다.

Input

입력은 여러 테스트케이스로 이루어져 있다. 첫째 물에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 10^4$)가 주어진다. 다음으로 테스트 케이스들에 대한 정보가 나온다.

각각의 테스트 케이스는 하나의 줄에 걸쳐 a, b, c, d의 합을 나타내는 하나의 정수 n($4 \le n \le 10^9$)이 주어진다.

Output

각각의 테스트 케이스에 대하여 a+b+c+d=n과 gcd(a, b)=lcm(c,d)를 만족하는 4개의 양의 정수 a, b, c, d를 출력하여라.

Example

input	output
5 4 7 8 9 10	1 1 1 1 2 2 2 1 2 2 2 2 2 4 2 1 3 5 1 1

Note

첫번째 케이스에서, gcd(1,1) = lcm(1,1) = 1, 1+1+1+1 = 4.

두번째 케이스에서, gcd(2,2) = lcm(2,1) = 2, 2+2+2+1 = 7.

세번째 케이스에서, gcd(2,2) = lcm(2,2) = 2, 2+2+2+2 = 8.

네번째 케이스에서, gcd(2,4) = lcm(2,1) = 2, 2+4+2+1 = 9.

다섯번째 케이스에서, gcd(3,5) = lcm(1,1) = 1, 3+5+1+1 = 10.

Tutorial

결론부터 말하면 답은 n-3, 1, 1, 1이다. gcd(n-3) = lcm(1,1) = 1 이며 합은 n이기 때문이다.

바로 위의 결론이 나왔다면 좋았을텐데, gcd와 lcm을 너무 오랜만에 봐서 약간의 삽질을 했다. 우선 a, b, c, d를 다음과 같이 표기해 보았다. 또한 우리가 앞서 말한 a, b, c, d를 A, B, C, D라 표기하였다.

$g := gcd(a, b), g' := gcd(c, d)$
$A = a \cdot g$
$B = b \cdot g$
$C = c \cdot g'$
$D = d \cdot g'$
$gcd(a, b) = 1, gcd(c, d) = 1$
$g = c \cdot d \cdot g'$

전형적인 gcd와 lcm이 나왔을 때 표기 방법이다. 이제 n을 나타내보았다.

$n = A + B + C + D$
$n = a \cdot g + b \cdot g + c \cdot g' + d \cdot g'$
$n = a \cdot c \cdot d \cdot g' + b \cdot c \cdot d \cdot g' + c \cdot g' + d \cdot g'$
$n = g'(a \cdot c \cdot d + b \cdot c \cdot d + c + d)$

여기까지 적고 곰곰히 생각해보았다. 위의 식으로 모든 수를 표현하려면 어떤 조건이 필요할까. 우선 처음 든 생각은 g'이 항상 1이어도 될 것 같다였고, 다음으로는 c와 d가 1이어도 되나? 였다. 여기까지 생각이 미치자 b까지 1이어도 가능하다는 생각이 들었으며, 비로소 a = n-3, b = 1, c = 1, d = 1이 항상 답이 될 것이라는 생각을 하게 되었다.

Solution

#include <bits/stdc++.h>

using namespace std;

int main()
{
	int t, n;
	
	cin >> t;
	while(t--){
		cin >> n;
		cout << n-3 << " 1 1 1\n";
	}
	
	return 0;
}

B. Array Cloning Technique

Problem

https://codeforces.com/contest/1665/problem/B

Problem - B - Codeforces

codeforces.com

n개의 정수로 이루어진 배열 a가 주어진다. 처음에는 오로지 주어진 배열만이 있다.

다음 2가지 작업을 할 수 있다:

배열 하나를 골라 복제한다. 이 작업 후에는 해당 배열이 하나 더 생기는 것이다.
원하는 두 배열의(같은 배열이어도 된다.) 원하는 두 위치의 원소를 바꾼다.

모든 원소의 값이 같은 배열을 얻기 위해 수행해야하는 작업의 최소 횟수를 구하여라.

Input

입력은 여러 테스트 케이스를 포함한다. 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 10^4$)가 주어진다. 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫째 줄에는 배열의 길이를 의미하는 하나의 정수 n($1 \le n \le 10^5$)이 주어진다.

각 테스트 케이스의 둘째 줄에는 배열의 원소를 의미하는 n개의 정수 $a_1, a_2, ..., a_n (-10^9 \le a_i \le 10^9$)이 주어진다.

모든 테스트케이스에 대하여 n의 총합이 $10^5$을 넘지 않음이 보장된다.

Output

각 테스트 케이스에 대하여 모든 원소가 같은 배열을 만드는데 필요한 작업의 최소 횟수를 의미하는 하나의 정수를 출력하여라.

Example

input	output
6 1 1789 6 0 1 3 3 7 0 2 -1000000000 1000000000 4 4 3 2 1 5 2 5 7 6 3 7 1 1 1 1 1 1 1	0 6 2 5 7 0

Note

첫번째 테스트 케이스는 이미 배열의 모든 원소가 같다. 따라서 답은 0이다.

두번째 테스트 케이스에서는 주어진 배열을 복사한다. 그러면 2개의 배열이 생길 것이다:

[0 1 3 3 7 0]과 [0 1 3 3 7 0]

이후 모든 0이 한쪽으로 가도록 원소를 바꾼다.

[0 0 0 3 7 0]과 [1 1 3 3 7 3]

이제 첫번째 배열을 복사한다.

[0 0 0 3 7 0], [0 0 0 3 7 0], [1 1 3 3 7 3]

첫번째 배열에 있는 두개의 원소를 바꾸자.

[ 0 0 0 0 0 0], [3 7 0 3 7 0], [1 1 3 3 7 3]

우리는 6번의 작업으로 모든 원소가 같은 배열을 만들었다.

이보다 더 적은 작업으로 할 수 없음을 보일 수 있다.

Tutorial

어떠한 원소로 배열을 만드는지는 상관 없기 때문에, 주어진 수열에서 가장 많은 원소로 배열을 바꾸는 것이 유리하다. 또한 배열에 원하는 원소가 제일 많을 때 복사하는 것이 유리하기 때문에 처음 배열 복사 후, 원하는 원소를 모두 바꾸고 배열을 복사하는 것이 좋다.

위의 두 사실을 바탕으로 초기 배열에서 가장 많은 원소의 개수가 x개라면, 우리는 다음의 작업을 통해 작업 횟수를 구할 수 있다.

if x*2 < n, then
- 작업 횟수 = 작업 횟수 + 1 + x
- x = x * 2
- 다시 위로
else,
- 작업 횟수 = 작업 횟수 + n - x
- 끝

복사본을 만들면 원하는 원소의 개수가 2배로 늘어나며 복사 작업을 포함하여, 해당 원소를 모두 옮기는데는 x+1 번의 작업이 필요하기 때문이다.

Solution

#include <bits/stdc++.h>

using namespace std;

map<int,int> m;

int main()
{
	int t, n, i, a, maxi, cnt;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> n;
		for(i=0; i<n; i++){
			cin >> a;
			
			if(m.find(a) == m.end()) m[a] = 0;
			m[a]++;
		}
		
		maxi = 0;
		for(auto it: m){
			maxi = max(maxi, it.second);
		}
		
		cnt = 0;
		while(maxi < n){
			cnt++; // copy
			cnt += maxi;
			maxi *= 2;
		}
		
		cout << cnt-(maxi-n) << '\n';
		
		m.clear();
	}
	
	return 0;
}

C. Tree Infection

Problem

https://codeforces.com/contest/1665/problem/C

Problem - C - Codeforces

codeforces.com

트리는 사이클이 없는 연결된 그래프이다. 루트-트리는 루트라고 불리는 특별한 정점이 있는 트리이다. 정점 v(루트를 제외한)의 부모는 루트에서 정점 v로의 가장 짧은 경로 중, 정점 v의 이전 정점을 의미한다. 정점 v의 자식은 정점 v를 부모로 하는 모든 정점을 의미한다.

n개의 정점으로 이루어진 루트-트리가 주어진다. 1번 정점이 루트이다. 초기 모든 정점은 건강하다.

매초 너는 2가지 작업을 할 수 있다. 전파 작업 후, 감염 작업을 한다:

전파: 각각의 정점 v에 대하여, v의 자식 중 적어도 한명이 감염되었다면, v의 자식 중 최대 한명을 감염시킬 수 있다.
감염: 건강한 정점 하나를 감염시킬 수 있다.

이 작업들은 트리 전체가 감염될 때까지 반복된다. 트리 전체를 감염시키기 위해 필요한 최소 시간을 구하여라.

Input

입력은 여러 테스트 케이스로 이루어진다. 첫째 줄에는 테스트 케이스의 개수를 의미하는 하나의 정수 t($1 \le t \le 10^4$)이 주어진다. 테스트 케이스는 다음과 같이 이루어진다.

각 테스트 케이스의 첫째 줄에는 트리의 정점 개수를 의미하는 하나의 정수 n($2 \le n \le 2 \cdot 10^5$)이 주어진다.

각 테스트 케이스의 둘째 줄에는 n-1개의 정수 $p_2, p_3, ..., p_n (1 \le p_i \le n)$이 주어지며, $p_i$는 i번째 정점의 부모를 의미한다.

주어진 그래프는 트리임이 보장된다.

모든 테스트 케이스에 대하여 n의 총합이 $2 \cdot 10^5$을 넘지 않음이 보장된다.

Output

각 테스트 케이스에 대하여 트리 전체를 감염시키는데 필요한 최소 시간을 의미하는 하나의 정수를 출력하여라.

Example

input	output
5 7 1 1 1 2 2 4 5 5 5 1 4 2 1 3 3 1 6 1 1 1 1 1	4 4 2 3 4

Note

아래 그림은 첫번째 테스트 케이스의 트리를 매초 나타낸 것이다.

감염되지 않은 정점은 검은색이다. 파랑색 정점은 매초 감염 작업을 통해 감염된 정점이다. 초록색 정점은 매초 전파 작업을 통해 감염된 정점이다. 빨간색 정점은 이전에 감염된 정점이다.

전파와 감염 작업은 너가 고를 수 있음에 유의하여라.

Tutorial

감염 작업에 의한 감염은 매초 하나의 정점 밖에 감염시킬 수 없지만, 전파에 의한 감염은 경우에 따라 매초 여러 정점에 감염시킬 수 있다. 그렇다면 우리는 어떤 정점에 감염 작업을 하여야 할까? 정답은 간단하다. 자식을 가진 모든 정점에 대하여 자식들 중 하나의 정점에만 감염 작업을 하면 된다. 이후엔 전파 작업을 통해 형제 정점에 감염이 전파될 것이기 때문이다.

그렇다면 여기서 또 문제, 그럼 어떤 순서로 정점을 감염시켜야 할까? 이것도 간단하다. 자식 정점이 많은 정점의 자식부터 감염을 시켜나가면 된다.

위의 방법대로만 작업을 수행한다면, 우리는 자식이 많은 순서로대 정점을 정렬하였을 때, 각 정점의 자식들이 모두 감염이 되는데까지 걸리는 시간은 (i + (자식 정점의 수) - 1)이 될 것이다. 그리고 우리는 모든 정점이 감염되어야 하므로, 이 시간 중 최댓값을 출력하면 된다. (참고로 루트 정점을 의미하는 1번 정점은 0번 정점의 자식이라고 가정하면 코드 짜는데 유리하다.)

그러나 위의 방법대로 하면 주어진 예제의 5번째 테스트 케이스에서 오답이 나오는 것을 확인할 수 있다. 상황에 따라 자식 정점이 많은 정점의 자식 정점에는 여러번의 감염 작업을 하는게 유리할 수 있기 때문이다.

나는 여기서 문제를 너무 어렵게 생각해서 D번을 풀고 다시 C번으로 오려고 했었다. 한 정점의 자식 정점들에 여러번의 감염 작업을 하더라도 전파 작업 시 하나의 정점만이 감염되는데, 아무생각 없이 감염 작업을 한 횟수만큼 감염이 될 것이라고 생각하였기 때문이다.

그러나 자식을 가진 모든 정점에 대하여 자식 정점들을 한번씩 감염 시켰다면, 이후 아무리 많은 감염 작업을 하더라도 전파 작업에 의해 감염 시킬 수 있는 정점은 증가하지 않으며, 감염 작업에 의해 감염되는 정점이 하나 늘어날 뿐이다.

정리하면 다음과 같다. 자식 자식의 수를 내림차순으로 정렬한 배열을 c라고 하고, 자식을 가진 정점의 수를 m이라고 하면 앞서 말한 방법에 의하면 i번째 정점의 모든 자식들이 감염되는데 걸리는 시간은 $t_i = c_i + i - 1$이다. m개의 자식들에 대하여 자식들을 최소한 하나씩 감염시키는데 걸린 시간은 T = m이 될 것이다. 그러나 만약 $max(t_i) > T$라면 i번째 정점의 자식들 중 하나를 감염 작업을 통해 감염 시켜 시간을 줄여주는 것이 좋다. 즉, $max(t_i) > T$ 이면 T를 1 증가시키고, max(t_i) 값을 1 감소시켜준다. 이 작업이 완료되면 T가 답이 된다.

Solution

#include <bits/stdc++.h>

using namespace std;

int chil[200010];
priority_queue<int> que;

int main()
{
	int t, n, i, p;
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> t;
	while(t--){
		cin >> n;
		
		for(i=0; i<=n; i++) chil[i] = 0;
		
		chil[0] = 1;
		for(i=2; i<=n; i++){
			cin >> p;
			chil[p]++;
		}
		
		sort(chil, chil+n+1, greater<int>());
		
		for(i=0; i<n; i++){
			if(chil[i] == 0) break;
			que.push(chil[i]+i);
		}
		for(; i<que.top(); i++){
			que.push(que.top()-1);
			que.pop();
		}
		
		cout << i << '\n';
		
		while(!que.empty()) que.pop();
	}
	
	return 0;
}

D. GCD Guess (WA)

Problem

https://codeforces.com/contest/1665/problem/D

Problem - D - Codeforces

codeforces.com

Input

Output

Example

input	output

Note

Tutorial

문제를 해결해보기 위해 다양한 생각을 했다. 그리고 가장 먼저 발견한 것은 유클리드 호제법의 성질을 이용하여, a와 b를 잘 설정하면, x와 a의 gcd 값을 구할 수 있을 것이라는 사실이었다. 유클리드 호제법은 gcd(a, b) = gcd(a, b-a)를 만족한다(a < b 일 때). 이를 이용하여, b를 2*a로 설정한다면, gcd(x+a, x+b) = gcd(x+a, x+2a) = gcd(x+a, a) = gcd(x, a)가 된다.

그러나 여기까지 생각을 해도 도무지 문제에 접근할 수 없었다. 만약 x가 큰 소수라면 어떠한 a를 가지고 와도 그 결과는 1일 확률이 너무나도 큰데, 답이 1이면 공약수가 없다는 것만 알 수 있기 때문이다. 이와 동시에 생각한 것은 a와 x의 gcd를 구할 수 있다면, a는 최대한 많은 소인수를 가지고 있으면 유리할 것이라는 생각이었다. 또한 gcd가 아닌 나머지 값이 나오면 참 좋겠다는 생각을 하였다.

한참을 종이에 끄적이던 중, gcd(x-1, a)를 알 수 있으면 좋겠다는 생각이 들었다. 확장해서 gcd(x-k, a)를 알고 싶어졌다. 따라서 gcd(x, a)를 구한 방법을 거꿀로 올라가 봤다. gcd(x-k, a) = gcd(x+a-k, a) = gcd(x+a-k, x+2a-k). 즉, a-k와 2a-k를 d입력으로 주면, gcd(x-k, a)를 구할 수 있다. 중간에 x+a-k가 a보다 작을 수도 있다고 생각하여 -k를 +k로 바꾸어 a+k와 2a+k를 이용하기로 하였다.

여기까지 생각이 들자 이렇게 되면, a의 인수에 p가 있으면 k를 0~p-1 값을 대입하여 질문하면 적어도 한번의 답변에서 p의 배수가 나올 것이라는 생각을 하였고, 이렇게 되면 p의 배수를 답한 k에 대하여 x+k가 p의 배수가 되는 것을 알 수 있다. 즉, x를 p로 나눈 나머지를 알 수 있게 되는 것이다. 내가 앞서 바라던 내용이다!

여러 소수들에 대한 나머지를 알고 있을 때, 수를 찾는 방법은 암호수학시간에 했다. 바로 중국인의 나머지 정리를 이용하는 방법이다! 여기까지 생각이 들자, 정말로 가능한지 생각해보았다. 2부터 소수들을 곱해나갔을 때, 질문을 해야하기 때문에 그 값이 $10^9$을 넘지 않는 수가 어디까지일까 알아본 결과 23까지의 소수를 곱하면 223,092,870로 $10^9$을 넘지 않았다. 그리고 23까지의 소수이기 때문에 23번의 질문으로 우리는 223,092,870개의 숫자를 구별할 수 있다. 그렇게 알아낸 수를 N이라고 하면, 답은 N이 될 수도 있지만, N + 223,092,870가 될 수도 있고, N + 2*223,092,870가 될 수도 있었다. 그러나 5*223,092,870의 값이 $10^9$을 넘었으며, 즉, 5번의 추가 질문으로 값을 특정지을 수 있게 되는 것이다.

라고 생각하고 열심히 짜 봤지만 어디서 오류가 떴는지 결국 해결하지 못한채 시험이 종료되었다 ㅜㅜ

Solution

#include <bits/stdc++.h>

#define P 10

using namespace std;

int X=2*3*5*7*11*13*17*21*23;
int p[100]={2,3,5,7,11,13,17,21,23,29,};
long long M[100], M_[100];
int rest[100];

void solve();
int question(int a, int b);
int CRT();

int main()
{
	int t, i, j;
	
	for(i=0; i<10; i++) M[i] = X/p[i];
	for(i=0; i<10; i++){
		for(j=1; j<p[i]; j++){
			if((j*M[i])%p[i] == 1) M_[i] = j;
		}
	}
	
	cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

void solve()
{
	int a, b, ret, i, j, ans;
	
	for(i=0; i<30; i++) rest[i] = -1;
	
	for(i=0; i<5; i++){
		a = X+i;
		b = 2*X+i;
		ret = question(a, b);
		
		for(j=0; j<10; j++){
			if(rest[j] != -1) continue;
			if(ret%p[j] == 0) rest[j] = i;
		}
	}
	
	ret = CRT();
	
	ans = 0;
	for(i=1; i<=5; i++){
		a = ret*i;
		if(a > 1000000000) break;
		
		int tmp = question(a, a*2);
		ans = max(ans, tmp);
	}
	
	cout << "! " << ans << '\n';
}

int question(int a, int b)
{
	int ret;
	
	cout << "? " << a << ' ' << b << '\n';
	cin >> ret;
	
	return ret;
}

int CRT()
{
	long long x=0, i;
	
	for(i=0; i<10; i++){
		x = (x + M[i]*M_[i]*rest[i])%X;
	}
	
	return x;
}

마치며...

1번에서 gcd, lcm 문제가 등장하였는데, 너무 오랜만에 보는 lcm이었다. 처음부터 극단적인 경우를 생각했더라면 더욱 빠르게 문제를 풀 수 있었을 테지만, 오랜만에 등장하는 lcm으로 인해 수학적으로 식을 정리해야 될 것만 같은 생각이 들었고, 결과적으론 문제를 해결했지만 문제를 복잡하게 접근했던 것 같다.

또 C번을 풀 때에도 풀이를 생각하는 과정에서 처음 생각한 풀이에서 반례가 나오자 반례를 해결하기 위한 생각 때문에 문제를 멋대로 해석하는 실수를 저지르고 말았다. 문제가 너무 어렵게 느껴지면 문제의 조건을 다시 확인하는 것이 문제를 해결하는데 도움이 된다는 사실을 다시 한번 느꼈다.