[Hard] SRMChallengePhase

각 coder i 마다 4종류의 그룹으로 분류할 수 있다. - sender : attempted[i] == 'Y' && challenged[i] == 'N' - receiver : attempted[i] == 'N' && challenged[i] == 'Y' - both : attempted[i] == 'Y' && challenged[i] == 'Y' - unused : attempted[i] == 'N' && challenged[i] == 'N' unused 그룹에 속한 coder는 답에 아무런 영향을 미치지 못하므로 관심에서 제외한다. 그리고 |sender| < |receiver| 라면 답은 0이다. challenge를 시도하는 사람보다 challenge를 당하는 사람이 더 많은 것은 있을 수 없는 상황이기 때문이다. 우리가 구해야 하는 답은 시간 순으로 정렬된 sequence of challenge attempts 의 가능한 경우의 수이다. 특정한 sequence 하나를 table로 모델링해보자. 구체적으로, 먼저 M x 2 table 을 만든다. 만약 i번째 challenge가 A가 B를 challenge 하는 것이라면 i번째 행의 왼쪽 열에 A를, 오른쪽 열에 B를 적는다. 이런 식으로 table을 채우면 이것이 하나의 sequence가 된다. 그리고 자명하게 M = |sender| + |both| 가 될 것이다. 문제의 조건을 만족하면서 M x 2 table을 채우는 경우의 수를 구하면 우리가 원하는 답이 된다. 먼저 both 그룹에 속한 coder부터 배치해보자. 여기서는 우선 both coder 가 수행한 challenge, both coder 가 당한 successful challenge 만 고려한다. 위의 2가지 케이스만 고려할 경우 i번 both coder 는 왼쪽 열에서 한번, 오른쪽 열에서 한번 등장해야한다. 그리고 왼쪽 열에서 등장한 행 번호를 a, 오른쪽 열에서 등장한 행 번호를 b라고 하면 a < b 를 만족해야한다. 이 경우의 수는 DP로 구할 수 있다. D[n][k] = 구분되지 않는 k명의 both coder를 n x 2 table에 채우는 경우 = D[n-1][k] + (n-k)*D[n-1][k-1] 1) 맨 처음 행의 왼쪽 열이 비어있는 경우 -> D[n-1][k] 2) 맨 처음 행의 왼쪽 열에 both coder를 두는 경우 -> 이 both coder는 그 아래 어딘가에서 오른쪽 열에 등장해야 한다. 이 때, 등장할 수 있는 경우의 수가 n-k가지 이다. (n-k) * D[n-1][k-1] 이제 sender, receiver, both 그룹 모두 함께 배치해보자. (앞으로는 S=|sender|, R=|receiver|, B=|both| 로 나타냄) 먼저, B명의 both coder를 (S+B) x 2 table에 배치한다. -> D[S+B][B] * B! S명의 sender coder를 왼쪽 열의 남은 칸에 배치한다. -> S! 오른쪽 열에 S칸이 남았는데, 여기에 R명의 receiver coder를 배치한다. -> P(S, R) 오른쪽 열에 S-R칸이 남았는데, 이제 여기는 unsuccessful challenge 이므로 아무나 와도 된다. -> (N-1)^(S-R) 따라서 답은 D[S+B][B] * B! * S! * P(S, R) * (N-1)^(S-R) 시간복잡도는 O(N^2) 여기서 한걸음 더 나아가 생각해보면 D[n][k] 는 사실 제2종 스털링 수와 같다는 사실을 알 수 있다. 구체적으로 D[n][k] = S(n, n-k) 이다. 생각해보면, both coder를 k명 배치하는 것은 결국 집합을 n-k개 만드는 것과 같기 때문이다. 이를 이용하면 시간복잡도를 O(NlgN) 으로 줄일 수 있다.