Codeforces Round #748 (Div. 3)

2021.10.14

나쁘지않게 잘 한것 같다.

Div 3 치고 C가 좀 어려운듯?

A

Problem - A - Codeforces

3개의 수 중 최댓값이 되려면 각 수에 몇을 더해야 하는지 구하라는 문제

B

Problem - B - Codeforces

25로 나눌수 있게 수들을 제거하는데 제거의 최소 숫자를 구하라는 문제

어차피 25로 나눌 수 있으면 뒷자리 2자리만 생각하면 되기 때문에 str로 보면 n = 18이라서 $n^2$으로 충분히 풀 수 있다.

C

Problem - C - Codeforces

걍 출구에서 가장 가까운놈부터 탈출시키면 되는 그리디 문제

D1

Problem - D1 - Codeforces

특정 수에 k를 여러번 빼서 모든 수를 같은 수로 만들수있는 최대 k를 구하는 문제였다.

k가 1이라면 언제나 만들수 있으므로 언제나 k는 1보다 크거나 같다.

이 문제는 n이 40 밖에 되지 않기 때문에 그냥 모든 수의 차이의 절댓값들의 최대 공약수를 찾으면 되는 문제였다.

D2

Problem - D2 - Codeforces

이 문제는 D1의 좀 더 어려운 문제로 최소 절반은 같은 수로 만들 수 있는 k의 최댓값을 찾는 문제였다.

무지성으로 걍 싹다 돌리기의 시간복잡도를 잘못 계산해서 $40\times40\times200000$으로 계산해야되는데 $40\times2000000$으로 해서 걍 시간 초과 나버렸다 ㅋㅋ

Gravekper님의 해설을 보니 걍 두 개 랜덤으로 찍어서 걔네의 공약수에 k의 최댓값이 들어있을 확률이 $1\over4$이다. 그래서 이걸 100번 반복하면 안들어있을 확률이 $({3\over4})^{100}$으로 매우 작아 맞을 수 있다고 한다....

이때 $1\over 4$인 이유는 절반이 같아야 하므로 아래 그림처럼 나타낼 수 있다.

이때 안 같아도 되는 것의 개수와 같아야 하는 것의 개수가 같으므로 두개를 뽑을 경우 다음과 같은 경우가 나올 수 있다.

1. 안 같아도 됨 구역에서 2개 뽑힐 경우
2. 첫번째는 안같아도 됨 구역에서, 두번째는 같아야 됨 구역에서 뽑힐 경우
3. 첫번째는 같아야 됨 구역에서, 두번째는 안 같아도 됨 구역에서 뽑힐 경우
4. 같아야됨 구역에서 2개가 뽑힐 경우이다.

여기서 4번만이 우리가 원하는 경우이므로 $1\over 4$ 확률로 정답이 공약수에 들어있다고 가정하는 것이다.

E

Problem - E - Codeforces

map이나 set같은것을 잘 사용해서 leaf인 노드를 잘 찾을 수 있게 짜면 맞는 문제..

leaf가 없어지면 다음 leaf가 될수있는 노드는 leaf의 부모이다를 잘 사용하면 되는 문제였음..