오늘의 PS (5) - 220501~7

카테고리 제목이 '오늘의 PS'인데 제목에는 당당히 7일치를 박아놓았다. 하지만 저 기간 중 문제를 풀었다고 할 날은 5월 1일과 7일 이틀뿐이었기 때문에, 한 글에 정리해보려 한다.

 

5월 1일 - 2022 DGIST 현풍전산배 알고리즘 대회 Open Contest

타임라인은 정확히 기억이 나지 않아 문제별 후기만 간단히 정리하도록 하겠다.

 

A. 에어컨

전형적인 구현 문제이다. A번 치고는 까다로운 구석이 여럿 있었던 것 같다. 출력 형식 때문에 printf를 오랜만에 사용해 볼 수 있었다.

 

B. 비즈마켓

코포 Div.2에서 볼 수 있을 것 같이 생겼다. 두 배열을 하나는 오름차순, 하나는 내림차순으로 정렬한 뒤 잘 구해주면 됐던 것 같다.

 

C. D. 사각형 게임 (Small, Large)

오픈콘이라 두 가지 버전이 있는 줄 알았는데, 본 대회에서도 그랬다고 들어서 놀랐다. C는 브루트포스로 풀 수 있으며, D는 거기에 조금의 그리디적인 생각을 더해주면 해결할 수 있다.

 

E. 랜선 연결

문제 자체는 괜찮은 냅색 응용문제라고 생각한다. 다만 약간 당황스러운 코너 케이스 하나가 모두를 황당하게 만들었던 것 같다. 지문을 오히려 모호하게 쓰거나, 해당 케이스에 대해 확실히 언급을 해주는 것이 더 괜찮지 않았을까 싶다.

 

F. 뮤직 플레이리스트

그림을 그려보면, 겹치지 않는 두 구간합의 합의 최댓값을 구해야 한다는 것을 알 수 있다. 이는 Kadane DP를 앞에서 한 번, 뒤에서 한 번 돌려서 Prefix와 Suffix 형태의 배열을 만들면 쉽게 구할 수 있다.

 

G. 최고의 간선

얼마 전 팀 연습에서 풀었던 16528과 같은 아이디어를 사용하는 문제다. 16528에서 했던 것을 각 정점에 대해 해준 후, DFS를 적절히 돌려서 체크해주면 된다.  시간 복잡도가 \(O(NMlogM)\)인데, 1억==1초라는 기준에서 보면 약간 빡빡해 보였을 수도 있을 것 같다. 물론 실제로는 0.5초 정도에 돌아간다.

 

H. 천체 관측

기하 구현을 할 줄 아는가? 라고 묻는 문제이다. 별다른 아이디어가 필요하지 않고, 그냥 하라는 대로 구현을 잘 하면 되는데 그걸 못해서 결국 시간 내에 풀지 못했다. 나중에 보니까 두 CCW의 부호가 다름을 확인하는 과정에서 CCW를 곱하는데, CCW를 1 0 -1 버전이 아니라 외적값을 그대로 뱉는 버전을 써서 오버플로우가 났던 것 같다.

 

I는 \(O(N^2)\) 풀이는 비교적 빨리 나오는데, \(O(N)\) 풀이도 있는 것 같아 고민중이다.

 

5월 7일 - 2022 KAIST RUN Spring Open Contest

 

A. Sequence Conversion

코포 Div.2에서 본 것 같이 생긴 문제 2. 쉽게 떠올릴 수 있는 그리디한 풀이를 짜면 맞는다.

 

B. Ontongdaejeon

내가 못하는 그리디 문제다. 바로 떠올릴 수 있는 전략은 예제에 떡하니 반례가 있으며, 뭔가 포인트 저장이 실수로 되는 것 같아 (이건 사실 확실치 않다) 귀찮아 보인다. 이상한 그리디 코드를 몇 번 냈으며, 통과한 전략은 '지금 포인트를 조금 쓰더라도 남은 물건을 모두 포인트로 살 수 있다'에 해당할 때만 포인트를 쓰는 것이다. 그 외에 이분탐색을 쓰는 풀이도 있는 것 같다.

 

C. TOO EASY Cookie Run

보자 마자 파라메트릭임을 쉽게 알 수 있고 코드도 어렵지 않은데, 무지성으로 짜면 long long에서 오버플로우가 난다. 이를 잘 처리만 해주면 쉽게 맞을 수 있다. 시간 복잡도는 결정 함수 구현을 투포인터로 하면 \(O(NlogX)\), 이분탐색으로 하면 \(O(NlogNlogX)\) 이다.

 

D. Sequence Conversion 2

N이 3000이라 대충 제곱 DP일 것 같다. \(DP[i][j][k]\)를 마지막 원소를 i~j번으로 묶고, 마지막 상태가 k (오르막 또는 내리막) 일 때 최대 길이로 정의해준 후, 각 부분합을 정렬해놓은 DP를 같이 관리해주면 \(O(N^2logN)\)에 문제를 풀 수 있는데, 나만 그런건지는 모르겠다만 상수가 꽤 커서 계속 TLE가 났다. 결국 열심히 최적화를 해서 15번만에 AC를 받았는데, 대회가 끝나고 생각해보니 long long을 계속 쓴거 같아서 처음 50점 솔루션을 int로 바꿔서 냈더니 1960ms에 돌아가더라. 이걸 왜 2시간동안 못봤을까?

 

E와 F는 재밌어 보이는데 시간이 없어 보지 못했다.

 

백준 오픈콘 등수만큼 의미가 없는게 없긴 하지만, 요즘은 치는거마다 5위권 언저리는 항상 하는 것 같아 만족스럽다. 있는 콘테스트마다 꾸준히 친게 도움이 된 것 같다.