Pinely Round 1

Dashboard - Pinely Round 1 (Div. 1 + Div. 2) - Codeforces

A - Two Permutations

단순 수학

00:02 AC

 

B - Elimination of a Ring

N이 짝수이고 (N / 2)번 등장한 수가 2개라면 답은 (N / 2 + 1)이다.

이외의 경우 답은 항상 N이다.

증명 없이 감으로 제출하였다.

00:08 WA

처음에는 maxv번 등장한 수로 잘못 판단하였다.

위의 풀이대로 수정하고 다시 제출하였다.

00:11 AC

 

문제의 조건에 따라 단순히 등장하는 수의 개수가 2개인지 파악하는 것으로도 충분하다.

 

C - Set Construction

위상 정렬

00:18 WA

문제 조건을 잘못 이해하였다.

살짝 수정해서 다시 제출하였다.

00:21 AC

 

E - Make It Connected

D번이 감이 안 와서 E번을 살짝 구경하였다.

뭔가 간단하게 풀릴 것 같아서 다음과 같은 단순한 풀이를 시도하였다.

가장 큰 연결 요소와 가장 작은 연결 요소를 찾는다.

가장 큰 연결 요소에 속하지 않는 모든 정점에 대하여 연산을 수행한다.

또는 가장 작은 연결 요소에 속하는 모든 정점에 대하여 연산을 수행한다.

00:48 WA

 

원래라면 포기하고 D번으로 돌아갔어야 하지만 뭔가 느낌이 왔다.

여러 예제를 그려 보며 case work를 하였다.

• 이미 연결 그래프라면 연산이 필요 없다.
• 서로 인접하지 않은 정점 u와 v가 동일한 연결 요소에 속한다면 v에 대하여 연산을 수행한다.
• 이제 모든 연결 요소는 완전 그래프이다.
• 연결 요소의 개수가 2개라면 작은 연결 요소에 속하는 모든 정점에 대하여 연산을 수행한다.
• 그렇지 않다면 서로 다른 임의의 연결 요소 2개의 임의의 정점에 대하여 연산을 수행한다.

01:11 WA

 

밑줄 친 case를 추가하였다.

• 이미 연결 그래프라면 연산이 필요 없다.
• 정점 v의 차수가 0이라면 v에 대하여 연산을 수행한다.
• 서로 인접하지 않은 정점 u와 v가 동일한 연결 요소에 속한다면 v에 대하여 연산을 수행한다.
• 이제 모든 연결 요소는 완전 그래프이다.
• 연결 요소의 개수가 2개라면 작은 연결 요소에 속하는 모든 정점에 대하여 연산을 수행한다.
• 그렇지 않다면 서로 다른 임의의 연결 요소 2개의 임의의 정점에 대하여 연산을 수행한다.

01:14 WA

 

마지막 case를 새롭게 수정하였으나 완전히 틀렸으므로 언급하지는 않겠다.

01:22 WA

 

D번이 많이 풀리고 있었으나 여기까지 온 이상 E번을 꼭 풀고 싶었다.

다행히 위의 풀이에서 세 번째 case가 잘못되었음을 깨달았다.

다음과 같이 수정하였다.

• 이미 연결 그래프라면 연산이 필요 없다.
• 정점 v의 차수가 0이라면 v에 대하여 연산을 수행한다.
• 서로 인접하지 않은 정점 u와 v가 동일한 연결 요소에 속하고 v가 단절점이 아니라면 v에 대하여 연산을 수행한다.
• 이제 모든 연결 요소는 완전 그래프이다.
• 연결 요소의 개수가 2개라면 작은 연결 요소에 속하는 모든 정점에 대하여 연산을 수행한다.
• 그렇지 않다면 서로 다른 임의의 연결 요소 2개의 임의의 정점에 대하여 연산을 수행한다.

이렇게 하여 Union-Find + Articulation Point + case work 풀이가 완성되었다.

사실 위의 풀이가 성립하려면 완전 그래프가 아닌 연결 요소에 대하여 정점 v가 반드시 존재함을 증명해야 한다.

어차피 페널티도 큰데 proof by ac를 시도하였다.

01:46 WA

 

단절점 코드에서 초기화를 잘못하였다.

01:51 AC

 

너무 많이 틀렸는데 그래도 마음은 홀가분하였다.

레이팅이 나락 갔을 줄 알았는데 오렌지 퍼포를 내고 있었다.

그만큼 D번과 E번 모두 쉽지는 않은 라운드였다.

 

D - Carry Bit (not solved)

핵심적인 관찰은 대회 중에 마쳤으나 조합론 지식이 부족하여 계산에 실패하였다.

 

carry가 존재하는 상태와 존재하지 않는 상태를 각각 A와 B라고 하자.

잘 관찰해보면 다음과 같은 사실을 도출할 수 있다.

• 현재 상태를 유지하는 경우의 수는 (3 * 이전 상태의 경우의 수)이다.
• 상태를 전이하는 경우의 수는 이전 상태의 경우의 수와 동일하다.

답은 K개의 A와 (N - K)개의 B를 배치하는 경우의 수와 동일하다.

초기 상태는 B이므로 다음과 같이 구간을 배치하는 경우의 수를 모두 구하여 더해주면 된다.

• B A
• B A B
• B A B A
• B A B A B
• ...

예를 들어 네 번째 경우를 보자.

• 상태 전이는 4번이다. 경우의 수는 3^(N - 4)가 된다.
• K개의 A를 2개의 구간으로 분할한다. 경우의 수는 C(K - 1, 1)이다.
• (N - K + 1)개의 B를 3개의 구간으로 분할한다. 경우의 수는 C(N - K, 2)이다.

초기 상태가 B이므로 (N - K)에서 1을 더해주었다.

 

추가적으로 K가 0일 때는 예외 처리가 필요하다.

 

F1 - Anti-median (Easy Version) (not solved)

Pass

 

F2 - Anti-median (Hard Version) (not solved)

Pass

 

G - Centroid Guess (not solved)

Pass

 

끝

끝