2022 제7회 국민대학교 알고리즘 대회 후기

다 풀긴 했는데 버그잡느라 시간을 너무 많이 써서 좋은 상은 못 받을 것 같다.

 

3문제 나와서 각각 100점씩 총 300점 만점이었다.

---

1번은 그냥 쉬운 수학이었고, 각 값을 m으로 나눈 나머지별로 개수를 세고 각각 짝이 맞는 것끼리 가짓수를 곱해서 경우의 수를 구했다. 이때, 나머지가 0인 것이나 m이 짝수일 때 나머지가 m / 2인 것은 컴비네이션 2로 계산해야 한다.

---

2번이 제일 오래 뇌절했던 문제였는데 살짝 잘못 생각해서 시간을 오래 잡아먹었다. 그러고도 인덱스를 i를 써야되는데 j라고 써서...이거 찾느라 정말 오래 걸렸다. 하필 예제는 왜 맞는 건데;;

세 가지 경우로 나눠서 생각하면 된다.

 

내가 방문하려는 점 P(x, y)에 대해서

1. 점 P가 '마스크를 쓰는 점들을 모두 포함하는 가장 작은 직사각형' 내부에 포함된다면(경계포함) 점 P는 마스크를 쓰는 구간임이 확실하다. (=답이 0이다.)

2. 마스크를 쓰는 점들 모두와 점 P를 모두 포함하는 가장 작은 직사각형 내부에 마스크를 안 쓰는 점이 하나라도 있다면 점 P는 마스크를 안 쓰는 구간임이 확실하다. (=답이 1이다.)

3. 이 두 경우가 모두 아니라면 점 P는 마스크를 쓰는 구간인지 안 쓰는 구간인지 확정지을 수 없다. (=답이 2다.)

 

1번 케이스는 마스크를 쓰는 점들에 대해 최대 x좌표와 최대 y좌표를 구해서 직사각형을 구성하면 해결된다.

2번 케이스는 내가 방문하려는 점들과 마스크를 안 쓰는 점들을 y좌표로 정렬해서 스위핑해주면서 x좌표를 펜윅트리로 관리해줬다. 근데 알고보니 시간제한이 10초라서 펜윅 안쓰고 그냥 for 돌려도 500,000(방문하려는 점의 개수) * 10,000(x좌표의 범위) 정도라서 통과할 수도 있을 것 같다.. y좌표와 x좌표의 값의 범위가 같기 때문에 뭘 기준으로 정렬해도 효율이 달라지지는 않는다.

---

3번은 그냥 딱봐도 다익스트라 문제다. 어디서 어디까지 가라는데 가중치가 다르다니까 쉽게 다익스트라를 떠올릴 수 있다.

간선정보가 전형적인 그래프랑은 다르게 '통행하는 데 시간이 오래 걸리는 도로의 시작 좌표, 도착 좌표'와 '통행이 불가능한 도로의 시작 좌표, 도착 좌표'가 주어지는데, 나는 구현을 최대한 일반적인 다익스트라와 비슷하게 하기 위해 이걸 vector를 이용해 시작좌표만 알면 어디어디가 오래걸리고 갈 수 없는지를 저장했다. 말로 설명하려니 복잡한데 그냥 그래프를 만들었다고 이해하면 된다. 이 과정에서 역간선을 까먹고 안 저장해서 뇌절을 좀 했다..

그냥 취향에 맞게 구현하면 된다.

---

원래 1시간 전에 다풀고 놀다 나가는게 계획이었는데(1시간 동안 조기퇴실 불가) 망했다.

생각해보니 시간싸움에 강한 것 같지 않다. 원래 구상을 다 마치고 구현을 하는 편이기도 하고 시간을 신경쓰다보면 구현을 무지성으로 하고 허둥대면서 실수도 잦아서 오히려 더 꼬이는 것 같기도 하다.

 

예선이 없어서 그랬는지 작년보다 문제수도 많고 이 덕분에 문제 난이도를 좀 더 다양하게 낸 것 같다. 쉬운 문제 하나가 추가됐다고 보면 될 것 같은데 나머지 두 문제가 작년보다는 조금씩 더 어렵게 낸 것 같다.

 

1시 10분까지 입실이었는데 늦게 들어와도 봐주더라. 그래도 혹시 컷당할지 모르니 여유있게 가는게 좋다. 그리고 노트북이 잘 안되는 경우도 있어서 일찍 가야 노트북 교체도 편-안하게 할 수 있다.

 

작년과 달리 기념품은 주지 않았다. 사람수가 많아져서 그런가?