[알고리즘] UCPC 2023 Open Contest

더 이상 UCPC에 나갈 수 없어 오픈콘테스트에 참여했다.

 

A 체육은 코딩과목입니다.

예선 A가 가장 쉽다는 것은 전통이다. 그냥 문제에서 주어진 내용을 구현하면 된다.

 

B 물류 창고

MST?생각하다가 트리 DP인가? 하다가 포기했다.

 https://codeforces.com/contest/1825/problem/D2 랑 비슷하다고 느꼈는데 에디토리얼 보니까 작은거 큰거...

 

C 차량 모듈 제작

얘가 MST문제였다. 그래서 B는 MST가 아닐 것이라는 믿음을 가지고 포기했다. 갑자기 두 원을 포함하는 체인의 길이를 구하는 방법이 생각이 안나서 https://www.youtube.com/watch?v=25ARSNtiN5k 보고 겨우 풀었다. ㅋㅋ

 

여담으로 예제 3번 그림이 3개의 기어를 연결한거로 헷갈려서 좀 고생했다.

 

D 더 흔한 타일 색칠 문제

정말 쉬운 던져주는 문제 같은데 문제 이해를 잘못해서 풀지 못했다. ㅋㅋ 꼭 다시 칠하기 전 배열에 존재하는 KxK로만 만드는게 아니었다. ㅋㅋㅋ 우연찮게도 나의 풀이가 예제를 통과해서 맞왜틀만 하다가 포기했다. 아무튼 맞았음

 

E 반전수

뭔가 가장 어려울 것 같고 논문이 있을법 해서 열심히 검색하다가 포기했다.

 

F 응원단

처음엔 덱으로 접근하려다가 가로, 세로 모두 이동이 있고 S쿼리때문에 아닌 것 같았다. 그러다가 나중에 $(1, 1), (1, 2), (2, 1), (2, 2)$만 움직여도 된다는 사실을 깨닫고 구현을 시작했으나 S쿼리를 해결하지 못해서 못 풀었다. 내가 잘 못 푼 건지 원래 그런건지 구현이 좀 빡셌다.

 

G 은하 온라인 마케팅 프로젝트

문제를 보지도 않았다.

 

H 팔찌

문제를 보지도 않았다. 들리는 말에 의하면 푸는데 현대대수가 들어간다는데 나중에 풀어봐야겠다.

 

I 자석

전에 코포에서 구간의 차이를 가지고 최대/최소를 구하는 문제에 한번 데여봐서 잘 풀었다. D에서 삽질하다가 36분에 솔브했는데 실제로 걸린 시간은 5분정도인듯?

 

J 다섯 용사의 검

문제를 보지도 않았다.

 

K 세미나 배정

A, D, I 다음으로 솔브수가 많아서 도전해봤는데 내가 가장 약한 유형이었다. 최대/최소 구하는 문제니 이분탐색 쓸 것 같고 스케줄링 비슷하게 풀면 될 것 같았는데 실패했다. 아직도 풀이를 모른다.

 

---

본선 컷이 7솔이던데 정말 고인 것 같다. 나만 어려웠나..

그래도 문제들은 재밌었다. 내년엔 콜포태 한번 도전해봐야겠다.