[CF] Codeforces Round 883 (Div. 3)

https://codeforces.com/contest/1846

Dashboard - Codeforces Round 883 (Div. 3) - Codeforces

오~랜만에 코포글이다. 코포는 계속 쳤는데, 나름 잘 친 거 같기도 못 친 거 같기도 그냥 쓰고 싶어서 쓴다.

 

대충 다시 블루에 가긴 한다. E2가 hack 당해서 19점만 먹는 건 좀 아쉽긴 하다. 풀이는 맞는 거 같은데, 구현에서 에지케이스가 있는 거 같다.

 

A.

높이 - 줄 길이 > 0 의 개수를 구하면 된다.

 

B. 

가로, 세로, 대각선 2개를 다 보고 답을 출력하면 된다.

 

C. 

그리디하게 풀 문제를 정하면 된다. 시간이 작을 수록 먼저 해결하면 된다.

{푼 문제 수, 페널티, 인덱스} 이 세 가지를 잘 정렬해서 등수를 찾으면 된다. 

정렬 조건은 푼 문제수 내림차순, 페널티 오름차순, 인덱스 오름차순으로 하면 된다. 처음에 페널티 정렬 조건을 반대로 해서 한 번 틀렸다.. 문제를 제대로 읽자. 아니 문제 안 읽어도 알았어야 했다 ㅋㅋ

 

D. 

중학교 수학시간에 배운 닮은 도형의 넓이 비를 이용하면 된다.

빨간선 길이 제곱과 파란선 길이 제곱이 각 삼각형의 넓이 비가 같다는 것을 이용하면 된다.

높이 오름차순으로 정렬한 이후에 직전 삼각형과 겹치는 부분이 생기면, 위의 내용을 이용해서 겹치는 부분을 빼주면서 답에 더해주면 된다.

 

E1. 

문제를 정리하면,

\( (k^e - 1) / (k - 1) = n \)을 만족하는 \((k, e)\) 쌍이 있는지 구하는 문제이다. \(n <= 10^6\) 이므로 가능한 모든 \(k, e\)쌍에 대해서 \(n\)을 만들 수 있는지 확인하면 된다.

 

E2.

E1과 다른 점은 $n <= 10^{18}$ 라는 점이다. 

여기선 \(n\)제한이 커져서 나이브하게 되지 않는다. 내 풀이는 모든 \(e\)를 보면서 \(k\)를 이분 탐색하는 것이다. \(e\)가 정해진 이후에는 \(k\)와 \((k^e - 1) / (k - 1)\)의 사이의 관계가 비례하기 때문에 이분 탐색이 가능하다. 

근데 이 글을 쓰는 도중에 hack을 당했다ㅠ 대충 구현에서 에지케이스가 있는 것 같다. 자고 일어나서 봐야겠다.

 

F.

못읽었어요.

 

G. 

사실 E2보다 먼저 읽었는데, E2 풀고 나서 조금 더 생각해 보니까 풀이가 나왔다. 근데 10분밖에 없어서 구현 실력 이슈로 Accepted를 받진 못했다. 대회 시간에 풀이 생각해 낸 자신에게 격려하는 마음으로 풀이를 써보겠다.  

문제를 요약하자면, m개의 약으로 병을 치유하는 문제이다. 

처음에 병에 걸린 상태가 주어지고, 각각의 약으로 특정 병을 치유하거나, 부작용으로 인해 걸리게 할 수 있다. 각각의 약을 먹는 데에 걸리는 시간도 주어진다.

구해야 할 것은 약을 잘 선택해서 먹어서 모든 병을 치유하는 데에 걸리는 최소 시간이다.

 

내가 처음에 생각한 것은 '순서'가 중요하니, 약을 어떤 순서로 먹어야 할까였다.

근데 순서를 확정할 방법이 없어 보였다. greedy하게 찾을 수도 없어 보였고

 

다음으로는 어떻게 '최소'시간을 찾을 지에 대해 생각하다 보니, 최단거리 문제로 치환해서 풀 수 있을 것 같았다.

그럼 그래프 모델링을 해야 한다.

정점은 병에 걸린 상태로 두면 된다. 최대 1024개의 가짓수가 있을 수 있다.

간선은 특정 약을 먹었을 때의 상태 변화를 대응시키면 된다. 간선 만드는 데에는 1024 * 1024 정도의 시간이면 구할 수 있다.  

 

구현이 조금 버벅거렸는데, 초기화, 문자열 해싱정도만 신경 써주면 된다.

 

그나저나 학회에서 코포 이후에 스터디하면서 풀이 공유를 했는데, E번은 $ 1+k+k^2 $만 따로 예외처리해서 푸는 풀이도 있다고 한다. 

스터디 하고 Vermeil, moralbook, Shandy5833과 만담을 나눴는데 진짜 개재밌었다 ㅋㅋ 진짜 무조건 공군감 ㅋㅋ