대회후기: Codeforces Round #703 (Div. 2)

자다 깨서 정신없이 시작한 대회.

---

A: Shifting Stacks

블록은 오른쪽으로만 이동 가능하므로, 첫번째 stack부터 $i$번째까지 스택까지의 구간에 블록이 충분한지를 모든 $i$에 대해 확인해주면 된다.

AC: 5분

---

B: Eastern Exhibition

택시거리 총합을 최소화시키는 문제인데, 택시거리 특성상 $x$축 방향 거리와 $y$축 방향 거리가 서로 독립적임을 알아차린다면 금방 끝나는 문제이다. 각 축에 대해서 값을 정렬한 후, 중앙값 하나 혹은 중앙값 두개 사이가 모두 최솟값이 된다. 하지만 나는 각 축의 거리가 독립적이라는 사실을 정말 정말 늦게 파악했고, 대회 마감 직전에 풀이를 코딩했다. 심지어 풀이도 앞서 서술한 정해와는 조금 다른데, 우연히 같은 결과가 나와서 맞았다. 대회 시간이 일반적인 대회처럼 2시간이었다면 해결하지도 못했을 문제다.

AC: 2시간 12분

요즘따라 쉬운 문제에서 자꾸 막힌다...

---

C1: Guessing the Greatest (easy version)

제약조건이 더 어려운 C2까지 한번에 풀었으므로 내용은 아래에만 쓴다.

AC: 1시간 25분

---

C2: Guessing the Greatest (hard version)

내가 좋아하는 interactive problem이다. 서로 다른 수들의 배열이 있는데, 제일 큰 수의 위치를 찾아내는 것이 목표이다. 쿼리로는 구간을 넣을 수 있고, response로는 그 구간에서 두번째로 큰 수의 index를 받는다.

 

일단 전체 쿼리를 넣어야 할 듯 해서 전체 쿼리를 넣는다. 그러면 전체에서 두번째로 큰 숫자의 위치를 알게 된다.

최종적으로 찾고자 하는 것은 제일 큰 숫자이므로, 제일 큰 숫자가 방금 찾은 두번째로 큰 숫자의 위치에 대해서 왼쪽에 있는지, 오른쪽에 있는지가 궁금해진다. 다행히도 왼쪽 구간 혹은 오른쪽 구간에 대해서 쿼리를 넣어봐서, 응답으로 처음에 받았던 전체에서 두번째로 큰 숫자의 위치가 다시 나온다면 그 구간에 전체에서 제일 큰 숫자가 있음을 쉽게 알 수 있다.

 

고로 이진탐색을 진행하면 해결된다.

AC: 1시간 25분

 

---

총평

B에서 거의 두시간을 통째로 날려버리는 바람에 망해버렸다. C는 정말 보자마자 풀리는 문제인데도 B에 매달려 있느라 해결이 늦었다.

레이팅을 위해서는 막힌 문제를 버리고 넘어가야함을 알지만, 고집 때문에 매번 붙잡고 있게 된다.

 

레이팅 변화: 1926 - 49 = 1877

My Performance: ★☆☆☆☆

---

연습지

사용하지 않았다.