2024 IOI 멘토교육 3주차
IOI 2023 Day 1을 돌았다.
0:00 ~ 1:53(35 / 0 / 0 -> 35)
1, 2, 3번 문제를 읽고 이해했다. 1, 2, 3번 문제가 모두 어려워 보였기 때문에 1번 문제부터 천천히 고민해보기 시작했다.
1번 문제의 1, 2, 3번 섭테는 간단하게 해결할 수 있었고, 4번 섭테는 뭔가 더 아이디어가 필요할 것 같았다.
X의 오른쪽, Y의 왼쪽으로 얼마나 갈 것인지를 $O(N^2)$으로 모든 경우를 다 해 보고, 각 경우를 $O(logN)$에 처리하면 될 것 같았다.
각 경우에 대해서 선택해야 하는 값들을 작은 것부터 선택하는 그리디가 성립하기 때문에, 가장 작은 것 x개를 골랐을 때, 합이 K 이하가 되는 x의 최댓값을 구하면 된다. 이는 좌표 압축 + 세그먼트 트리로 구현할 수 있다.
처음에는 탑다운 방식으로 구현했는데, 시간초과가 나서 바텀업으로 고쳤더니 맞았다.
이 방법을 떠올리고 구현하는데 너무 많은 시간을 할애한 것 같다.
1:53 ~ 2:00(43 / 5 / 0 -> 48)
모든 문제의 풀이를 떠올리고 나중에 구현하는 방식은 내가 풀이를 떠올리는 방식이 온전치 않고, 최근 들어 구현 미스도 잦기 때문에 섭테를 빨리 하나씩 해결하기로 했다.
우선 1번 문제의 1번 섭테를 긁었다. 1번 섭테에서도 앞서 말한 그리디가 성립하므로, 최솟값부터 골라나가면 된다.
다음으로 2번 문제의 1번 섭테를 긁었다. D=3이므로 완전 그래프라는 것을 알 수 있고, 0부터 N-1의 순열을 아무거나 반환하면 된다.
2:00 ~ 2:14(43 / 15 / 0 -> 58)
2번 문제의 2번 섭테를 긁었다.
D=2일 때는 직관적으로 최장 경로의 길이가 N이라는 것을 알 수 있다.
노드들을 순서대로 합쳐나간다고 생각하자. 지금까지 합친 노드의 경로의 양 끝점을 A, B라 하고, 새로운 정점을 C라 하면 A, C 또는 B, C 사이에 간선이 무조건 존재할 것이므로, 이를 합쳐주는 방식으로 구현하면 된다.
2:14 ~ 2:25 (43 / 15 / 6 -> 64)
3번 문제의 1번 섭테를 긁었다.
생각을 잘못해서 좀 꼬였다.
나무의 위치를 $(a, b)$라고 하면, 답은 $N^2-min(a+1, N-a) \times min(b+1, N-b)$이다.
2:25 ~ 2:42 (43 / 15 / 20 -> 78)
3번 문제에서 $N \le 500$일 때 모든 빈칸을 사용하는 것이 가능한지 판별하는 섭테를 풀었다.
불가능한 경우는 두 가지로, 막힌 칸의 좌우나 양옆에 안 막힌 칸이 있거나, 두 안 막힌 칸의 두 직각 경로에 모두 막힌 칸이 있는 것이다.
이를 Naive하게 판별하면 된다.
2:42 ~ 3:01 (43 / 40 / 20 -> 103)
2번 문제에서 3번 섭테를 긁었다.
3번 섭테부터 힘들 것이라 예상했지만, 실제로는 간단한 방법으로 풀렸다.
세 경로가 있을 때, 각 경로의 한 끝점을 A, B, C라고 하면 둘 중 하나는 병합할 수 있다.
이 과정을 반복하면 두 경로만 남기 때문에, 둘 중 더 큰 경로를 쓰면 $\lceil N/2 \rceil$ 이상임을 보장할 수 있다.
3:01 ~ 3:42 (43 / 40 / 29.5 -> 112.5)
3번 문제에서 $N \le 2000$일 때 모든 빈칸을 사용하는 것이 가능한지 판별하는 섭테를 풀었다.
이 때부터 본격적으로 말렸다.(물론 앞에서도 수많은 삽질을 했다.)
어떤 안 막힌 칸 $(a, b)$에 대해 $(a, b)$에서 갈 수 없는 칸의 조건을 생각해보자.
어떤 막힌 칸 $(a, c)$나 $(c, b)$가 있어서 그 위치를 넘어가는 범위로는 당연히 갈 수 없을 것이다.
또한, 오른쪽의 막힌 칸 $(a, d)$와 아래쪽의 막힌 칸 $(c, b)$에 대해서, $(c, d)$의 오른쪽 아래 칸은 모두 갈 수 없을 것이다.
이 과정을 네 가지 방향에 대해 반복하면 누적합을 이용해 빠르게 판단할 수 있다.
3:42 ~ 4:36(43 / 40 / 35.5 -> 118.5)
3번 문제의 전체 풀이로 갈 법한 풀이를 떠올렸지만, 모든 풀이에서 $N=3$일 때 반례가 등장해서 좌절감을 느꼈다.
결국 2번 섭테를 긁기로 했다.
3번 문제의 섭테를 거의 풀지 못한 것이 매우 아쉬웠다.
4:36 ~ 5:00(43 / 40 / 35.5 -> 118.5)
아무것도 못했다.
결론
최종 점수 43 + 40 + 35.5 = 118.5점으로 끝났다.
확실히 기존 세트와 난이도 분포가 달라졌고, 어려운 문제 셋이었던 같다.
나는 쉬운 문제를 빨리 풀고 어려운 문제의 섭테를 생각하는 편이기 때문에, 이렇게 모든 문제가 어려운 셋은 잘 못 푸는 것 같다.
확실히 사고하고 문제를 해결하는 스킬이 부족한 것 같다.
1번은 어려운 문제였다.
2번은 어려운 문제였다.
3번은 어려운 문제였다.
섭테를 더 긁었으면 좋을 것 같다는 아쉬움이 남는다.
업솔빙
2번 문제를 풀이를 보고 업솔빙에 성공했다.
40점 풀이를 확장시켜서 답을 찾는 방법을 찾는다면 60점을 얻을 수 있고, 여기서 쿼리 횟수를 줄여 85점을 줄이는 것은 간단하다.
100점 풀이는 훨씬 어렵다.
우선 60점 풀이부터 생각해보자.
40점 풀이처럼 2N번의 쿼리를 사용해 모든 정점을 두 개의 경로로 쪼갰다고 생각하자.
각 두 경로를 s1~e1, s2~e2라고 하자.
이 때 s1 또는 e1과 s2 또는 e2 사이에 간선이 있다면, 답은 N이 될 것이다.
그 사이에 간선이 없다면, s1~e1과 s2~e2는 각각 사이클을 이룰 것이다.
그러면 s1~e1과 s2~e2 사이에 간선이 한 개라도 있다면, 그 간선을 기준으로 사이클을 잘라서 답을 N으로 만들 수 있고, 그렇지 않다면 두 경로 중 더 긴 것이 답이 된다.
이를 나이브하게 $N^2$번의 쿼리로 해결하면 60점을 받을 수 있고, 이분 탐색을 통해 간선 확인 과정을 $2logN$번의 쿼리로 해결하면 85점을 받을 수 있다.
100점을 받기 위해서는 N=256일 때 최대 400개의 쿼리를 사용할 수 있으므로, 2N번의 쿼리를 사용해 두 개의 경로를 구성하는 과정을 개선시켜야 한다.
사용해야 하는 쿼리의 횟수가 2N인 이유는 한 개의 정점을 새로 두 경로 중 하나에 포함시키기 위해 두 번의 쿼리를 사용하기 때문이다.
이를 개선시키기 위해 두 개의 정점을 새로 두 경로 중 하나에 포함시키기 위해 세 번의 쿼리를 사용할 것이다.
지금까지 관리하는 두 개의 경로의 끝점을 e1, e2라고 하자.(e2가 존재하지 않을 수도 있다.)
이 때 무조건 e1과 e2는 연결되지 않도록 관리할 것이다.
경우를 잘 나눠서 쿼리를 날리면 새로 들어온 정점 a, b을 두 경로에 포함시킬 수 있다.
1. e2가 존재하지 않는 경우
쿼리 1. e1, a가 연결되었는가?
True의 경우: 쿼리 2. a, b가 연결되었는가?
True의 경우 : e1에 a, b 추가
False의 경우 : e1에 a 추가, e2에 b 추가
False의 경우: 쿼리 2. a, b가 연결되었는가?
True의 경우 : e2에 b, a 추가
False의 경우 : e1에 b 추가, e2에 a 추가
2. e2가 존재하는 경우
쿼리 1. a, b가 연결되었는가?
True의 경우 : 쿼리 2. e1, a가 연결되었는가?
True의 경우 : 쿼리 3. e2, b가 연결되었는가?
True의 경우 : e1과 e2 사이에 a, b 넣고 merge
False의 경우 : e1에 a, b 추가
False의 경우 : e1, e2가 연결 안됨, e1, a가 연결 안됨 -> e2, a가 연결
쿼리 3. e1, b가 연결되었는가?
True의 경우 : e1, e2 사이에 b, a 넣고 merge
False의 경우 : e2에 a, b 추가
False의 경우 : 쿼리 2. e1, a가 연결되었는가?
True의 경우 : 쿼리 3. e2, b가 연결되었는가?
True의 경우 : e1에 a 추가, e2에 b 추가
False의 경우 : e1에 b 추가, e2에 a 추가(*중요*)
False의 경우 : e1에 b 추가, e2에 a 추가
위와 같은 개노가다를 뛰어 주면 모든 경우에 대해 e1, e2가 연결되지 않도록 관리하면서 세 번의 쿼리로 두 개의 정점을 새로 포함시킬 수 있다.
(*중요*)라고 써 있는 줄이 가장 복잡하다.
논리적으로 잘 따져주기만 하면 구현이 길지만 어렵진 않다.