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

🎄대회로 맞이하는 크리스마스.🎄

새해에도 코딩과 함께~ 🔥🔥🔥

---

A: Temporarily unavailable

실직선 위의 위치  \(a\)에서 \(b\)까지 일정한 속도로 이동할 때, 위치 \(c\)의 기지국으로부터 거리 \(r\) 초과로 떨어져 있는 시간을 구하는 문제이다. 두 구간의 교집합의 크기를 구하면 바로 해결 가능하다.

5분에 AC

---

B1: K for the Price of One (Easy Version)

문제의 제목과도 같이 \(k\)개의 물건을 동시에 구매할 수 있다. 이때의 구매가는 \(k\)개의 물건 중 최고 가격의 물건이다. 혹은 하나의 물건을 낱개로 구매할 수도 있다. 보유한 돈의 액수가 주어지고 각 물건의 가격이 정해졌을 때, 최대 몇개의 물건을 구매할 수 있는지 구해야 한다. B1의 경우 \(k\)값이 2로 한정되어있다.

물건의 가격을 정렬한 후 이진탐색을 이용해 해결하였다. 가격순으로 정렬된 물건 중에서 적절한 위치를 선택한 후, 그 지점으로부터 가격이 더 싸지는 방향으로 두개씩 묶어서 구매한다. 마지막에 묶이지 않는 하나가 남는다면 그 하나만 따로 구매해준다. 이때 필요한 총 금액을 보유한 금액과 비교해 이진탐색을 진행하였다. 싼 물건부터 사야 하고, 사는 물건 중에서는 비싼 물건부터 묶어서 구매해야 돈이 최대로 절약되기에 이러한 풀이를 떠올릴 수 있었다.

21분에 AC

---

B2: K for the Price of One (Hard Version)

B1과의 차이점은 \(k\)값이 이제 2가 아닌 숫자로 들어올 수 있다는 점이다. 기존의 풀이에서 물건을 묶는 단위를 임의의 \(k\)개로 수정하였고, 이진 탐색 또한 수정해야되었다. 이진 탐색의 유효성이 보장되기 위해서는 탐색 대상이 정렬되어 있어야 하는데, 3 이상의 \(k\)부터는 마지막에 묶이지 못하여 개별 구매해야 할 수 있는 물건의 개수가 증가하기 때문에 총 소요 금액의 정렬이 보장되지 않는다. 이에 대한 해결 방법으로 탐색 범위 내에 \(k\)의 배수 위치가 존재한다면, 원래 탐색하려던 위치 대신 그 \(k\)의 배수를 탐색하였다. More formally, 탐색 위치 \(x\)에 대해 \(f(x)=\lceil \frac x k \rceil \times k\)의 위치를 대신 탐색하였다.

디버깅 시간 및 변형된 이진탐색을 구상하는 시간이 꽤 들어 18분이 소요되었다.

39분에 AC

---

C: Petya and Exam

입력이 많아 조금 당황스러웠던 문제이다. 제한 시간 내에 풀어야 하는 시험이 있는데, 시험은 쉬운 문제들과 어려운 문제들로 구성되어 있다. 쉬운 문항과 어려운 문항은 각각 한 문제를 푸는 것에 정해진 시간이 소요된다. 시험은 응시자가 원하는 시간에 조기종료할 수 있는데, 시험이 진행됨에 따라 문항별로 각기 다른 시간에 그 문제를 푸는 것이 '필수'가 된다. 예를 들어, 3분에 필수가 되는 문제가 있다면, 시험시간 3분 이후에 시험을 종료한다면 해당 문제를 풀고 종료해야만 한다(아니면 0점 처리된다). 이때 시험에서 받을 수 있는 최대 점수를 구하는 문제이다. (1문제당 1점으로 둔다.)

 

뭐가 많아서 오히려 별 생각이 안들었다. 그래도 일단 뭐라도 해봐야겠다는 생각에 쉬운 문항과 어려운 문항을 분리시켜 필수가 되는 시간 순서대로 정렬하였다. 예제 입력을 놓고, 우선은 시험 시간이 진행됨에 따라 문항 선택을 어떤 greedy한 방식으로 하는 방법을 떠올려보았다. 여러 시도 후에도 별 진전이 없자 풀이의 방향을 틀어 시험 종료 시간을 기준으로 풀 수 있는 문항의 수를 탐색하는 방법이 있겠다는 생각을 해 보았다(사실은 종료시간 - 1 기준으로 봐야 하는데 이는 나중에 알게 되었다). 각 문제가 필수가 되는 시간 기준으로 탐색을 해 본다면 입력의 크기 \(n=2\cdot10^5\)이기에, 각 종료 시간마다 \(\log n\) 이하 시간에 풀 수 있는 문항 수를 셀 수 있다면 제한 시간 내에 돌아가는 \(n\log n\) 풀이가 될 것이다.

 

\(\log n\)시간에 풀 수 있는 문항 수를 찾는 것은 크게 어렵지 않았다. 앞의 두 문제에서 활용한 이진 탐색을 이용한다면 현재 살펴보고 있는 시험 종료시간 이전에 풀어야만 하는 문항이 쉬운 문제와 어려운 문제 중 각각 몇개 있는지 \(\log n\) 시간에 찾을 수 있다. 이렇게 점수를 받고자 한다면 필수로 풀어야만 하는 쉬운 문제와 어려운 문제의 수를 각기 구한 후, 그 문제들을 전부 푸는 것에 소요되는 총 시간을 계산해 시험 종료시간 전에 가능한지 판별하면 된다. 만약 시간이 남는다면 남은 시간 동안에는 남아있는 쉬운 문항을 최대한 풀고, 어려운 문항으로 넘어가 계속 문제풀이를 진행하면 된다. 모든 시험 종료시간에 대해 이를 진행한 후, 그중 가장 많은 문제를 푼 경우를 기억만 해주면 된다. AC를 받기 전에 한번의 TLE 판정을 받았는데, 이는 앞의 밑줄친 부분을 나눗셈으로 구현하지 않고 문장 그대로 루프로 구현해버려서였다... 이런 실수는 최소 5번은 했을텐데 이제 제발 나눗셈을 애용하자. 나눗셈!!

 

이걸 구현하는데 도대체 무슨 디버깅을 하루종일 했는지 모르겠다.

1 TLE 후 1시간 39분에 AC

---

총평

무난무난하게 푼 대회였다. 각 문제를 보고 풀이를 떠올리는 것에 걸린 시간은 비교적 적었으나, 구현하는 것 자체에 시간이 오래 걸렸고 대회의 상당 proportion을 디버깅하면서 보냈다. 문제풀이 연습을 통해 speed and precision을 높이자.

 

레이팅 변화 1703 + 53 = 1756

My Performance: ★★★☆☆