Good Bye 2022: 2023 is NEAR
Dashboard - Good Bye 2022: 2023 is NEAR - Codeforces
codeforces.com
A - Koxia and Whiteboards
매번 정렬하면서 가장 작은 수를 대체하면 된다.
00:03 AC
정해에서는 마지막 수는 항상 남는다는 점을 이용한다.
따라서 마지막 수를 제외한 (N + M - 1)개의 수를 정렬한 후 상위 (N - 1)개의 수와 마지막 수를 선택하면 된다.
B - Koxia and Permutation
1 N 2 (N - 1) 3 ...
00:07 AC
C - Koxia and Number Theory
동일한 수가 존재한다면 x는 존재하지 않는다.
00:09 WA
추가적인 조건이 필요하다.
모든 a_i와 소수 p에 대하여 a_i % p의 빈도를 세자.
x가 존재하려면 빈도의 최솟값은 2 미만이어야 한다.
N이 최대 100이므로 50 이하의 소수만 고려하면 된다.
00:18 AC
D - Koxia and Game
BOJ 9938번 응용 문제임은 금방 알아차렸는데 뇌절에 뇌절을 거듭하다가 코드가 산으로 갔다.
Union-Find 또는 dfs로 해결할 수 있는 문제이다.
나는 Union-Find로 시도하다가 추가적으로 dfs를 돌리고 마지막에는 단절선 코드까지 가져오는 뇌절을 하였다.
다시 보니 Union-Find만으로 해결되길래 다 지우고 새로 짰다.
00:45 TLE 00:50 TLE 00:52 TLE 01:07 TLE 01:12 WA 01:22 WA 01:28 AC
풀이를 간략하게 설명하자면 다음과 같다.
답의 존재 여부의 판단 방법은 BOJ 9938번의 풀이를 참고하자.
답이 존재한다면 그래프의 각 연결 요소 c에 대하여 c가 self-loop를 포함하는지 확인해야 한다.
self-loop의 포함 여부에 따라서 N 또는 2를 곱해주면 된다.
정말 여러 가지 복합적인 이유로 틀렸는데 가장 큰 원인은 뇌절이다.
나머지 원인은 뇌절이 불러온 스노우볼이라서 자세히 설명하지는 않겠다.
그래도 몇 가지 깨달음을 얻었으니 정리하고 가자.
- 답이 존재하지 않는다면 별도로 처리해주자.
- TC 문제에서는 초기화를 잘 하자.
- 구현이 복잡해지면 먼저 올바른 풀이인지 확인하자.
아직 처참한 실력이니 계속 노력해야겠다.
E - Koxia and Tree (not solved)
각 간선에 대하여 해당 간선의 사용 횟수를 구하면 된다.
다음과 같은 배열 A, sz, par을 관리하자.
- A[i] = 정점 i에 나비가 존재할 확률, 초깃값은 0 또는 1
- sz[i] = 1번 정점을 루트로 할 때 i번 정점을 루트로 하는 서브트리에 존재하는 나비의 수
- par[i] = 1번 정점을 루트로 할 때 i번 정점의 부모 정점의 번호
정점 u와 v를 연결하는 간선 e에 대하여 다음과 같은 세 가지 경우가 있다.
- 나비가 이동하지 않는다.
- 정점 u에서 v로 나비가 이동한다.
- 정점 v에서 u로 나비가 이동한다.
이때 각 간선을 지나는 나비의 수는 최대 한 마리이다.
위의 세 가지 경우에 대하여 자세히 알아보자.
편의를 위하여 u가 v의 부모 정점이라고 가정한다.
(i) 나비가 이동하지 않음
발생 확률은 A[u] * A[v] - (A[u] + A[v]) / 2 + 1이다.
이때 간선의 사용 횟수는 sz[v] * (K - sz[v])이다.
(ii) 정점 u에서 v로 나비가 이동
발생 확률은 A[u] * (1 - A[v]) / 2이다.
이때 간선의 사용 횟수는 (sz[v] + 1) * (K - sz[v] - 1)이다.
(iii) 정점 v에서 u로 나비가 이동
발생 확률은 A[v] * (1 - A[u]) / 2이다.
이때 간선의 사용 횟수는 (sz[v] - 1) * (K - sz[v] + 1)이다.
모든 경우를 살펴본 후 A[u]와 A[v]를 업데이트하면 된다.
A[u]와 A[v] 모두 (A[u] + A[v]) / 2가 됨을 보일 수 있다.
정답은 sum(발생 확률 * 간선의 사용 횟수) / C(K, 2)가 된다.
F - Koxia and Sequence (not solved)
Pass
G - Koxia and Bracket (not solved)
Pass
H - Koxia, Mahiru and Winter Festival (not solved)
Pass
끝
끝