대회후기: Codeforces Round #625 (Div. 1)

코포에서의 첫 Div. 1 대회이다. 예상대로 개망했다.

---

A: Journey Planning

Integer array가 들어온다. Subsequence 하나를 택해 그 sum을 최대화 해야 하는데, subsequence에서 성립해야 하는 규칙이 한 가지 있다: subsequence에서 adjacent한 두 값은 두 값 사이의 value 차이와 index 차이가 같아야 한다.

 

잠시 생각해서 알 수 있는 사실은 A, B가 동시에 선택 가능하고 A, C가 동시에 선택 가능하다면 A, B, C가 모두 동시에 선택 가능하다는 사실이다. 따라서 선택되는 첫 element만 정한다면 그 이후에 있는 element 중 선택 가능한 모든 element를 만나는 대로 전부 다 greedy하게 주워담으면 된다...

그래서 첫 element 기준으로 루프를 돌며 별 생각 없이 $O(n^2)$으로 솔루션을 구현하고 TLE를 한 번 받았다.

 

$O(n)$으로 최적화를 성공한 줄 알고 다시 제출했지만 다시 한번의 TLE이었다. (이번에도 worst case $O(n^2)$)

 

다시 문제 description으로 돌아와 생각하던 중 내가 놓치고 있던 사실을 깨달았다. A와 B가 동시에 선택 가능하다는 뜻은, 각각의 value - index값이 일치한다는 뜻이었다.

따라서 각 값을 value - index 값 기준으로 분류해서 더해주면 된다. $O(n)$ 풀이.

2 TLE 후 46분에 AC

---

B: Navigation System

Description이 좀 장황해서 풀이도 지저분하게 길어질까봐 걱정했지만, 은근 간단하게 풀리는 문제였다.

 

Strongly connected digraph가 입력으로 들어온다.

문제의 주인공은 그래프상의 출발지로부터 목적지까지 일정 경로를 거쳐 지나간다. 이 경로 또한 주어진다.

주인공이 타고 이동하는 차량에는 항상 현재 위치로부터 목적지까지의 최단경로 중 하나를 보여주는 네비게이션이 있다.

만약 주인공이 이동 과정에서 네비게이션이 보여주고 있던 최단경로로부터 벗어난다면 네비게이션은 경로를 재탐색한다.

 

주인공이 주어진 그래프 상에서 주어진 경로대로 이동할 때, 일어날 수 있는 최대의 경로 재탐색 횟수와 최소의 경로 재탐색 횟수를 출력해야 한다.

 

풀이의 방향은 크게 고민하지 않아도 됐다. 다익스트라 혹은 BFS를 이용해 목적지로부터 그래프를 거꾸로 traverse하고, 각 지점에서 목적지를 향해 최단경로로 가고자 할 때 다음으로 밟아야 하는 node들이 어떻게 있는지만 잘 저장해두면 된다.

 

이렇게 전처리를 끝낸 이후에는 입력으로 들어온 경로를 살펴보며 경로 재탐색 횟수가 최대/최소 몇번 일어나는지 확인하면 된다.

최단경로를 이탈한다면 최대/최소 횟수 모두 다 increment이고, 최단경로가 여럿 있는데 그 중 하나를 택한다면 최댓값만 increment이다.

2 WA 후 1시간 29분에 AC

(WA는 그냥 뻘짓이었다.)

---

총평

A를 왜 이렇게 오래 붙잡고 있었는지 모르겠다. A와 B 모두 제출 후에 확인해보니 나보다 늦게 제출한 사람이... 없었다.

퍼플 달기 힘들다.

 

레이팅 변화 1955 - 73 = 1882

My Performance: ★★☆☆☆

 

연습지

이번 대회에서는 종이에 연필을 대지 않았다.