PS/오늘의 PS

오늘의 PS (19) - 220630

leo020630 2022. 7. 1. 05:16

오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: https://www.acmicpc.net/category/detail/2355

 

2020 Sogang Programming Contest (Master)

 

www.acmicpc.net

순서를 섞었기 때문에 실제 대회 번호와는 차이가 있다. 우선은 내가 푼 순서대로 정리할 예정이다.

 

20300 - 서강근육맨 (실제 대회 B, 위 스코어보드에서는 C)

A, B가 바로 풀 문제는 아닌 것 같아 C를 잡았다. 짝수일 때는 정렬해준 후 맨 앞과 맨 뒤를 차례대로 매칭해주면 되는데, 홀수일 때는 잘 생각이 나지 않는다. 친절하게도, 제곱 풀이가 가능한 제한이기 때문에 하나를 빼준 후 짝수일 때와 똑같이 하면 된다.

 

20299 - 3대 측정 (실제 대회 A, 위 스코어보드에서는 G)

이후 쉬워보이는 문제를 잡았다. 브론즈 문제이니 풀이는 생략한다.

 

20301 - 반전 요세푸스 (실제 대회 C, 위 스코어보드에서는 F)

그냥 요세푸스가 queue이니 반전 요세푸스는 deque일 것이라는 추측을 한 후 바로 짜서 맞았다.

 

20303 - 할로윈의 양아치 (실제 대회 E, 위 스코어보드에서는 A)

이후 A부터 차례대로 문제를 읽었는데, 그냥 냅색이라 바로 짰다.

 

20302 - 민트 초코 (실제 대회 D, 위 스코어보드에서는 D)

이후 D가 풀렸길래 보러 갔다. 각 소인수 별 등장 횟수를 체크해준 후 나눗셈이 곱셈보다 많은 경우가 있으면 불가능하다. 약간의 예외 처리가 필요한데 이를 하지 않아 한번 틀렸다.

 

20305 - 피보나치와 수열과 쿼리 (실제 대회 G, 위 스코어보드에서는 B)

이후 B를 보다 풀이가 생각나 짰다. 전형적이지 않은 좋은 쿼리 문제라고 생각했다.

 

20304 - 비밀번호 제작 (실제 대회 F, 위 스코어보드에서는 H)

주어진 정점들을 시작으로 멀티 소스 BFS를 돌려주면 된다. 이렇게 말하니 별거 없어 보이는데, BFS의 특성을 잘 이해하고 있어야 정당성을 입증할 수 있어 꽤 어려운 문제라고 생각했다.

 

20306 - 블랙홀 (실제 대회 H, 위 스코어보드에서는 E)

이상의 문제를 40분만에 다 푼 후, 1시간 컷이 가능하겠다는 생각에 싱글벙글하며 E를 보러 갔다. 다 읽고 나니 E도 쉬웠다. 파라메트릭을 한 후 각 건물마다 볼록다각형에 포함되는지 \(O(logN)\)만에 판별해주면 문제를 해결할 수 있다. 이와 비슷한 문제를 최근에 풀었기에 바로 짜서 냈더니 틀렸다. 자꾸 틀리길래 1시간쯤 후에 답지를 살짝 까봤다. 그랬더니 첫 페이지에 파라메트릭은 어림도 없습니다~라는 멘트가 적혀 있었다. 답의 상한이 \(10^{18}\) 스케일이라 좌표가 long long 범위에 저장이 되지 않는 것이 이유였다. 파이썬을 쓰는 방법도 있지만, 익숙하지 않기에 그냥 정해를 생각해보기로 했다. 대충 각도 정렬을 한 후, 점과 직선 사이의 거리 공식을 쓰면 될 것 같아서 구현했다. 그리고 무수한 틀렸습니다의 감옥에 갇혔다. 위에는 12번밖에 나와있지 않지만, 연습 시간인 3시간이 지난 후에도 계속 냈다. 많은 양의 예외를 처리해준 후에야 (추가적인 18번의 틀렸습니다와 함께) 정답을 맞을 수 있었다. 구현 상 오버플로우와 각종 오류를 처리해야 할 부분이 많아서 어려운 문제인 것 같다.

 

오늘은 모비스 예선과 팀연습, 내일은 UCPC 예선이 있다. 잘 쳤으면 좋겠다.

'PS > 오늘의 PS' 카테고리의 다른 글

오늘의 PS (21) - 220716  (0) 2022.07.17
오늘의 PS (20) - 220708  (0) 2022.07.09
오늘의 PS (18) - 220629  (0) 2022.06.30
오늘의 PS (17) - 220627  (0) 2022.06.28
오늘의 PS (16) - 220625  (0) 2022.06.26