2022 IOI 멘토교육 2주차

문제 셋:

1번 IOI09 POI (https://www.acmicpc.net/problem/5462)

2번 BOI06 Coin Collector (https://www.acmicpc.net/problem/3368)

3번 CEOI13 Adriatic (https://www.acmicpc.net/problem/9284)

4번 KTST20 하나 둘 셋 (https://www.acmicpc.net/problem/25013)

 

KOI 스타일로 구성된 4시간 셋입니다.

 

0:00 ~ 0:06

난이도 순이라는 걸 알고 있었기 때문에 1번부터 차례로 풀었습니다. 매우 쉬운 문제이므로 바로 AC를 받고 넘어갔습니다.

 

0:06 ~ 1:30

2번을 봤습니다. 문제를 잘못 이해해서 1시간 가까이 뇌절을 했고, 일단 나이브라도 짜서 부분점수를 긁으려 했습니다. 나이브를 짜는 과정에서 문제를 잘못 이해했다는 것을 깨닫고, 나이브를 새로 짜서 부분점수를 긁었습니다. 문제를 잘못 이해했을 때 했던 관찰은 그대로 유효해서, 새로운 풀이를 쉽게 유도했습니다.

 

관찰. 얻을 수 있는 동전의 종류의 최댓값은 로그 스케일이다.

 

현재 x원만큼 거스름돈을 받아야 하는 상황에서 어떤 동전으로 그 중 일부를 지급하면 반드시 x/2원 이하로 줄어들기 때문에 성립합니다.

dp[i][x]: i번째로 비싼 동전까지 봤고, 현재 x가지 종류의 동전을 얻었을 때 남는 거스름돈의 최댓값

이라고 정의하면 dp[i][x]를 dp[i+1][x]와 dp[i+1][x+1]로 상태전이해줄 수 있으므로, 얻을 수 있는 동전의 종류의 최댓값을 계산할 수 있습니다.

파라매트릭 서치를 이용해서 구매할 물건의 비용의 최댓값을 구해주면 O(Nlog^2K)에 문제를 풀 수 있습니다.

 

정해는 작은 비용의 동전부터 보면서 그리디하게 현재 보는 동전을 수집할 수 있으면 수집하도록 가격을 정하는 풀이라고 합니다.

 

1:30 ~ 2:47

3번을 봤습니다. 단순히 그래프를 가지고 뭔가를 하는 풀이는 당연히 안 될 것이라고 생각했기 때문에, 문제에서 나타나는 특징을 먼저 찾아봤습니다. 어떤 점 x에서 시작해서, k번 이내로 도달할 수 없는 영역을 그려보면, 어떤 두 점 (x1, y1), (x2, y2)가 존재해서 (x1, y1)의 오른쪽 위, (x2, y2)의 왼쪽 아래로 나타납니다.

(x1, y1)의 오른쪽 위를 못 가는 상황에서 1번 더 이동하면 그 영역이 어떻게 변할지를 O(L^2)에 전처리할 수 있습니다. (L은 격자판 한 변 길이)

모든 점은 도달할 수 있다면 L번 이내로 도달 가능하므로, 각 점에 대해 1번씩 늘려주면서 시뮬레이션을 하면 O(NL)에 문제를 풀 수 있고, 이는 서브태스크 4까지 맞을 수 있습니다. (N<=25000)

 

2:47 ~ 3:21

전처리 과정을 약간만 변형하면 (x, y)에서 시작했을 때의 답까지 다 구해놓을 수 있습니다. 따라서 문제를 O(L^2 + N)에 풀 수 있습니다. 디버깅이 오래걸렸습니다.

 

3:21 ~ 4:00

4번을 봤습니다. 서브태스크 1을 풀 수 있는 풀이는 간단한 비트 dp였고, 일단 긁었습니다. 다항시간 풀이를 찾으려고 노력해보았지만 대회 시간 내에 찾지 못했습니다. 감도 안 잡혔네요...

 

2번과 3번에서 뇌절을 좀 많이 해서 시간 관리를 제대로 못한 것 같습니다. 문제를 제대로 읽고 나이브를 바로바로 짜야겠다는 생각이 들었습니다. 그리고 그리디 알고리즘 좀 연습해야겠네요...