저번에 예고하였던 대로, 궁극의 웰노운 알고리즘도 작성할 겸 PS일지도 쓸 겸 글을 작성하게 되었다. 총 2개의 ARC와, 총 1개의 다3 수학문제를 풀었으며, 한 개의 요코하마 셋을 돌았다(이전에 내걸었던 공약에 비해 한 것이 많지 않아보인다면, 사실이다. 다만 지난주동안 바빴어서 어쩔 수 없었다.). 또한, 앞으로는 그냥 PS일지에다가 궁극의 웰노운 알고리즘을 작성할 예정이다.
암튼, 일단은 궁극의 웰노운 알고리즘부터 설명을 하겠다.
1. Lagrange Interpolation
사실, 이 주제는 별로 언노운은 아니고 아마 많은 사람들이 알고 있는 테크닉일 것이라고 생각한다. 그냥 핵심부터 말하자면, d차 다항식은 점 d+1개가 주어질 시 유일하게 결정된다는 것이다. 해당 글에서는 Lagrange Interpolation을 PS적으로 어떻게 활용할 수 있는지에 대해 다룬다.
라그랑주 보간법으로 풀 수 있는 문제중에는 다음이 있다:
\( \sum_{k=1}^n \binom{ak+b}{d} \)를 \( O(d)^2 \)만에 구하기
일단 기본적으로 여러 수학적인 도구들이 없다면 위의 값을 아주 나이브하게 계산하는 것은 대략적으로 \( O(nd) \)정도의 시간복잡도를 소요할 것 처럼 보이며, 설령 베르누이 수를 통해 파울하버 공식을 이용하여 답을 구한다고 치면 비록 d에 대한 다항시간 풀이를 얻긴 하겠지만, 그런 끔찍한 구현을 하고 싶은 사람은 많지 않을 것이라고 생각한다.
그렇다면, 라그랑주 보간법은 어떻게 이 문제를 \( O(d)^2 \)만에 구한다는 것일까?
한 가지 중요한 관찰이 필요하다. 다항식을 유한개 더한 것이 다항식임은 자명하다. 그런데, 재미있는 것은 다항식의 "부분합" 또한 다항식이라는 것이다. 즉, \( P(x) \)가 다항식이라고 할 때, \( \sum_{i=1}^x P(i) \)는 x에 대한 다항식이다. 이제, 아마 이 글의 독자들은 어떻게 위의 문제를 해결할 것인지 알 수 있을 것이다. 단순히, \( \sum_{k=1}^n \binom{ak+b}{d} \)를 n:1~d+2까지 계산해준 다음, 보간법을 돌리면 n에 임의의 값을 대입한 것을 알아낼 수 있다.
당연히, 위의 예시를 안다면 독자들은 \( \sum_{k=1}^n k^d \)의 값을 계산하는 방법 또한 알 수 있을 것이다. 물론 이 문제같은 경우에는 다룰 수 있는 여러가지 방법이 있고, 파울하버 공식은 그중 하나겠지만, 굳이 이 값을 계산하는데에 많은 사고를 소요하고 싶지 않은 사람들도 있을 것이다. 만약 d가 충분히 작다면, 그냥 보간법을 돌리면 문제가 아주 손쉽게 해결된다!
지금 보니까 보간법을 O(nlog^2n)정도에 돌리는 방법도 있다는 듯 한데, 그건 굳이 읽어보기 귀찮아서 두번째 포스팅으로 미루거나 그냥 나만 읽어보거나 그것도 아니라면 템플릿에만 박아두거나 하겠다. 관심있으면 직접 찾아서 읽어보길
2. ARC
2.1. ARC 105
A. 가능한 모든 조합을 신경써보면 된다.
B. 앳코 그레이급의 문제치고는 살짝 어려워서 의외였던 문제(물론 많이 어렵진 않다). 답이 전체의 gcd임을 어렵지 않게 보일 수 있다.
C. 이건...생각보다 쉽지 않았다. 일단, 낙타의 수가 많아야 8이기 때문에, 가능한 모든 낙타의 순서를 시도해볼 수 있다. 이제, 낙타 i,j에 대해서 이 두 낙타가 얼마나 떨어져 있어야 하는지를, 적절한 전처리를 통해 알아낼 수 있다. 이를 통해서 완전그래프상에서 각 정점들에 가중치를 매겨주고, 첫 번째 낙타부터 마지막 낙타 사이의 거리가 최소 얼마여야 하는가같은걸 계산하는 방식으로 풀린다고 한다. 사실 나도 에디토리얼을 봐서 잘 모른다.
D. 셋을 돌 때에는 첫 가방에서 몇개를 가져갈지 정할 수 있는줄 알아서 풀지 못했는데, 근데 알고보니 가방에서 가져갈때는 전부 가져가는거였다...그러면 그냥 한쪽 접시에 몰아주면 xor의 값이 과반수를 넘길 수 있다는 느낌의 논리를 사용해서 문제를 풀 수 있다.
2.2. ARC 106
A. 로그제곱에 풀린다.
B. 연결 컴포넌트 내부의 값들의 합이 변하지 않는다는 전제하에 원하는 배치로 바꿀 수 있으므로, 각 컴포넌트의 값의 합이 변하지 않았는지 체크하면 된다.
C. 자명한 constructive.
D. 꽤 흥미로운 문제였는데, 일단 sum[i]를, (a_j)^i들의 전체합으로 정의한다. 이제 구하고자 하는 식을 잘 살펴보면, sum[i]들 몇개의 곱의 합으로 나타내어질 수 있음을 알 수 있다. 이를 실제로 계산하면 문제가 풀린다.
E. 문제를 읽어보면, 플로우 모델링을 얻을 수 있다. 여기에서 정점을 몇개의 부분정점으로 쪼개고 나면, 그냥 매칭을 찾는 문제로 환원할 수 있다. 이제 홀의 정리의 조건이 성립하는지만 체크하면 되고, 이는 zeta transform으로 계산할 수 있다.
3. Different Summands Counting
https://www.acmicpc.net/problem/18969
일단, 양수라는 조건이 짜증나니까 n에서 m을 빼고 시작하자.
서로다른 수의 개수의 총합을 세기 위해서는, i가 사용되는 배치의 개수를 모든 i에 대해 합하면 된다는 사실을 알 수 있다.
포함배제의 원리를 적용하면, 이는 결국 i가 사용되는 배치의 개수-i가 두 번 이상 사용되는 배치의 개수 + i가 세 번 이상 사용되는 배치의 개수 -...와 같은 식으로 적어줄 수 있다.
k:1~m에 대해서, 모든 i에 대해서 i가 k번 이상 사용되는 배치의 개수의 총합을 계산할 수 있는지 확인해보자.
식정리를 열심히 해주면, \( \binom{m}{k}(\sum_{i=0}^inf \binom{n-ik}{m-k}) \)가 됨을 확인할 수 있다.
아주 놀랍게도, 내가 위에서 설명한 Lagrange Interpolation을 사용하면 이를 계산할 수 있다!
따라서 모든 k에 대해서 위 값을 계산하고 포배에 따라 합치거나 빼거나 하면 답을 계산 가능하다.
4. ICPC 2019 Asia Yokohama Regional
C는 풀이를 찾긴 했는데 워낙 구현이 까다로웠고, 다 짰다고 생각했는데 오류를 찾았으며, 이를 고칠려면 14분만에 좌표압축과 세그를 짜야해서 구현은 실패했다. 해결한 순서대로 서술한다.
A. 가장 빠른 시점의 속도를 전부 순회하면 문제가 풀린다.
H. 올바른 괄호문자열은 (를 +1로, )를 -1로 환원했을때 "산맥"의 개수이기 때문에, 1을 더하거나 빼면서 동적으로 값을 관리하는 것은 어려운 것이 아니며, 수정하는 객체의 개수가 상수개이므로 롤백도 어렵지 않다.
B. 값이 알려진 각 점들로부터, 다른 점들까지의 거리를 이용해서 각 점들이 취할 수 있는 최대 높이와 최소 높이를 구한다. 당연히 최대 높이가 최소 높이보다 낮다면 불가능한 것이고, 그렇지 않다면 모든 점들이 최소 높이를 취한 상태가 실제로 구성될 수 있음을 보이는 것은 어렵지 않다.
G. 굉장히 짜증나는 문제였다고 생각했는데, 다른 사람들은 어떻게 생각할진 잘 모르겠다.
동일한 문자열을 서로다른 방법으로 구축하는 것은, 잘 생각해보면 그냥 처음에는 서로다른 두 문자열로 시작해서, 비어있는 쪽에 어떤 문자열을 더해주고, 동일한 prefix를 제거하여 다시 두 문자열 전부를 비게 하는 것으로 생각할 수 있다. 당연히, 어떤 순간에 양쪽 다 비지 않은 상황이 발생한다면, 그 뒤로 특정 prefix는 영원히 남게 되기 때문에 불가능하고, 따라서 적어도 한 쪽은 비어있는 상태만이 중요하다.
다음과 같은 상태들을 각 정점으로 하는 그래프를 생각하자: (현재 비어있는 쪽이 왼쪽인가/오른쪽인가, 안 비어있는 쪽의 길이는 얼마인가, 안 비어있는 쪽의 비트스트링은 무엇인가)
총 정점의 개수는 2^16정도의 스케일이 된다.
비어있는 쪽에 문자열을 더해서 공통되는 prefix를 지웠을 때 한 쪽이 사라져서 다른 정점의 상태에 대응되는 것을 간선으로 이어주고, 그 간선의 가중치는 추가한 문자열의 길이로 하자.
각 정점들마다, 간선의 개수는 안 비어있는 쪽의 길이에 좌우된다. 그 길이가 l이라고 하면, 안 비어있는 쪽에 추가하는 길이 l 이하의 가능한 문자열의 개수는 어차피 l개 이하이고, l 초과의 것들은 대략적으로 2^(16-l)정도의 스케일이다. 길이 l의 비트스트링의 가짓수는 2^l이기 때문에, 결국 총 간선 수는 16*2^16정도가 된다.
이제, 초기에 주어진 문자열의 쌍을 전부 시도해보면서 한쪽이 포함되는 쌍들에 대해서, 나머지 부분들의 최단거리값들을 초깃값을 설정해준 다음에, 다익을 돌리면서 양쪽이 다 빈 경우의 답을 구하고, 이를 2로 나누면 그것이 답임은 직관적으로 알 수 있다.
E. 재미있었던 문제같다.
어떤 i,j에 대해서, i<j이면서 a[i]>a[j]가 성립한다면, 이 둘은 반드시 다른 탑에 들어가야 한다. 이러한 관계를 만족하는 i,j를 간선으로 이어주자.
이제, 전체 그래프가 이분그래프가 아니라면 문제의 해결이 불가능하므로 No를 출력한다.
남은 파트에서 해당 그래프는 이분그래프라고 가정하겠다.
해당 그래프의 각 컴포넌트들을 배치하는 방법은 다른 컴포넌트를 배치하는데에 어떠한 영향도 주지 않는다(길이로 인한 제약을 제외하고). 또한, 한 컴포넌트를 배치하는 방법은 정확히 두 가지이다. 따라서 길이로 인한 제약이 없었다면 답은 2^(컴포넌트 개수)가 되었을 것이다.
길이제약이 있다면, 그냥 컴포넌트를 앞에서부터 보면서 dp[i][j]: i번째 컴포넌트까지 배치했을 때, 1번 탑의 높이가 j인 가짓수로 정의하여 dp를 돌리면 문제가 풀린다.
I. 그냥 더럽고 티피컬한 블록컷트리 자구문제. 필자는 블록컷트리를 짤줄 모르기 때문에 dfs tree를 통해 구현하였다.
C. 비록 풀진 못하였지만, 그래도 풀이는 발견했으므로 작성해보겠다.
Observation 1. 한 구간이 다른 구간을 포함하는 경우가 없는 최적해가 존재한다.
pf) 포함되는 구간을 제거하면 자명.
Observation 2. 어떤 구간을 제거했을 때 구간들 전체의 합집합이 여전히 변하지 않는다면, 이걸 지우는 것이 항상 이득이다(즉, 그런 구간이 없는 최적해가 존재한다.).
이 관찰들을 통해서, 다음과 같은 결론에 도달할 수 있다:
먼저, 각 구간들을 왼쪽 끝을 기준으로 정렬한다. dp[i]를, i번째 구간을 사용하고, i번째 구간까지 사용했을 때의 최댓값으로 정의한다.
dp[i]를 전이하는 방법은, 다음과 같다:
먼저, (i랑 겹치지 않는, i보다 선행되었던 구간들의 dp값중 최댓값+구간 i 자체의 이득)이 답의 후보이다.
i랑 겹치면서, i를 포함하지 않는 구간 j:[l,r]을 생각하고, 구간 i:[x,y]와 같이 두자. 이 두 구간의 색상이 같았다고 하자. 이러한 모든 구간 j에 대해서, dp[i]=max(dp[i],dp[j]-pos(y-l+1))을 취한다.
두 구간의 색상이 달랐다면, dp[i]=max(dp[i],dp[j]-(2pos+neg)(y-l+1))을 취한다.
이러한 전이를 할 수만 있다면, 문제가 풀림은 위의 두 관찰에 의해 명백하다.
이는, i를 증가시켜가면서 구간 i랑 겹친 구간들과, 그렇지 않은 구간을 관리하면서 계산한다. 그렇지 않은 구간들의 경우에는 그냥 dp의 최댓값만 계속 갱신해주면 되므로 어렵지 않다.
겹친 구간들은 약간 까다로운데, 구간의 오른쪽 끝은 i에 대해 정렬이 되어있지 않기 때문에 구간 i를 포함하던 것이 i가 증가함에 따라 포함하지 않을 수도 있고, 그 반대의 현상도 발생하기 때문이다. 이를 해결하는 것은 세그를 사용하는 것이 최선인 것 처럼 보인다. 세그를 사용한다면, 각 구간들에 대해서 dp[i]-pos(y), dp[i]-(2pos+neg)(y)같은 값들을 세그로 관리해주면 위의 dp전이를 빠르게 처리 가능함을 알 수 있다.
5. 소감
최근에 다양한 일이 있었기 때문에 바빠서 많은 수행을 하진 못했던 것 같다. 그리고 사실 그냥 icpc셋 하나를 도는게 조금 더 성취감있는? 듯한 느낌이 들어서 그냥 적당히 마음이 내키는대로 수행을 할 것 같기도 하다.
'ps이론' 카테고리의 다른 글
| [ROAD TO ULTIMATE MATHCHUNG] 2. Bus Stop (1) | 2025.01.12 |
|---|---|
| [궁극의 웰노운 알고리즘] 11. Partition number, Euler's Pentagonal Theorem (2) | 2025.01.10 |
| [ROAD TO ULTIMATE MATHCHUNG] 0. 궁극의 수학충이 되기 위한 길 (2) | 2025.01.10 |
| [궁극의 웰노운 알고리즘] 10. Square Counting Technique (2) | 2024.08.15 |
| [궁극의 웰노운 알고리즘] 9. SMAWK, min-plus convolution(convex and convex), min-plus convolution(convex and arbitrary) (1) | 2024.06.17 |
