https://www.acmicpc.net/contest/view/849
2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 (SUAPC 2022 Summer) Open Contest
www.acmicpc.net
6문제 풀었습니다. 생각보다 잘한 듯?
수학적인 사고력을 요하는 문제가 많네요.
A
, ,
double 이차원 배열 dp를 다음과 같이 정의합시다:
$dp[l][k]$ = (최솟값이 $0$, 최댓값이 $l$인 구간에서 $k$를 찾는 기댓값)
경우의 수를 적당히 잘 나누어주어 기댓값을 저장합니다.
시간 복잡도는 O($2400^2$ + $N$)입니다.
B
그냥 구현
C
$N \leq 10^6$이라는 건 (아마) $O(N^2)$ 풀이가 안 된다는 거고, 딱히 정렬을 하는 방식을 사용할 거 같지 않으므로 $ O(NlogN) $ 풀이도 아닐 겁니다. 그러므로, $ O(N) $ 시간 복잡도를 갖는, 적당한 방법을 직관적으로 찾기를 요구하는 문제인 듯합니다.
일단 $N$이 적혀있는 카드는 가장 먼저 뽑아야 합니다: 안 그러면 $N$을 적혀있는 카드를 뽑는 사람은 패스를 2번 이상 받게 됩니다. 이후 생각이 잘 안 나서, $N \leq 12$에 대해서 브루트포스로 찍어보니, $N$이 짝수일 때만 정답이 구해지더라고요. 그래서 일단 짝수일때만 가능하다고 생각하고 풀었습니다. 풀고나서 생각해보니, $N$이 $3$ 이상의 홀수일 때
$\sum_{n=1}^{N-1} n = \frac{N(N-1)}{2} \equiv 0 (mod N)$ 이기에, 처음 시작하는 사람은 무조건 2번 이상 패스를 받습니다.
$N$이 짝수일 때 처음 시작점을 1이라고 한다면, $2 \to N-1 \to 3 \to N-2 \to ...$ 에게 패스를 하면 된다는 사실을 관찰할 수 있습니다. '직관적인 관찰'이라 어떻게 생각했는지 모르겠네요.
그리고 $N$이 홀수라도 $N=1$일 때는 됩니다. 이 경우만 예외처리해주면 됩니다.
F
일반성을 잃지 않고, $A_1, ... A_N$을 $A_1 < A_2 < ... < A_N$로 정합시다.
차의 개수의 최댓값
$A_i = 2^{i-1}$로 설정하면 차이의 개수는 $N(N-1)/2$개로 최대입니다. $2^{29} < 10$억이라 가능합니다.
차의 개수의 최솟값
$\left|A_2 - A_1 \right| <\left|A_3 - A_1 \right| < ... < \left|A_N - A_1 \right|$ 이므로, 차의 개수의 최솟값은 최소 $N-1$개입니다.
그리고 간단히 $A_i = i$로 결정하면 차의 개수가 $N-1$개가 됩니다.
I
좀 디버깅이 끔찍한 case-work 문제입니다. 일단, 케이스를 좀 편하게 나누기 위해 row, col별로 씨앗의 개수를 세주고, 씨앗이 있는 row, col의 수, 그리고 씨앗이 뿌려져있는 칸의 수를 세줍니다.
1) 만약 씨앗이 뿌려져있는 칸의 수가 $2K$개라면 겹쳐서 씨앗을 뿌리지 않았으므로 $-1$ 출력
2) 1)이 아니라면: $2K$ - '씨앗이 뿌려져있는 칸의 수'개만큼 씨앗을 겹쳐뿌렸습니다. case를 나누어,
I) 씨앗이 있는 row의 수가 1인 경우: 두 명 모두 한 줄에 겹쳐 뿌렸다는 뜻입니다. 몇 개가 겹쳤는지 '씨앗이 뿌려져있는 칸의 수'를 통해 구하고, '겹칠 수밖에 없는' 위치의 씨앗의 좌표를 저장해 출력합니다.
II) 씨앗이 있는 col의 수가 1인 경우: I)이랑 row/col 바꿔서 풀면 됩니다.
III) 그외: 한 명은 세로로, 한 명은 가로로 씨앗을 뿌렸습니다. 이 경우 최대 1곳에서만 만나며, 위 정보를 통해 빠르게 구해줍니다.
$K=1$일 때의 예외 처리를 해줘야할 거 같지만, 2) - I)에서 잘 처리가 됩니다.
그와 별개로 실수하기 참 쉬운 문제입니다. 저는 한 곳에서만 $N, M$을 바꿔썼다가 디버깅이 엄청 오래 걸렸습니다.
M
주제별로 뽑을 수 있는 경우의 수를 $X_i$라고 하면, 정답 $X = \prod_{i=1}^{N} X_{i}$ 이고,
$X_i= \sum_{n=1}^{N} \binom{A_i}{n} \binom{B_i}{n}$ where $N = min(A_i, B_i)$ 입니다.
그리고
$X_i= \sum_{n=1}^{N} \binom{A_i}{n} \binom{B_i}{n} = \binom{A_i+B_i}{N} - 1 $
이 됩니다. 이는
$(1+x)^{A_i+B_i} = (1+x)^{A_i}(1+x)^{B_i}$의 $N$차항의 계수를 비교하면 알 수 있습니다. 찾아보니 Vandermonde's Identity라고 합니다. 수학 전공한거 맞나? ㅋㅋ... 잘 모르겠어서 구글에 대충 쳐서 구했습니다.
그리고, 오일러 소정리를 이용하면, 임의의 소수 $p$에 대해,
$\binom{A_i+B_i}{A_i} \equiv \frac{(A_i+B_i)!}{A_i!B_i!} \equiv (A_i+B_i)!(A_i)!^{p-2}(B_i)!^{p-2} (mod p)$
가 성립합니다. 본 문제에서 $p = 10^{9}+7$입니다.
$1!$ 부터 $(A+B)!$을 미리 구하고, 분할정복을 이용하여 $p$제곱을 계산하기에, 각 쿼리를 $O(logp)$에 처리할 수 있습니다. 시작 복잡도는 $O((A+B) + Nlogp)$.
글 정리하겠다고 학부 시절에는 쳐다도 안 봤던 LaTex 문법을 다 써보네요ㅋㅋ
생각보다 쓰는 방법이 간단해서, 시간 복잡도 '$ O(N) $' 정도의 표현에 대해서는 계속 써야겠습니다.