[ROAD TO ULTIMATE MATHCHUNG] 3/2. Atcoder Regular Contest 104

https://atcoder.jp/contests/arc104/tasks

Tasks - AtCoder Regular Contest 104

104번 콘테스트부터 하는 이유는, 최근의 앳코더 형식과 비슷하게 출제되기 시작한 시점이 104번 콘테스트부터이기 때문이다.

 

A. 자명.

 

B. (i,j)가 실제로 가능한지 판별하는 방향으로 한다. (i,j) 구간에서 A개수가 T개수와 같고, C개수가 G개수와 같다면 가능하다. 따라서 모든 i에 대해서, j를 증가시키며 문제를 풀 수 있다.

 

C. 문제의 조건을 분석해보면, 조건을 만족하는 사람들의 출입은 결국 전체 시간대가 (i,i+2k-1) 구간으로 나누었을 때, 구간 내에서 x와 x+k가 매칭되어있는 경우이다. 따라서 dp[i]를 i까지의 시간대가 이미 구간으로 전부 분할될 수 있다는 식으로 정의해주면, 이제 dp[i]가 실제로 가능한지를 체크하려면 dp[i-2k]가 가능하고, (i-2k+1, i) 구간이 매칭될 수 있는지를 체크해주면 된다. dp[2n]이 참이라면 Yes, 아니라면 No이다.

 

D. 가장 재미있었던 문제. 몇가지 관찰들이 필요하다.

 

우선, k 하나를 고정한 상태에서 문제를 푸는 경우를 생각해보자. 그러면 문제를 다음과 같이 치환할 수 있다:

 

1-k, 2-k, 3-k, ..., N-k를 각 정수당 최대 K개 사용하여 그 합이 0이 되도록 하는 가짓수를 구하여라.

 

1-k~(k-1)-k까지는 음수이고, k-k는 0이며, 나머지는 양수이다. k-k에 대해서는 그냥 이를 고려하지 않고 마지막에 답에 (k+1)을 곱해주면 고려가 끝난다. 문제는 음수와 양수들에 대해서 문제를 푸는 것인데, 이는 사실 N까지의 양수들만 썼을 때 i를 만드는 가짓수를 plus[N][i]로 정의하고, -N까지의 음수들만 썼을 때 -i를 만드는 가짓수를 minus[N][i]로 정의하였을 때, 답은 \(\sum_{i=0}^{\infty}plus[N-k][i]minus[k-1][i]\)와 같음을 알 수 있다. 한편, 당연히 plus[K][i]=minus[K][i]이다. 

 

그렇다면, plus[N][i]를 어떻게 구해야 하는지 고민해볼 수 있다. 이를 하는 방법은, 약간의 생성함수적 접근을 생각하면 어렵지 않게 할 수 있다. \( \sum_{i=0}^{\infty}plus[i]x^i=\prod_{i=1}^N (1+x^i+...+x^{Ki}) \)와 같음을 관찰할 수 있다. plus[N-1][i]를 구했다고 가정해보자. 또한, plus[N][i]의 생성함수를 P(N)과 같이 정의하자. 현재까지 P(N-1)을 계산했다고 가정하자. 그렇다면, \(P(N)=(1+x^N+...+x^{NK})P(N-1)=(1+x^N+x^{2N}+...)P(N-1)-(x^{N(K+1)}+x^{N(K+2)}+x^{N(K+3)+...})P(N-1) \)이라는 점을 사용하면, 최고차항의 지수정도의 스케일의 연산으로 P(N)을 구할 수 있다. 이를 구하는 것은 항간의 덧셈, 뺄셈으로 구성되기 때문에, 당연히 P(N)을 알면 역연산들을 적용해서 P(N-1)을 구할 수도 있다.

 

이제 풀이의 대략적인 틀을 잡을 수 있다.

 

일단, minus[N][i]의 생성함수를 M이라고 하자. P(0)=M(0)=1임은 명백하다. 일단, i=1~N-1까지 보면서 P(N-1)을 계산한다.

 

이제 P(N-1), M(0)을 이용해서 k=1일때의 답을 계산한다. 이제 P(N-1)을 통해서 P(N-2)를 구하고, M(0)을 이용해서 M(1)을 구하고, k=2일 때의 답을 계산한다. 이를 계속 반복하면 k=N까지 답을 구할 수 있다. 

 

시간복잡도는, 일단 최고차항의 지수는 대략적으로 \(O(N^3)\)정도이기 때문에, P(N)으로부터 P(N+-1)을 구하는 시간복잡도도 O(N^3)정도이다. 이러한 갱신연산을 총 O(N)번 하므로, 총 시간복잡도는 대략적으로 O(N^4)이다. 

 

따라서 전체 문제가 O(N^4)만에 해결된다. 최고차항의 지수가 N^3의 1/6정도의 스케일이므로, 생각보다 상수가 크지 않아서 모듈러 연산이 있음에도 불구하고 4초만에 돈다.

 

E. x_1,...,x_N의 가능한 대소관계를 전부 가정한다. 이러한 총 가짓수는 약 5000개 정도로, 이러한 수를 bell number이라고 하는듯한데, 차피 충분히 작은건 딱봐도 알 수 있기 때문에 자세한 설명은 스킵한다.

 

그러면 이제 결국 문제를, 1<=x_i<=a_i이며, x_i<x_{i+1}을 만족하는 x_i의 수열의 개수를 구하는 것으로 환원할 수 있다.

 

이는, dp[i][j]를, x_i가 (a)들로 인해 분할되는 정수구간에서 j번째에 위치하는 가짓수로 정의하면 계산이 된다는듯하다.

 

F. 안읽어봄