이번에 다룰 주제들은 dp이다. 물론 앞으로도 수많은 dp 포스팅을 써야겠지만...아무튼 이번에는 굉장히 웰노운적인 dp 트릭들을 다룰 예정이다. 사실 나도 그냥 이름이 신기해보여서 가져온거긴 한데 aliens trick 빼고는 뭔지 몰라서 공부해야 한다. 물론 이번에도 4번째 포스팅과 3번째 포스팅을 유기하고 왔지만, 뭘 기대하고 들어왔냐는 말은 싹아지가 없어보여서 그냥 안했다.
일단 3번째 포스팅은 거의 다 했고, 4번째 포스팅은 곰국에 막혀서 던졌다. 따라서 5번부터 시작한다.
1. aliens trick
뭐 여기에서 다루는 주제중에서는 가장 유명하고 웰노운인 것 같다. 일단 백준 태그가 정식으로 있는 시점에서부터...
아무튼, 기본적으로 trick의 이름이 붙은 문제에 대해 설명하는 것이 가장 정석적인 것 같다. 20090번: Aliens (acmicpc.net)뭐 나도 아직 짜본적은 없긴 한데...이번 기회에 짜보려 한다.
20090번: Aliens
take_photos(5, 7, 2, [0, 4, 4, 4, 4], [3, 4, 6, 5, 6]) In this example we have 7 × 7 a grid with 5 points of interest. The points of interest are located in four different cells: (0, 3), (4, 4), (4, 5) and (4, 6). You may take at most 2 high-resolution ph
www.acmicpc.net
문제를 요약하자면, n*n 격자판에 몇개의 특별한 위치가 존재한다. 이제 해당 격자판의 대각선의 일부를 대각선으로 하는 정사각형을 최대 k개 만들어서 그 위치들 전체를 덮는 문제인데, 이때 면적을 최소화해야 한다.
우선, 한 가지 관찰할 수 있는 사실은 정사각형의 개수 제한이 없다면 문제는 굉장히 자명해진다는 점이다. 모든 특별한 위치들에 대해서, 그 위치를 꼭짓점으로 하는 정사각형들로 덮는 것이 최적일수밖에 없다. 따라서, 우리는 k가 굉장히 클 때의 문제를 해결했다!
...그러나, 결국 우리는 k가 특정 값으로 주어진 경우의 문제를 해결하진 못했다. 이건 어떻게 처리할 수 있을까?
일단, 문제를 조금 더 해결하기 쉬운 형태로 바꾸어보자. 만약 대각선을 기준으로 왼쪽 아래에 존재하는 점들은, 그대로 대칭해서 오른쪽 위의 점들로 바꾸어줄 수 있다. 또한, 어떤 점을 포함하면 자명하게 포함될 수 밖에 없는 점들도 존재한다. 그러한 점들도 제거해주자. 이렇게 입력을 고쳐주고 나면, 하나의 x좌표에는 많아야 하나의 점만이 존재하게 되며, 각 점들은 x좌표의 크기가 커질수록 y좌표의 크기는 감소하게 된다. x좌표순으로 각 점들에 인덱스를 매기자.
이제 dp[i][j]를 i번 점까지를 포함하며, 총 j개의 사진을 찍은 경우의 최솟값으로 정의할 수 있다. 이러한 정의하에서, dp[i][k]는 다음과 같이 계산된다:
dp[i][k]=min(dp[j][k-1]+(X[i]-X[j])*(Y[j+1]-X[i]+Y[j+1]-X[j]))
즉, 모든 항들을 전부 계산하기 위해서는 O(nk^2)정도가 소요될 것이다. 역시 전체 문제를 해결하기에는 터무니없이 느리다.
여기에서 조금 더 최적화를 해줄 수 있는 방법이 있는데, 바로 convex hull trick을 적용하는 것이다. dp식을 잘 살펴보면, i에 의해 변동되는 값은 오직 X[i] 뿐이며, 식을 정리해보면 X[i]에 대한 일차식으로 나타나기 때문에, cht를 적용 가능하다! 따라서 우리는 아주 러프하게 대충 O(nklogn)정도만에 문제를 해결하게 되었다. 확연히 빨라졌지만, 여전히 느리다.
이제 여기에서 우리는 조금 다른 방향의 최적화를 진행할 것이다. 만약에 구간을 나누는 것 자체에 가중치를 매긴다면 어떨까? 즉, dp식을 강제로 dp[i][k]=min(dp[j][k-1]+(X[i]-X[j])*(Y[j+1]-X[i]+Y[j+1]-X[j]))+C로 수정하는 것이다. 만약 C가 터무니없이 크다면, 자명히 단 하나의 정사각형만으로 모든 점들을 커버치는 것이 최대의 이득일 것이다. C가 0이라면 우리가 관찰했듯 모든 점들에 대해 나누는 것이 최적이다. 만약, 적당히 C를 조절하여 정확히 k개의 구간으로 나누는 것이 최대의 이득이 되도록 한다면? 그런 경우 우리는 k개의 구간으로 나누는 것에 대한 문제 또한 같이 풀 수 있게 된다! 그렇다면 C는 어떻게 찾을까?
우선, 한가지 알아야 하는건 C가 커지면 커질수록 적은 구간으로 나누는 것이 이득이라는 사실인데, 굉장히 자명하다. 따라서, 뭔가 일단은 C에 대해 이분탐색을 하면 될 것 같긴 하다. 그런데, 가장 우려되는 부분은 "그 어떤 C에 대해서도 k개의 구간으로 나누는 것이 최적이 아닌 경우"이다. 그런데, 해당 문제의 경우에는 놀랍게도 그렇지 않다는 사실을 증명이 가능하다! 그 핵심은 각 k들마다 최솟값들의 그래프를 그렸을 경우 그것이 볼록한 함수로 나타나는데에 있다. 만약 이 함수가 볼록하다면, C를 잘 조절하는 것은 어떻게 생각해보면 전체 그래프에서 y=Cx를 더한 다음 최솟값을 따는 구조라고 해석할 수 있다. 만약 simplex algorithm을 알고 있는 사람이라면 뭔가 조금 더 직관적으로 와닿지 않을까...? 물론 난 simplex algorithm이 뭔지 몰라서 잘 모르겠다. 어쨌든, 이런 직관으로 생각해보면 무조건 k개의 구간으로 나누는 것이 최적인 C가 존재함은 간단하게 이해가능하다.
뭐, 사실 가장 본질적인 부분은 다루었지만, 어쨌든 왜 k에 따른 최솟값의 그래프가 볼록한지도 설명해야 할 것이다. 뭐 이건 단순한 직관이긴 하지만, 잘 생각해보면, 최적해를 찾는다는 것은 어떤 적당한 한개의 정사각형의 오른쪽 위 부분에서 일부 직사각형들을 최대한 많이 파내는 행동이라고 생각할 수 있다. 만약 내가 이전에 추가로 파낸 면적보다 더 많은 면적을 파내는데에 성공했다면, 그땐 내가 이번에 파낸 방식을 적당히 재구성해서 이전의 결과들중 "최소한 하나를" 훨씬 좋게 만들 수 있을것만 같다. 왜냐하면 어쨌든 하나의 최적해가 도출되는 과정 전체를 볼록하게 재구성하는 것은 가능하기 때문이고, 뭔가 적당히 부등식같은걸 가져와 박으면 풀릴 것 같긴 하다. ㅁㄴㅇㄹ 걍 독자들을 위한 연습문제로 남긴다.
어쨌든, 이러한 아이디어의 핵심을 함축하자면, "특정 인자에 대해 볼록한 dp값을 가지는 dp에서 그 인자에 대한 가중치를 준 문제를 풀어 해당 인자를 유도하자"라는 것이다. 보통 이런 아이디어가 라그랑주 승수법에서 특정 정류화 문제를 해결하는 경우에도 잘 활용되기 때문에, 이런 아이디어를 라그랑주 최적화라고도 하는 것 같긴 하다.
2. hirschberg
3. connected component dp
절대로 혼동해선 안되는 것은, 커넥션 프로파일 dp와는 다른 아이디어라는 것이다! 보통 이 아이디어는 어떤 순열에 대한 문제를 해결할 때 자주 사용되곤 한다.
이 문제에 대한 좋은 motivation은,10872번: 팩토리얼 (acmicpc.net)이다. 문제를 요약하자면, 가능한 모든 길이 n의 순열의 개수를 구하는 것이다(...)
10872번: 팩토리얼
0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.
www.acmicpc.net
뭐, 혹자는 단순히 n!을 계산하면 되지 않느냐고 할 수도 있다. 사실 그게 맞긴한데(...) 이 아이디어에 대한 intuition을 얻기 위한 제물이라고 생각하고 일단은 해보자.
사실, 이 아이디어는 개념 자체로는 굉장히 단순하다. dp[i][j]를 1부터 i까지를 순열들의 특정 위치에 고정해두었는데, 이때 특정한 "component"의 개수가 j개인 가짓수를 의미하도록 하는 것이다. 이때, component라는 것은 특정한 연속한 객체들의 묶음을 의미한다. 예를 들어, {(3),(1,2)}같은 것은 총 2개의 component들이 배열되어있는 것을 보여주고 있다. 1,2는 반드시 저렇게 연속해서 붙어있어야 하지만, (3)과 (1,2)는 순서만 맞으면 되고 그 사이에 다른 원소가 들어와도 된다.
이러한 상황에서 특정한 상태를 전이하는 것은 다음의 3가지 방식으로 기술될 수 있다:
1. i+1을 아예 독립적인 하나의 component로 배치하는 경우. 총 j개의 component들이 있었으므로, i+1번 원소가 들어갈 수 있는 위치는 총 j+1개 존재한다. 따라서 dp[i+1][j+1]+=dp[i][j]*(j+1)을 해준다.
2. i+1을 어떤 component의 시작 혹은 끝에 추가하는 경우. 총 j개의 component들이 있었으므로, 총 2j개의 위치가 존재한다. 즉, dp[i+1][j]+=dp[i][j]*2j
3. i+1을 어떤 두 component의 중간에 집어넣고, 두 component를 merge하는 경우. 총 j개의 component들이 있었으므로, 총 j-1개의 위치가 존재한다. 즉, dp[i+1][j-1]+=dp[i][j]*(j-1)
이제 답은 dp[n][1]이 된다.
...라고만 하면 이것이 왜 되는지는 그닥 자명하지 않다. 기본적으로 경우의 수 dp에서는 중복이 되는 값이나, 혹은 dp식으로 처리하지 못한 경우의 수들을 굉장히 주의해야 하기 때문이다. 따라서, 모든 순열들이 위의 방식을 통해 적어도 한번 세어지며, 또한 정확히 한번 세어진다는 사실을 증명하겠다.
우선, 모든 순열들이 최소 한번씩은 등장한다는 사실부터 증명해보자. 이는 귀납법을 통해 증명 가능한데, 핵심적인 주장은 어떤 순열 p에 대해서도, 1부터 i까지를 p에서의 순서와 동일하게 배치 가능하며, 특히 p에서 인접한 원소들끼리는 같은 컴포넌트에 들어가도록 할 수 있다는 명제를 증명하는 것이다.
우선, i=0이면 "자명하다". 1부터 i-1까지 이 행위에 성공했다고 가정하자. 이제 i를 배치해야 하는데, 실제로 i가 존재하는 p의 위치를 k라고 해보자.
1. $p_{k}\le p_{k-1},p_{k+1}$. 이 경우에는 아직 k의 주변에 어떠한 "연결되어야 하는 컴포넌트"들도 존재하지 않는 상황이다. 단순히 i를 적절한 위치에 독립적인 컴포넌트로 추가해주면 된다.
2. $p_{k}\le p_{k-1}, p_k\ge p_{k+1}$이거나 혹은 그 반대의 경우. 이 경우에는 k의 바로 옆에 연결되어야 하는 컴포넌트가 정확히 하나 존재한다. 따라서 단순히 그 컴포넌트의 끝부분에 i를 붙여주면 된다.
3. 위의 어느 상황도 아닐때. 이 경우에는 k의 양옆에 있는 두 컴포넌트를 병합해주어야 한다. 그리고 그렇게 하면 충분하다.
뭐, 사실 이렇게 쓰고 보면 가능성 자체는 비교적 직관적일 것이다. 어떤 방법을 써서든 적당한 construction을 찾을 수 있다. 그렇다면, 이 순열이 만들어지는 과정이 이것뿐이라는 사실은 어떻게 알 수 있을까?
위의 과정들을 살펴보면 사실은 비교적 직관적이다. 우리는 총 3개의 상황으로 i를 어떻게 배치해야 할지를 분류하였는데, 사실 각 과정들은 아주 완벽히 구분되어있고, 그렇게 하도록 강제되어있다. 따라서 하나의 순열을 세는 두개 이상의 방법은 존재할수가 없다.
위의 논의들로 인해 해당 dp의 정당성이 입증된다. 이제 이 trick을 어떻게 써먹을 수 있을지 조금 더 생각해보자.
13188번: Kangaroo (acmicpc.net)
13188번: Kangaroo
A garden is composed of a row of N cells numbered from 1 to N. Initially, all cells contain plants. A kangaroo arrived in the garden in cell numbered cs. Then he jumps from cell to cell, eating the plants as he goes. He will always finish in cell numbered
www.acmicpc.net
문제를 간단히 요약하자면, s로 시작하고 t로 끝나는 순열의 개수를 count해야하는데, 이때 반드시 그 순열이 대충 "지그재그" 순열이어야 한다는 것이다. 뭐 지그재그라고만 하면 충분히 어떤 것인지 이해할 수 있을 것이라 생각한다.
아무튼, 그렇다면 이 문제는 어떻게 해결될 수 있을까? 뭐 사실 나도 코드를 아직 안짜보긴 했는데 만약 내가 이 trick을 통해 문제를 풀어야 한다면 이렇게 할 것 같다:
일단, s를 추가하기 이전까지는 다음의 두 방법만을 통해 상태를 전이한다:
1. 임의의 위치에 새로운 component를 만든다.
2. 임의의 두 컴포넌트를 merge한다.
이러한 방식으로 상태를 전이할수밖에 없는데, 왜냐하면 어떤 컴포넌트의 끝부분에 무언가를 추가하는 순간 나중에 그쪽에 나타날 컴포넌트와 병합될 때 필연적으로 모순이 발생할 수 밖에 없기 때문이다.
s는 자명하게 왼쪽에 붙거나, 가장 왼쪽에 새로운 component로 추가된다. 설명이 필요한가?
s를 추가하고, t가 추가되기 전까지는 다음의 두 방법만을 통해 상태를 전이한다:
1. 가장 왼쪽을 제외한 임의의 위치에 새로운 component를 만든다.
2. 임의의 두 컴포넌트를 merge한다.
물론, t도 오른쪽에 붙거나 새 component로 최우측에 추가된다.
t를 추가하고 n까지는, 다음의 두 방법만을 통해 상태를 전이한다:
1. 가장자리들을 제외한 임의의 위치에 새로운 component를 만든다.
2. 임의의 두 컴포넌트를 merge한다.
흠 이렇게 쓰고 나니까 생각보다 무척 구현이 할만해보이는 것 같다. 오전 1시긴 한데 바로 짤 수 있을것만 같은 느낌...아무튼 이렇게 하면 풀리지 않을까 생각한다.
오 맞았네 생각보다 구현이 간단해서 다행이다.
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll n,s,t,i,j,k,dp[2200][2200];
int main()
{
scanf("%lld %lld %lld",&n,&s,&t);
if(n==2)
{
printf("1");
return 0;
}
if(s>t)
swap(s,t);
dp[0][0]=1;
for(i=1;i<s;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]+=dp[i-1][j-1]*(j);
dp[i][j]%=1000000007;
}
for(j=0;j<i;j++)
{
dp[i][j]+=dp[i-1][j+1]*(j);
dp[i][j]%=1000000007;
}
}
for(i=0;i<=n;i++)
{dp[s][i]=dp[s-1][i];
if(i>=1)
dp[s][i]=(dp[s][i]+dp[s-1][i-1])%1000000007;
}
for(i=s+1;i<t;i++)
{
for(j=1;j<=i;j++)
{
dp[i][j]+=dp[i-1][j-1]*(j-1);
dp[i][j]%=1000000007;
}
for(j=0;j<i;j++)
{
dp[i][j]+=dp[i-1][j+1]*(j);
dp[i][j]%=1000000007;
}
}
for(i=0;i<=n;i++)
{dp[t][i]=dp[t-1][i];
if(i>=1)
dp[t][i]=(dp[t][i]+dp[t-1][i-1])%1000000007;
}
for(i=t+1;i<=n;i++)
{
for(j=2;j<=i;j++)
{
dp[i][j]+=dp[i-1][j-1]*(j-2);
dp[i][j]%=1000000007;
}
for(j=0;j<i;j++)
{
dp[i][j]+=dp[i-1][j+1]*(j);
dp[i][j]%=1000000007;
}
}
printf("%lld",dp[n][1]);
}잘 보면, 정말로 위의 절차를 통해 구현했음을 알 수 있다. 꽤 인상적인 아이디어로군
4. open and closed interval trick
이 아이디어는 다른 트릭들에 비해 비교적 직관적이고 간단한 아이디어라고 생각된다. 사실 그만큼 이런 아이디어를 적용할 수 있는 문제가 그렇게 많을지에 대해서는 의구심이 들긴 하지만...그래도 이런 전략에서 특정한 dp들에 대한 좋은 intuition이 될 수 있지 않을까 싶다.
일단, 다음과 같은 문제를 풀고 싶다고 하자:
n명의 사람이 있고, 각자의 '실력'이 있다. n명의 사람을 몇개의 그룹으로 나누고 싶은데 한 그룹에서의 '불균형'은 그 그룹 내의 실력의 최댓값과 최솟값의 차이며, 전체 불균형은 모든 그룹의 불균형의 합이다. 전체 불균형이 k 이하가 되도록 그룹을 나누는 가짓수를 구하여라(n<=200,k<=1000,a_i<=500)(Problem - F - Codeforces)
Problem - F - Codeforces
codeforces.com
아주 자명하게도, 브루트포스는 불가능하고 이런 경우의 수를 카운팅하는 방법은 사실상 dp가 가장 직관적으로 생각할 수 있는 풀이임을 알 수 있다. 그러나, 그 dp를 어떻게 구성해야 답을 구할 수 있는지에 대해서는 의문점이 생길 수 있다.
일단 한가지 알아야 하는 사실은, 모든 사람을 정렬하고 난 뒤에도 문제는 전혀 바뀌지 않는다는 점이다. 그렇다면 우리는 모든 사람들을 정렬하고, i번째 사람을 추가할 때 어떤 현상이 발생하는지를 분석해볼 수 있다.
이러한 생각에 착안해보면, 다음과 같은 세팅을 하게 된다: 몇개의 '열린 구간'과 '닫힌 구간'이 있는데, 구체적으로 해당 문제에서 '열린 구간'은 아직 사람을 전부 넣지 않은 그룹을 의미하고, '닫힌 구간'은 모든 사람을 집어넣은 그룹을 의미한다. 예를 들어, 사람이 5명 있고 우리가 만들고자 하는 상태가 {1,2,4}, {3}, {5}였다고 하고, 현재까지 3번 사람까지 넣었다고 생각해보자. 그렇다면 그룹은 {1,2}, {3}이 될 것이고, {3}은 이미 완성된 그룹이기 때문에 '닫힌 구간'으로 간주되고, {1,2}는 아직 4를 추가하지 않았으므로 '열린 구간'으로 간주된다. 이러한 세팅 하에서, 이제 어떤 사람 한 명을 추가할 때 어떤 변화가 발생하는지 생각해보자. 가장 마지막으로 추가했던 사람의 실력을 a_(i-1), 현재 추가할 사람의 실력을 a_i, 현존하는 "열린 구간의 개수"를 k라고 했을 때, "현재까지 계산된 전체 불균형"이 k*(a_i-a_(i-1))만큼 증가했다고 볼 수 있다. 왜냐하면 이미 닫힌 구간은 답에 전혀 간섭하지 않고, 열린 구간들은 반드시 a_i 이상의 무언가가 그 그룹 안에 들어올 것이기 때문에 그 불균형을 각 사람들의 실력의 간극을 전부 더함으로써 계산이 가능하기 때문이다. 대충 실제로 수직선에 대해서 사람들의 실력에 따라 구간을 그려보면 직관적으로 이해가 갈 것이다.
따라서, 우리는 다음과 같은 dp를 세울 수 있다: dp[i][j][k]: i번째 사람까지 추가했고, j개의 열린 구간이 있으며, 현재까지 계산된 전체 불균형이 k인 가짓수라고 하자. 그렇다면 dp의 전이는 몇개의 케이스로 나뉜다.
일단 기본적으로 dp[i-1][j][k]에서 전이를 진행한다고 하자. 일단, val=k+j*(a[i]-a[i-1])이라고 하고, v=dp[i-1][j][k]라고 하자.
1. i번째 사람으로만 이루어진 그룹을 만든다: dp[i][j][val]+=v
2. 어떤 열려있는 구간에 i번째 사람을 추가한다: dp[i][j][val]+=v*j
3. 새로운 열려있는 구간을 만든다: dp[i][j+1][val]+=v
4. 열려있는 구간에 i번째 사람을 추가하고, 그 구간을 닫는다: dp[i][j-1][val]+=v
이렇게 하면 모든 경우를 전부 고려할 수 있고, 따라서 문제가 해결됨을 알 수 있다.
흠...이렇게 쓰면서 이 트릭에 대한 고찰을 해보니 뭔가 고2때 봤던 FKMO 2022의 조합문제가 기억난다. 아마 6번이었나...? 한번 찾아봐야겠군
흠...대충 어떤 문제였는지 보고 왔는데 풀이에 대한 기억이 가물가물하다. 대충 다음과 같은 문제다:
어떤 구간들의 집합 X가 fancy하다는 것은, 다음 조건이 만족한다는 것이다.
1. X의 원소는 2022개이다.
2. X의 각 원소들은 [0,1]에 포함되는 닫힌 구간이다.
3. 임의의 실수 r에 대해서도, r을 포함하는 X의 원소들의 개수는 1011개 이하이다.
이때, 두 fancy한 집합 A,B에 대해서, 두 집합의 두 원소의 교집합이 공집합이 아닌 쌍의 개수를 최대화하는 문제이다.
음...최대한 내 기억을 더듬어본다면, 나의 접근은 이러했다.
우선, 3번 조건이 없다면 모든 원소가 [0,1]인 것이 최대의 이득이 될 것이다. 그러나 3번 조건의 존재로 인해서 이러한 시도는 좌절된다.
그런데, 잘 생각해보면 어떤 fancy한 집합은 특정한 구간들을 시각화한 것으로 생각할 수 있다. 구체적으로, 구간들을 높이가 1인 직사각형으로 대응하여 생각할 때, 주어진 조건은 높이가 1011이고 너비가 1인 직사각형에 모든 직사각형들을 배치할 수 있다는 조건으로 재해석할 수 있다. 또한, 공집합이 아닌 쌍의 개수를 최대화하기 위해선 주어진 조건을 높이가 1011이고 너비가 1인 직사각형(앞으론 배경 직사각형이라 하겠다)을 각 구간에 대응되는 직사각형들을 통해 "분할"할 수 있다는 것으로 강화할 수 있다. 이제, 공집합이 아닌 쌍의 개수를 세는 것을 더블 카운팅 기법을 통해 더욱 간단한 문제로 바꿀 수 있다.
B의 기준에서 한번 그 개수를 세어보자. A에는 같은 행 내의 두 직사각형들 사이에 존재하는, 이른바 "균열"이 존재할텐데, B의 한 구간에 대해 답은 해당 구간(J)의 정확히 내부에 있는 균열의 개수+1011과 같다는 사실을 알 수 있다. 만약 J의 경계와 균열이 겹친다면, 이는 고려할 수 없다. 왜냐하면, 어쨌든 쌍의 개수를 센다는 것은 뒷부분의 구간이 J인 것의 개수를 모든 J에 대해 더하는 것으로 생각할 수 있기 때문에, 하나의 J에 대한 개수를 세어주면 충분하며, 그 J와 겹치는 것의 개수를 잘 생각해보면 우선 A에 있을 1011개의 행에 의해 기본적으로 한개씩 주어질 것이며, 만약 어떤 행에서 두 직사각형의 균열이 J 내부에 존재한다면 그 두 직사각형이 전부 J와 교집합을 가지는 것으로 해석할 수 있기 때문이다. 따라서 다음과 같은 식이 성립한다. 여기에서 알 수 있는 사실은, 하나의 B의 행에 존재하는 모든 구간들에 대해 그 답의 합은 결국 "B의 구간들의 경계와 A의 균열들이 일치하는 몇개의 부정적인 오차"를 제외하고는 1011*(해당 행에 있는 B의 구간의 개수)+A의 모든 원소의 개수와 동일하다는 것이다. 이 "부정적인 오차"는 사실 B와 A를 통틀어서 모든 "균열들"의 위치를 서로 다르게 조정해주면 최소화되며, 행의 시작부분이나 끝부분등만이 오차로 남아서 결론적으로 다음과 같은 정확한 식을 주게 된다:
1011*(해당 행에 있는 B의 구간의 개수)+A의 모든 원소의 개수-1011.
이를 모든 B의 행에 대해 더해주면, 또 다음을 얻는다:
1011*(B의 구간의 개수)+1011*A의 모든 원소의 개수-1011*1011
따라서, 해당 값은 1011*1011*3이 되며, 이 모든 과정들이 최적이었으므로 이것을 넘는 값은 존재할 수 없다.
풀이가 예전에 서술했던 것에 비해 다소 덜 엄밀한 것 같긴 하다. 아무튼, 뭔가 여기에서 직사각형에 대응되는 세팅이 비슷했어서 기억났던 것 같다. 굳이 dp가 아니어도 이런 쪽으로 괜찮은 motivation이 될 수 있지 않을까?
5. X2 +1 trick
왠지 재미있어보여서 그낭 먼저 공부해봤는데, 역시 재미있다. 일단 이 트릭을 설명하기 전에, 굉장히 비슷한 구조를 가지고 있는 알고리즘인 키타마사법에 대해 설명하겠다(사실 키타마사법이 이 트릭의 특수한 예시라고 볼 수 있는 것 같다.).
우선, 다음과 같은 문제를 생각하자: 13725번: RNG (acmicpc.net)
13725번: RNG
첫째 줄에 k와 N (1 ≤ k ≤ 30,000, 1 ≤ N ≤ 1018)이 주어진다. 둘째 줄에는 A1, A2, ..., Ak가 셋째 줄에는 C1, C2, ..., Ck가 주어진다. (0 ≤ Ai, Ci < 104857601)
www.acmicpc.net
간단히 문제를 요약하자면, k차 선형점화식의 n차 항을 계산하라는 것이다. 이는 키타마사법을 알고 있는지를 물어보는 문제에 가깝다.
아주 나이브하게 생각해보면, O(Nk)정도의 시간에 문제를 풀 수 있음을 알 수 있다. 그러나, 이는 터무니없이 부족하다. 조금 더 생각해보면, 선형점화식을 행렬의 거듭제곱으로 표현할 수 있다는 사실을 통해 O(k^3logn)정도만에 문제를 풀 수 있을 것이다. 음...Nk에 비하면 그나마 나아진 것 같긴 한데 결국 오십보 백보이다. 이때, 키타마사법은 이 빠른 행렬 거듭제곱의 아이디어를 조금 수정하여 진행한다.
핵심은 모든 선형점화식의 항들은 초항들의 선형결합으로 이루어져있다는 것이다. 그리고, 만약 n번째 항을 구하고 싶다면 x^n을 (a_1-....-a_kx^(k-1)+x^k)로 나눈 나머지를 통해 답을 구할 수 있음을 알 수 있다(각각의 계수들이 어떤 초항을 얼마나 더하는지를 지시하기 때문이다.). 따라서, 우리가 해야 할 것은 적당히 다항식의 곱셈을 관리하는 것이다. 만약 바로 다음 다항식으로 넘어가고 싶으면 x를 곱하고, 그렇지 않다면(2n번째 항의 다항식을 얻고 싶으면) 거듭제곱을 한다. 그리고, 이게 X2 +1 트릭의 기본 아이디어이다. 즉, X2를 한 항을 찾거나, +1을 한 항을 찾는 것이다. 아무튼 키타마사법에 fft를 곁들이면 O(klogklogn)정도 걸린다.
X2 +1의 아이디어를 쓰는 다른 문제를 아직 백준에서는 발견하지 못해서, 그냥 어딘가의 문제를 가져왔다. Perfect Permutations | Practice Problems (hackerearth.com)
Perfect Permutations | Practice Problems
www.hackerearth.com
간단히 말하자면, 반전수가 K이며, 수열의 길이가 N인 순열의 개수를 세는 것인데, 여기서 우리는 서브태스크 4만을 확인할 것이다. 즉, K<=1000, N<=10^9이다.
일단, 아무래도 dp문제이기 때문에 dp식을 세워봐야 할 것이다. 생각해볼 수 있는 가장 간단한 방법은, dp[i][j]:길이 i이며, 반전수가 j인 순열의 개수로 정의하는 것이다. 이러한 정의하에서, i+1번째 위치에 어떤 원소를 두는가에 따라 dp식을 자명히 계산할 수 있다. 구체적으로, dp[i+1][j]=dp[i][j]+dp[i][j-1]+...+dp[i][j-(i)]가 될 것이다.
따라서, 우리는 이제 해당 문제를 O(NK)에 계산할 수 있게 되었다(제한에 비해 턱없이 부족하지만).
그렇다면, 이를 어떻게 해야 최적화 가능할까? 만약 우리가 어떤 i에 대해 dp[i][?]의 값을 전부 안다면, dp[i+1][?]의 값 또한 알 수 있음을 알 수 있다. 또한, 모든 i에 대해 dp[i]에 대한 정보를 알기는 힘들 것이다. 따라서, dp[i]로부터 dp[2i]를 알아내는 방안을 생각해볼 수 있다!
길이 2n의 순열을 생각하고, 이들을 왼쪽과 오른쪽 각각 n개로 나누자. 전체 순열에서 반전수가 나타나는 총 값은 1~n까지의 수들에 대한 반전수+n+1~2n까지의 수들에 대한 반전수+큰수 오른쪽에 있는 작은수의 개수의 총합으로 나타낼 수 있다. 이중, 앞의 2개는 이미 dp[n]을 통해 우리가 전부 컨트롤할 수 있는 값들이다! 따라서, 우리는 단순히 큰수의 오른쪽에 있는 작은 수의 개수들의 총합에 대한 정보만을 추가로 가지고 있으면 된다는 사실을 알 수 있다. 조금 더 구체적으로, 큰 수와 작은 수의 위치를 변경하는 것은 각 큰 수들과 작은 수들끼리의 관계를 변형하는 것과는 완전히 독립적이기 때문에, 이러한 것은 생성함수의 아이디어를 빌려 다항식을 곱하는 연산을 하는 것으로 간주할 수 있다.
다만, 내가 이걸 배운 자료에서도 이 아이디어를 쓰는 문제를 본 적이 별로 없다고 해서 그냥 가능성 정도만 알고 있어도 충분할 것 같다...
