Good Bye 2022: 2023 is NEAR

Dashboard - Good Bye 2022: 2023 is NEAR - Codeforces

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

 

끝

끝