Codeforces Round #841

Dashboard - Codeforces Round #841 (Div. 2) and Divide by Zero 2022 - Codeforces

서론

난이도에 비하여 상당히 오래 걸렸다.

 

A - Joey Takes Money

수 하나에 몰아주면 된다.

00:03 AC

 

B - Kill Demodogs

수학

00:12 AC

 

C - Even Subarrays

전체 경우에서 약수의 개수가 홀수인 경우를 빼는 것이 더 간편하다.

약수의 개수가 홀수인 수는 제곱수이다.

그리고 문제의 제한에 의하여 가능한 제곱수는 512개이다.

따라서 각 인덱스에 대하여 pxor을 구한 후 최대 512개의 원소만 순회하면 된다.

00:39 TLE

map 대신 배열을 사용하도록 하였다.

00:43 RTE

인덱스를 초과하였다.

00:45 AC

 

D - Valiant's New Map

전형적인 이분 탐색 + dp 문제인데 너무 늦게 발견하였다.

01:21 AC

 

E - Graph Cost

대회 전날에 BOJ 26953번을 풀었는데 동일한 아이디어를 그대로 적용할 수 있었다.

어떠한 k에 대하여 가중치가 (k + 1)인 간선의 개수는 Euler's phi function으로 구할 수 있다.

간선은 k가 큰 것부터 그리디하게 선택하면 된다.

01:44 AC

 

그리디 알고리즘이 성립하는 이유를 간단히 살펴보자.

먼저 다음과 같은 배열 B를 정의하자.

B[i] = 비용이 i인 간선 묶음의 개수

비용이 i인 간선 묶음은 가중치가 i인 간선 (i - 1)개로 구성된다.

여기서 배열 B의 값이 단조 감소함에 주목해야 한다.

 

간선이 1개인 그래프는 비용이 2인 묶음을 추가하여 만들 수 있다.

간선이 i(i > 1)개인 그래프는 다음과 같이 만들 수 있다.

• 간선이 (i - 1)개인 그래프에서 마지막으로 추가한 묶음을 x라고 하자.
• x보다 비용이 1만큼 큰 묶음이 존재한다면 해당 묶음을 추가하고 x는 제거한다.
• 그렇지 않다면 비용이 2인 묶음을 추가한다.

이 알고리즘으로 구한 해는 최적해이며 그리디 알고리즘이 구한 해와 동일하다.

따라서 그리디 알고리즘이 성립한다.

 

F - Function Sum (not solved)

Pass

 

끝

끝