Codeforces Round #829 (Div. 2)

Dashboard - Codeforces Round #829 (Div. 2) - Codeforces

A - Technical Support

단순 구현 문제인데 문제 이해가 조금 오래 걸렸다.

00:05 AC

 

B - Kevin and Permutation

증명은 확실하지 않지만 최댓값은 N/2이라고 믿고 제출하였다.

00:12 AC

 

C1 - Make Nonzero Sum (easy version)

C2가 잘 안 풀려서 C1 먼저 풀기로 하였다.

N이 홀수면 답이 없고 N이 짝수라면 2개씩 묶어서 보면 된다.

00:25 AC

 

D - Factorial Divisibility

C2가 잘 안 풀려서 D 먼저 풀었다.

D 답지 않게 상당히 쉽게 나왔다.

i의 등장 횟수가 (i + 1)의 배수인지 검사해주면 된다.

00:30 AC

 

C2 - Make Nonzero Sum (hard version)

전체적인 풀이는 C1과 매우 유사하다.

우선 0이 아닌 원소의 개수가 홀수이면 답이 없다.

그렇지 않다면 C1과 동일하게 2개씩 묶어서 보면 된다.

0에 대하여 적절한 처리가 필요하다.

00:38 AC

 

E - Wish I Knew How to Sort (not solved)

예제부터 이해가 불가능하였다.

문제 하단에 기댓값을 구하는 계산식이 나와 있기는 하다.

그런데 수렴값을 어떻게 구하는지 전혀 몰랐다.

Wolfram Alpha에게 유료 결제하고 물어봤는데 결과만 알려주고 계산 과정을 안 알려준다.

20분 동안 인터넷 뒤지다가 다음 링크에서 계산 방법을 찾을 수 있었다.

 

계산식을 다음과 같이 정리할 수 있었다.

(1/1 + 1/4 + 1/9 + ...) * (N * (N - 1) / 2)

수학을 잘 몰라서 분모와 분자를 별도로 계산하였다.

01:54 WA

예제는 잘 나오는데 WA를 받았다.

남은 시간 동안 코드를 열심히 살펴보았지만 원인을 찾을 수 없었다.

아쉽게도 대회가 종료되었다.

 

대회가 끝난 후 분자 계산을 잘못한 것을 깨달았다.

분자 계산 방법만 수정하고 다시 제출하니 AC를 받았다.

내 실력이 부족하였던 것이라서 아쉽지는 않다.

 

다른 사람 코드를 보니 분모와 분자를 별도로 계산하지 않고 하나의 값으로 관리한다.

나머지 연산의 곱셈 역원의 특징에서 내가 잘 모르는 부분이 있는 듯 하다.

위의 식을 다음과 같이 계산해도 답을 구할 수 있다.

모든 가능한 i에 대하여 ans += pow(i * i, MOD - 2);

ans *= N * (N - 1) / 2;

 

F - The Beach (not solved)

다익스트라 알고리즘으로 풀이할 수 있다.

sunbed의 이동을 free cell의 이동으로 바꾸어 생각할 수 있다.

각 칸을 체스판처럼 칠하였을 때 free cell의 색상은 바뀌지 않는다.

모든 free cell을 시작점으로 하여 다익스트라를 돌린다.

인접한 칸의 거리의 합의 최솟값이 정답이다.

에디토리얼을 봤을 때는 뭔가 될 것 같았는데 확실하게 증명이 되지는 않았다.

 

업솔빙하다가 원인 모를 TLE를 받았다.

참고로 이 문제에서 TLE를 받은 사람은 거의 없다.

문제의 원인은 std::priority_queue가 기본적으로 가장 큰 값을 리턴한다는 것이었다.

이것을 지금 깨달았다는 것은 지금까지 C++로 다익스트라 문제를 풀어본 적이 없다는 것이다.

그리고 이것은 사실이다.

 

끝

끝