쓰라는 궁극의 웰노운 알고리즘은 버리고 왜 이런 글을 올렸냐 하면, PS의 공부법에 대한 회의감에 의해 그렇다고 볼 수 있다. 보통 PS '공부'를 한다고 하면, 알고리즘을 배우고 짜보고, 혹은 대회를 전부 업솔빙해보거나 문제를 푸는 등의 행동을 할 수 있다. 그런데 사실 이런 공부법을 취한다면 구현이 굉장히 오래 걸리거나 하는 등의 문제에 의해 효율이 낮아지는 경우가 많다고 생각한다. 물론, 구현도 굉장히 중요한 부분이다. PS를 두 개의 부분으로 나누면 '발상'과 '구현'일 정도이며, 구현이 따라주지 않는다면 아무것도 불가능하다. 그런데 사실, '발상' 단계와 '구현' 단계는 차이점이 있다. '발상'은 일단 일반적인 직관에 따르면, 주로 문제의 난이도를 결정한다. 물론 오직 구현만으로 어려운 문제들도 있긴 하다. 5373번: 큐빙 (acmicpc.net)예전에 플래를 많이 푼 순부터 미는 연습을 하다가(얼마 안가 던졌다) 마주친 극악의 구현 문제이다.
5373번: 큐빙
각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란
www.acmicpc.net
그런데 결국 구현에는 핵심적인 특성이 있는데, "시간을 적당히 박으면 무조건 구현 가능하다는 점"이다. 그런데, "발상"은 그렇지 않다. 어떤 아이디어를 발상하기 위해서는 천문학적인 시간을 들이부어야 할 수도 있다. 물론 오직 구현난이도만으로 문제는 얼마든지 어려울 수 있겠지만, 사실 대부분의 대회들은 "발상"의 난이도를 높여서 난이도 조절을 한다. 그래서 사실은 "발상력"을 높이는 것이 중요하다고 생각한다. 발상을 하지 못하면 애초에 구현을 못하니까...
그래서 나는 뇌풀이 일지를 작성하기로 했다. 여러 문제들의 "이론적인 풀이"를 발상하거나 공부하고, 그걸 단순히 정리하는 것 뿐이다. 사실, 딱히 구현력이 오르지 않을 걱정을 하지 않아도 되는 이유가 내가 뇌풀이 일지만 쓰는게 아니기 때문이다. 평소에도 여러 셋을 돌고 문제도 풀 것이기 때문에...
아무튼, 오늘은 IOI 2023, IOI 2022 문제들의 뇌풀이를 공부할 예정이다.
IOI 2023 day 1 1번
29745번: Closing Time (acmicpc.net)
29745번: Closing Time
C++17, C++20, C++17 (Clang), C++20 (Clang)
www.acmicpc.net
문제를 간략히 요약하...기엔 문제의 상황이 다소 complicated해서 설명할 자신이 없다. 그냥 바로 내가 이해한 바를 작성해보겠다.
우선, 직선일 때 문제가 어떻게 해결되는지를 관찰해보는 것은 도움이 된다. 일단, 먼저 각 정점들마다 해당 정점에 1개의 중심 노드가 도달할 수 있도록 하기 위한 최소한의 비용, 두 중심 노드 모두 도달할 수 있도록 하기 위한 최소비용들을 계산할 수 있다. 이제 한번 전체 직선을 중심 노드들 사이의 경로와, 그렇지 않은 부분으로 나누어보자. 만약 우리가 각각에 대해서 점수를 k만큼 획득하기 위한 최소 비용을 전부 계산해두었다고 생각해보자. 아주 단순하게 생각해보면, 이 두 테이블을 통해서 "전체 문제" 점수가 K가 되도록 하기 위한 비용의 최솟값을 계산할 수 있다는 것은 조금 이상해보인다. 예를 들어, 다음과 같은 상황이 있을 수 있기 때문이다:
즉, X-Y 구간 내에서는 X가 파란색에 의해 선택되지 않았는데, 그 바깥 구간에서 X보다 선행되는 정점이 파란색에 의해 선택되어, 같은 색의 구간이 연속해야 한다는 조건을 어기는 경우를 생각해볼 수 있다. 그런데, 잘 생각해보면 이런 현상이 발생할지라도 단순히 무시할 수 있다. 왜냐하면 위의 점수가 k라고 할 때, 구간 밖의 파란 부분을 내부의 파란 부분과 연결시킨 최적해가 존재하기 때문에, 동일한 점수하에서 더 나은 비용을 요구하는 해가 존재하게 된다. 단순히 말하면 그냥 이런 상황이 고려되기 때문이라고 할 수 있다.
따라서 안과 밖 각각에 대해 문제를 독립적으로 풀어준 뒤, 단순히 두 배열을 적당히 합쳐주면 그것이 전체 문제의 최적해가 됨을 알 수 있다. 특히, "구간 밖"을 "왼쪽"과 "오른쪽"으로 나누어도 상관없으며, 사실 충분히 빠른 시간복잡도를 위해서는 이 방법이 유효하다.
우선, 구간 안쪽의 경우에는 비교적 자명하다. 내부에서 두 중심노드들에 의해 겹치는 부분의 가짓수에 따라 계산해주기만 하면 충분하다. 사실 구간 바깥도 별반 차이가 없는데, 어느 한 쪽에서 나올 수 있는 상태의 수는 O(n^2)이기 때문이다. 따라서 모든 구간에 대해 답을 빠르게 구할 수 있고, 따라서 전체 문제의 답도 빠르게 구할 수 있다.
이러한 관찰은 굉장히 쓸만한데, 트리에 대해서도 비슷한 방향으로 풀이가 흘러간다. 왜냐하면 "경로 안"과 "경로 밖"을 나누어 생각하는 논의는 여전히 통하기 때문이다. 경로 안에 대해서는 이전에 풀었던 것과 똑같이 풀면 되겠지만, 이번에는 O(nlogn)에 해결해야 할 것이다. 경로 밖의 경우는 사실 조금 complicated하다. 일단 경로 안쪽부터 해보자.
경로 안쪽에서 일어나는 일에 대해 생각해보면, 겹치는 부분과, 그에 의해 나뉘는 왼쪽과 오른쪽이 있을 것이다. 또한, 잘 생각해보면 각 왼쪽과 오른쪽을 확장시키는 것은 서로에게 아무런 영향이 없다. 즉, 처음에는 모든 구간이 겹치는 부분이라 한 뒤에, 왼쪽과 오른쪽중 차이를 최대화하는 부분들부터 안 겹치도록 바꾸어주면 그게 모든 k에 대해 최적해임을 알 수 있으며, 추가로 "그로 인해 만들어지는, 점수에 따른 이득의 배열이 convex함 또한 알 수 있는데, 왜냐하면 k가 감소할때마다 이득의 감소량이 감소함은 자명하기 때문이다.".
이제 경로 바깥에 대해 생각해보자. 솔직히 이 아이디어가 가장 인상깊었는데, 여기에서는 각 정점들을 두 그룹으로 나눈다. 일단 a_i가 정점 i로부터 1의 점수를 얻기 위한 비용, b_i가 정점 i로부터 2의 점수를 얻기 위한 비용이라고 하자. 그리고 모든 정점들을
2a_i<b_i인 케이스와, 그렇지 않은 케이스로 나누자.
첫 번째 케이스의 정점들에 대해서는, 단순한 그리디가 성립한다. 각 정점들에 대해서 a_i, b_i-a_i를 정렬한 뒤 작은것부터 뽑으면 어떠한 모순도 발생하지 않음을 쉽게 확인할 수 있다.
두 번째 케이스의 정점들에 대해서 생각해보면, 어떤 정점에서부터 1의 점수를 얻는 경우가 많아야 하나밖에 없음을 알 수 있다. 만약 정점 x,y가 1의 점수만을 받았고, a_x<=a_y였다고 하자. 그럼 우리는 단순히 정점 y를 버리고, x로부터 2의 점수를 얻으면 더 나은 최적해가 완성되기 때문이다. 이런 성질에 입각해서 답을 구해줄 수 있다.
이렇게 우리는 총 3개의 최적해 배열을 얻었다: 경로 내부의 테이블, 경로밖 케이스 1의 테이블, 나머지.
단지 약간의 의구심이 들 수 있는 것은, 경로밖의 정점들도 저렇게 두 그룹으로 나누어도 되냐는 것이다. 그런데, 사실 정말로 어떻게 정점들을 몇몇 그룹으로 분할하고, 문제를 해결해도 별 상관이 없다. 여전히 어떤 정점이 점수를 벌고, 그 부모가 벌지 못하는 상황이면 부모쪽으로 점수를 부여해줌으로써 이득을 볼 수 있기 때문이며, 최소한 그 상황만큼은 배열들을 잘 합쳤다는 가정하에 고려될 것이기 때문이다.
그렇다면, 배열들을 어떻게 합칠까? 잘 생각해보면, 첫 번째 테이블은 convex했다. 여기에 추가적으로 두번째 테이블도 convex한데, 그 이유는 이 경우 또한 k를 늘릴때마다 더해지는 비용이 증가하기 때문이다. 두 convex한 테이블은 사실 잘 생각해보면 minkowski sum의 아이디어를 빌려서 빠르게 합칠 수 있음을 알 수 있다. 따라서 남은 것은 두 테이블을 합치는거고, 사실 굳이 합칠 필요도 없이 투포인터로 풀 수 있다. 따라서 전체 문제가 풀린다.
흠...이렇게 써보고 나니 짤만해보이긴 하는데 나중에 시간나면 구현연습이나 해야겠다. 많은 그리디와 dp적인 관찰이 굉장히 중요한 문제였던 것 같다.
IOI 2023 day 1 2번
29746번: Longest Trip (acmicpc.net)
29746번: Longest Trip
C++17, C++20, C++17 (Clang), C++20 (Clang)
www.acmicpc.net
사실 이 문제는 이미 푼 상태이다. 셋을 돌면서 이녀석의 85점 풀이를 떠올리는데 한시간 반쯤 걸렸고 짜는데만 거의 두세시간은 걸리고 60점으로 폭사했던게 기억에 남는다. 심지어 셋 다 돌고 샤워하다가 대충 생각해서 100점풀이를 발견했어서... 뭐 디버깅해서 결국 100점으로 업솔빙하긴 했지만
근데 생각해보니 이미 푼 문제인데 굳이 풀이를 적을 필요가 있나...?
IOI 2023 day 1 3번
29747번: Soccer Stadium (acmicpc.net)
29747번: Soccer Stadium
Nagyerdő is a square-shaped forest located in the city of Debrecen, which can be modeled as an $N \times N$ grid of cells. The rows of the grid are numbered from $0$ to $N - 1$ from north to south, and the columns are numbered from $0$ to $N - 1$ from wes
www.acmicpc.net
흠... 방금 뭔가 풀이를 이해하고 왔는데 뭔가 대충 Treatment Project랑 비슷한 결의 문제인 것 같다. 사실 아직 Treatment Project의 풀이도 모르긴 하는데... 근데 뭔가 암튼 비슷하다.
일단, 해당 문제를 풀기 위해서는 조건을 만족하는 영역의 필요충분조건이 무엇인지를 규명해야 한다. 그러한 영역의 조건은 다음과 같이 나타난다:
1. 각 행과 영역의 교집합은 존재하지 않거나, 정확히 한 줄만 존재한다.
2. 전체 영역은 "대충 바이토닉"하다. 어느 행까지는 지속적으로 팽창되다가, 그 이후에는 천천히 수축된다.
3. '각 행들과 영역의 교집합'(i번째 행에 대해 이를 S_i라고 하겠다.)들은 쌍마다 포함관계이다.
바로 풀태만 설명해도 될 것 같아서 그렇게 한다... 즉 모든 영역들은 몇개의 영역들의 합집합으로 나타나게 된다. 그리고 3번 성질을 조금 더 깊게 고찰해보면, 전체 영역은 사실은 직사각형 몇개의 합집합인데, 이때 중요한 사실은 직사각형 하나의 가로폭이 수축할 때 세로폭은 팽창하는 구조라는 사실이다. 즉, "각 직사각형들을 정점으로 하는 DAG에서의 DP"를 생각할 수 있고, 이걸 최적화하는게 문제의 핵심이 된다. 일단 직사각형 정점에 대해서 생각해보자. 굉장히 나이브하게 보면 무려 n^4개의 정점이 있게 된다(!). 그러나, 잘 생각해보면 우리는 이른바 "꽉 찬" 직사각형들만 다루면 충분하다는 사실을 알 수 있고, 사실 잘 생각해보면 이런 "꽉 찬" 직사각형은 많아야 O(n^2)개인데, 위쪽 모서리가 끼어있을 수 있는 부분을 기반으로 counting하면 자명하다.
이제 이러한 정점들로 이루어진 특정한 그래프에 대해서 dp를 적당히 돌릴 것인데, 그렇다면 간선의 개수는 어떻게 되는가? 일단 전이를 하는 경우는 다음과 같다: 어떤 직사각형에 대해서 그 위쪽 모서리를 생각하고, 그 바로 위쪽 행을 생각하자. 위쪽 모서리가 나타내는 구간에 포함되며, 최대한 넓은 구간을 가지는 그런 구간들을 생각할 수 있다. 그 부분을 위쪽 모서리로 가지는 "꽉 찬" 직사각형들은 정확히 하나씩 존재할 것이며, 따라서 각 직사각형들마다 O(n)개씩 존재할 여지가 있다. 그러나 이는 O(n^3)의 전이를 나타내기 때문에 과도하게 느리다. 다른 방법을 찾아야 할까?
사실, 놀랍게도 이러한 전이는 O(n^2)번 발생한다. 왜냐하면 전이의 방향을 반대로 생각해서, 어떤 "꽉 찬" 직사각형에 전이할 수 있는 직사각형은 정확히 하나이기 때문이다. 일종의 트리와 같은 구조를 생각하면 될 것 같다... 아무튼, 따라서 우리는 제곱개의 정점과 상태를 가지게 되었다!
추가로, "꽉 찬 직사각형"을 찾아내기 위해서는 2차원 누적합과 이분탐색을 시도해볼 수 있을 것이다. 상태전이를 찾아내는건 음...어케하지 근데 뭔가 대충 될 것 같다. 생각해보니까 걍 나이브하게 짜도 될 것 같은데 더블카운팅적 논의에 의해
흠 이건 구현도 막상 어렵진 않아보이긴 해서 시간날때 짜봐야겠다.
어...원래는 2023 day2를 쓸 생각이긴 했는데 그냥 돌아볼까도 고민하고 있어서 그냥 2022 day 1을 쓰기로 했다.
1. 25438번: 메기 농장 (acmicpc.net)
25438번: 메기 농장
부 뎅클렉은 메기 양어장을 가지고 있다. 양어장은 $N \times N$ 격자칸 모양이다. 격자의 칸들은 같은 크기의 정사각형이다. 격자의 열들은 서쪽에서 동쪽으로 $0$부터 $N - 1$까지 번호가 붙어 있고,
www.acmicpc.net
갠적으로 재밌어보여서 풀고 있다. 풀이 찾으면 올릴듯
2. 25439번: 죄수들의 도전 (acmicpc.net)
25439번: 죄수들의 도전
만약 테스트 케이스 중 어느 경우에서든, devise_strategy가 리턴한 배열이 정확한 전략을 나타내지 않는 경우, 이 서브태스크에 대해서 당신은 $0$점을 얻는다. 서브태스크 3은 부분 점수가 있다. 이
www.acmicpc.net
대충 옛날에 뇌풀이까지 (아마도) 만들고 끝냈던 문제였던 것 같다. 아마 구현하다가 던졌으니까 확실히 풀이는 맞을...것이다. 근데 귀찮다
25440번: 송신탑
자카르타에는 $N$개의 송신탑이 있다. 송신탑들은 일직선 상에 위치하며 왼쪽에서 오른쪽으로 $0$부터 $N - 1$까지 번호가 붙어 있다. $0 \le i \le N - 1$인 각 $i$에 대해, 송신탑 $i$의 높이는 $H[i]$ 미터
www.acmicpc.net
asdf
