이동식 저장소

매우 오랜만에 코포에 참가한다.

A. Boring Apartments

매우 간단한 수학 문제이다. 

예상 난이도: 브론즈2

B. Yet Another Bookshelf

문제를 읽었을 땐 뭔가 어려워 보였는데, 생각해 보니 (인접한 두 segment 간의 거리)-1을 모두 더하면 답이 된다. B번을 너무 어렵게 생각해서(약 15분) D번 풀 시간이 부족해졌다..

예상 난이도: 실버4

C. Dominant Piranha

C번도 간단해 보이는 구현 문제이다.

우선 정답의 후보는 크기가 가장 큰 피라냐들로 한정한다. 가장 크지 않은 피라냐도 정답이 될 수 있는 경우가 있지만, 알고리즘을 단순화하기 위해 가장 큰 피라냐들을 생각한다.

주어진 피라냐들의 크기의 최댓값을 $m$이라고 하고, 크기가 $m$인 피라냐가 존재하는 위치 중 하나를 $i$라고 하자. 만약 $i$번의 양 옆에 자신보다 크기가 작은 피라냐가 적어도 한 마리 존재한다면 $i$가 정답이다. $i$번째 피라냐가 다른 피라냐를 먹으면 크기가 1 증가하여 $m+1$이 되는데, 이러면 $i$번째 피라냐는 다른 어떤 피라냐보다 크기가 크게 되어 모든 피라냐를 잡아먹을 수 있게 된다.

만약 $i$번이 자신의 좌우에 있는 피라냐를 둘 다 먹을 수 없다면, $i$번 피라냐는 성장할 수 없게 되고, 자신과 크기가 같은 피라냐를 잡아먹을 수 없게 된다.

따라서 크기가 $m$인 피라냐 중 자신의 좌우에 있는 피라냐를 적어도 한 마리 잡아먹을 수 있는 피라냐를 찾아 위치를 출력하면 된다. 나는 처음에 크기가 $m$인 피라냐 중 맨 앞에 있는 걸 출력했는데, 위에서 말했듯이 자신의 양 옆을 잡아먹을 수 없는 경우를 고려해야 한다.

예상 난이도: 실버2

D. Districts Connection

C번까지 문제가 쉬워서 적어도 D번까지는 풀어야 레이팅이 오를 것 같았다. 지금 보니 D 풀었어도 떨어졌을 것 같지만..

문제 자체는 간단하다. $a[i]\ne a[j]$인 $(i,j)$ 쌍을 연결하여 트리를 만들 수 있는지 묻는 문제이다. 따라서 나는 $a[i]\ne a[j]$를 만족하는 모든 $(i,j)$ 쌍을 저장해 놓고, 쌍의 개수가 $n-1$ 이상이면 앞의 $n-1$개를 출력하도록 하였다.

그런데 계속 틀렸다고 한다. 아니 왜? 사실 수면 시간을 한참 넘긴 터라(12시 40분..) 머리가 잘 안 돌아가긴 했다. 아무튼 무의미하게 계속 제출하다가 포기하고 잤다.

틀린 이유

아무렇게나 연결하면 트리가 만들어지지 않을 수도 있기 때문이다.

위의 그림에서 노드 4개가 3개의 간선으로 연결되어 있지만, 이 그래프는 트리가 아니다. 오른쪽 밑의 정점이 연결되지 않았기 때문이다.

 

따라서 이 알고리즘은 틀렸다. editorial처럼 하는 게 제일 쉬운 방법이다.

문제 난이도를 봤을 때 적어도 E번까지는 풀어야 하지 않았나 싶다. E번도 잠깐 읽어보니 DP로 잘 비비면 될 것 같았는데 너무 피곤해서(12시 50분!!!) 포기했었다. 시간이 야속해~

1400 회복하자..