연습 250619
1. 2025 Latin America Championship
serin, SongC, 나 이렇게 한 팀으로 한 첫 팀연습이다. 여기에서 확인할 수 있다.
H번은 기본적으로 이 문제 와 같은데, 2개의 단계가 아니라 3개의 단계로 이루어져 있는 것이다. 풀이의 기본적인 맥락은 비슷하지만, 단계의 개수가 커지면서 casework가 늘어난다.
이때 분할정복을 사용하면 인생이 편해진다. 어디에서 변화가 일어나는지 정확하게 알 필요 없이, '왼쪽 / 오른쪽에서 +x만큼의 변화가 나타난다' 와 같이 간단하게 나타낼 수 있다. 세그먼트 트리 노드 합치는 감성으로 하면 된다.
나는 분할정복 할 생각을 못해서 그냥 케이스워킹을 열심히 했다. 심지어 정해보다 케이스워킹을 999배 더 해서 구현하는데 힘들었다.
J번은 구껍질에서 원 그리는 문제였는데, 재미있는 방법이 있어서 써본다. 특정 점에서 레이저를 쏘아서 구껍질을 평면으로 projection할 수 있다. 여기까지는 이산수학때 배웠다. 이때 특정 점을 지나는 원은 직선이 된다. 이건 이산수학 때 안 배웠다. 3차원 문제를 2차원으로 내리면 인생이 편해진다. 반전기하? 비슷하게 생겼다. 그런데 내 인생에서 3차원 기하를 풀 일은 없지 않을까 생각한다.
2. https://www.acmicpc.net/problem/22905
문자열 문제를 트리 위로 올린 뒤에 트리 dp를 하면 된다. suffix tree는 segment tree 급으로 강력하다.
3. https://www.acmicpc.net/problem/8235
suffix tree가 문자열의 다가 아니라는 것을 깨달았다. 문자열이 tree로 올라가면서 문자의 연속성?같은 정보들이 사라지기 때문에 트리에 올릴 때는 잘 생각해야 된다. 멋진 풀이 1, 멋진 풀이 2 가 있는 문제를 suffix tree + hld를 섞어서 스위핑하면서 풀었다 ㅋㅋ;
이번에 추가적으로 알게 된 사실인데, stack은 deque를 기반으로 작동하고, deque는 하나에 엄청나게 많은 메모리를 사용한다. stack 2백만개를 선언했더니 512mb가 터져버렸다. 앞으로는 stack 쓰지 말고 vector 쓰자.
4. 2024-2025 Russia Team Open, High School Programming Contest (VKOSHP XXV)
2번째 팀연습이다. https://codeforces.com/gym/105617에서 문제를 확인할 수 있다.
I번에서 말렸다! 단순 그리디이다. s_2에 있는 문자를 스위핑하면서 s_1에 매칭해야 할 suffix를 S, s_2에서 매칭해야 할 suffix를 T, s_2에서 본 문자들 중 매칭되지 않은 문자들을 관리하는 스택을 stk라고 하자. 아래 2가지를 관찰해야 한다.
- 스택이 비어있는 경우 S의 첫글자와 T의 첫글자가 같으면 둘이 매칭해주는 것이 최적이다.
- 스택에 같은 글자가 2개 연속으로 들어오면 제거하는 것이 최적이다.
그리디 관찰을 잘하자!
H번은 문자열 문제이다. 결론적으로는 주어진 문자열 P와 Q개의 쿼리 [l, r]이 들어올 때, P의 prefix이자 suffix이고 [l, r]을 포함하는 최소 길이 구간을 구하는 문제이다.
내 풀이는 [l, r]을 덮는 구간이 [s, e]라고 할 때, s에서 시작하는 최대 prefix substring이 e를 포함, e에서 시작하는 최대 suffix substring이 s를 포함해야 되어서, 2차원 평면 상에서 가로 길이가 1인 직사각형과 세로 길이 1인 직사각형의 교집합으로 나타나서 스위핑을 하면 된다는 것이었다.
정해는 조금 더 재미있다. s의 prefix이자 suffix인 문자열은 교집합을 잡아서 s의 prefix이자 suffix이다. 따라서 각 위치 i에 대해 [i, r_i] / [l_i, i]가 p의 prefix이자 suffix인 최대 r_i / 최소 l_i를 구한 뒤에, 주어지는 쿼리 [l, r]에 대해서 [i1, r_i1]가 [l, r]을 덮는 최대 i1, [l_i2, i2]가 [l, r]을 덮는 최소 i2를 구하면 [i1, i2]가 찾고자하는 구간이 된다.
문자열 문제는 정말 재미있는 것 같다!