221019 팀? 연습

동방에서 혼자 Class 9 문제들을 보고 있었는데 선배들이 막고라를 신청해 팀 아닌 팀 연습을 하게 되었다. 그 시간에 팀 연습을 하는게 낫지 않나.. 라는 생각도 있었지만, 재밌을 것 같아 하기로 했다.

셋은 2021 KCPC를 사용하였다.

https://www.acmicpc.net/category/detail/2881

https://www.acmicpc.net/category/detail/2882

팀 연습이 아니기 때문에, 그냥 내가 푼 순서대로 문제별 후기를 적도록 하겠다.

 

23758 - 중앙값 제거 (실제 대회 2C-1A, 위 스코어보드에서는 B, S1)

구현 문제처럼 생겼지만, 직접 구현하면 TLE를 받는다. 해당 연산을 반복하면 중앙값 앞의 수들만 바뀌기 때문에, 해당 수들에 대해 2로 몇 번 나눠지는지를 구하고 모두 더하면 된다.

 

23757 - 아이들과 선물 상자 (실제 대회 2B, 위 스코어보드에서는 E, S2)

구현 문제처럼 생겼고, 그게 맞다. 항상 가장 많은 상자에서 선물을 가져가는 것이 최적임만 파악하면 그냥 pq 또는 set으로 구현해주면 된다.

 

23756 - 노브 돌리기 (실제 대회 2A, 위 스코어보드에서는 G, B2)

그냥 브론즈 구현 문제이다. 항상 짧은 쪽으로 이동해주면 된다.

 

23759 - 비슷한 문자열 (실제 대회 2D, 위 스코어보드에서는 J, G2)

각 문자열에 대해, 해당 문자열 앞에 올 수 있는 문자열의 후보는 \(O(K)\)이다. 따라서, \(last[i][j]\) = \(i\)번째 자리에 \(j\)번째 문자가 오는 문자열 중 가장 뒤의 문자열을 의미하는 배열을 관리해주며 DP를 돌리면 된다.

 

23760 - 까다로운 아이들과 선물 상자 (실제 대회 2E, 위 스코어보드에서는 D, P5)

계속 봐도 모르겠어서 제한을 한 번 봤더니, 각 선물 상자의 선물 개수가 작았다. 매 쿼리마다 k번째로 큰 수를 찾으면 되니, 웰노운인 k번째 원소를 찾는 세그먼트 트리를 사용해주면 된다.

 

23762 - 배드민턴 복식 팀 만들기 (실제 대회 1B, 위 스코어보드에서는 A, G2)

DP 식은 자명하게 나오는데, 케이스 워크도 많고 해야할 것 (역추적, 정렬 전 인덱스 저장) 이 많아 코딩이 상당히 까다로웠다. 무지성 복붙을 한 결과 4300B짜리 코드로 AC를 받았다.

 

23765 - 다각형의 넓이 (실제 대회 1D, 위 스코어보드에서는 H, P3)

slah007 선배가 먼저 풀었는데, 아무리 봐도 \(O(N^3 K) \) 짜리 풀이밖에 모르겠어서 그냥 믿고 짰더니 맞았다.. 다행히도 정해는 \(O(N^3)\)인 것으로 보이며, 크누스 최적화의 원리를 이용해 푸는 방법도 있는 것 같다.

 

23763 - 괄호 문자열 이동하기 (실제 대회 2F-1C, 위 스코어보드에서는 I, P1)

이런 문제가 특히 코포에서 많이 나오는데, 간단한 형태로 바꾸고 다시 변환하는 것이 유효한 경우가 굉장히 많다. 따라서, ()()()..()() 형태로 바꾸고 변환하는 방법을 생각해보았다. 위 괄호 문자열의 특징은 여는 괄호는 항상 홀수 자리에, 닫는 괄호는 항상 짝수 자리에 있어야 한다는 점이다. 이를 이용해 원래 괄호 문자열을 쪼개고 한 겹씩 벗기면서 제자리에 있지 않는 괄호면 뒤집어주는 것을 반복하면 된다. 난 구현을 이상하게 해 TLE를 많이 받았다.

 

qjatn0120 선배는 A부터 풀어버렸기에 시간이 많이 부족했고, slah007 선배가 페널티 관리를 못한 점 + I를 약간 잘못 읽은 덕에 1등을 할 수 있었다. 이제 다시 Class 9 풀어야지..