대회 결과
신촌지역 대학생(5개 대학..?) 프로그래밍 대회 동아리 연합 여름대회 Open이다. 본대회는 팀짜서 하는 대회인 것 같다. 이 대회 하면서 배운게 많아서 정리해야겠다 싶었다. (사실 플레 3개 푼거 박제하고 싶었다) 문제 세트는 https://www.acmicpc.net/category/detail/3855 에서 확인할 수 있다.
L. (AC/+13min) - priority_queue
우선순위 큐 11개 만들어서 잘 push, pop해주면 된다. 시간복잡도는 $O(NlogN+11KlogN)$이다.
G. (AC/+19min) - greedy, sorting
5개의 level마다 무조건 시간이 작은 것부터 풀어주면 가장 빠르게 푼다는 사실을 알 수 있다.
K. (AC/+44min) - geometry, math, number_theory
직사각형을 통과하는 직선이 넓이를 반으로 나누기 위해서는 직사각형의 중심을 통과해야 한다. 변이 축에 평행하지 않을 수 있기 때문에, 중심은 다음과 같이 구했다.
- 직사각형을 이루는 4개의 점을 x,y좌표 기준으로 정렬했을 때 1, 4번째 점을 잇는 선분은 항상 대각선이다. 즉, 직사각형의 중심 좌표는 이 선분의 중심이다.
두 직사각형의 중심점을 $(x_1, y_1)$, $(x_2, y_2)$라 할 때, $y=ax+b$는 이 두 점을 지나가야 한다. $a, b$는 정수가 아닐 수 있기 때문에, 분모 분자 따로 구해서 최대공약수로 나눠준 후, 분자가 음수면 바꿔주고 분모가 1이면 정수로 출력하는 case work 잘 해주자.
$a = \displaystyle \frac{y_1-y_2}{x_1-x_2}$, $b = \displaystyle \frac{y_1(x_1-x_2)-x_1(y_1-y_2)}{x_1-x_2}$ 이다.
I. (AC+1/+122min) - combination, inclusion_exclusion, fermat_little_theorem
시간제한이 0.5초라 고전했던 문제...
먼저, $n \times m$ 격자에서 경우의 수는 ${}_{n+m} \mathrm{C}_{m}$ 이다. $n, m \leq 1000000$이므로, $1!$ 부터 $(n+m)!$를 모두 구해준다. 그럼 이제 ${}_{n+m} \mathrm{C}_{m}$를 $O(log(MOD))$에 구할 수 있다. 이 때 페르마의 소정리를 활용한다.
* 페르마의 소정리란?
$MOD$가 소수일 때, $n^{MOD-1} \equiv 1$ $(mod\, MOD)$ 가 항상 성립한다. 즉, $n^{MOD-2} \equiv \displaystyle \frac{1}{n}$ $(mod\, MOD)$ 도 성립한다.
보통 자주 나오는 $MOD$ 값인 1e9+7, 998244353 등은 모두 소수이므로, 모듈러 나눗셈을 진행할 때 페르마의 소정리를 활용해야 한다. 여기에 더해 $MOD$가 10억 scale이므로 naive한 곱셈이 아닌 분할정복으로 빠르게 ($O(logMOD)$만에) 거듭제곱을 해야 한다.
그렇게 전처리를 했다면, $K \leq 20$개의 폭탄에 대해 하나 이상 밟는 경우의 수를 구해야 한다. 여기서 하나 이상 밟는 경우의 수나 하나도 밟지 않는 경우의 수를 바로 구하기에는 어려움이 있으나 AND 조건을 구하기는 쉬울 때, 우리는 포함-배제의 원리를 활용할 수 있다.
* 포함-배제의 원리란?
가 성립한다.
여기서 좌변은 폭탄을 하나 이상 밟는 경우의 수이고, 우변의 경우의 수를 모두 구해주면 정답을 구할 수 있다. 즉, $2^K$개의 경우의 수를 모두 구해야 한다.
* 시간복잡도의 늪으로...
$2^K$개의 경우의 수를 각각 구하는 데에 드는 시간복잡도는 $O(Klog(MOD))$이다. 총 시간복잡도는 $O(N+M+2^KKlog(MOD))$가 되어, 시간 초과가 뜬다.
최적화 방안 1. $(n+m)!^{MOD-2}$를 미리 구해두자! -> 시간복잡도는 $O((N+M)log(MOD)+2^KK)$이다. $2^KK \geq N+M$이므로 최적화된 것 같지만, 여전히 1초 이상 나온다.
최적화 방안 2. 실제로 쓰는 ${}_{n+m} \mathrm{C}_{m}$만 구해두자! -> 생각해보면 $K$개의 폭탄이 있을 때, $(0, 0)$, $(N, M)$까지 합치면 $(K+2)^2$개 정도의 조합 값만 필요함을 알 수 있다. 이것들만 먼저 구해준다면 $O(N+M+K^2log(MOD)+2^KK)$가 되어 약 200ms로 통과할 수 있다.
H. (AC/+142min) - prefix_sum
탭의 전체 길이를 $SUM$, 화면의 길이를 $L$이라 하고, 각 쿼리마다 그 탭이 중간에 있을 때 왼쪽 탭들 길이를 $P$로 둔다. 이 값은 쿼리 시작 전 누적합으로 구해 $O(1)$에 구할 수 있도록 전처리한다.
답은 $P-\frac{L}{2}$로, $0 \leq P-\frac{L}{2} \leq SUM-L$인지 확인해서 범위 밖에 있으면 예외처리한다. 시간복잡도는 $O(N+Q)$이다.
D. (AC/+209min) - dynamic_programming
2차원 격자에서 위로 갈 수 없다는 점이 힌트이다. 아래로 항상 $N-1$번 이동해야 하고, 좌우로 이동하는 경우만 생각하면 된다. 먼저 각 행마다 $(i_l,i_r)$값을 구하는데, 이 값은 행에서 가장 왼쪽에 있는 기계, 가장 오른쪽에 있는 기계를 의미한다. 행에 있는 기계가 하나도 없을 때는 따로 마스킹해준다. 또, 하나도 없는 행이 연속해서 여러 개 나오면 하나로 합친다.
다음은 $N \times 2$ DP 배열을 만든다. $dp(i,j)$는 $i$번째 행에서 0이면 왼쪽, 1이면 오른쪽으로 이동하는 경우를 의미한다. 전이함수를 짤 때 $i$번째 행에 기계가 있는지 없는지 case 나눠줘야 한다.
$dp(0,0) = -1, dp(0,1) = i_r+1$
$i$번째에 기계가 없을 때,
$dp(i,0) = (i_r-i_l) + min( dp(i-1,0)+|(i-1)_l-i_r|, dp(i-1,1)+|(i-1)_r-i_r| )$
$dp(i,1) = (i_r-i_l) + min( dp(i-1,0)+|(i-1)_l-i_l|, dp(i-1,1)+|(i-1)_r-i_l| )$
$i$번째에 기계가 있을 때,
$i_r \leq (i-1)_l$이면 동일, 아니면 $dp(i,0) = (i_r-i_l) + dp(i-1,1)+|(i-1)_r-i_r|$
$(i-1)_r \leq i_l$이면 동일, 아니면 $dp(i,1) = (i_r-i_l) + dp(i-1,1)+|(i-1)_r-i_l|$
정답은 $dp(n-1, 1)+(n-1)$이다.
J. (AC/+239min) - greedy, sorting, number_theory
동작 2는 필요없음을 알 수 있다. 또, 동작 1을 통해 될 때까지 소인수분해하는 것이 무조건 유리함을 알 수 있다. 그렇게 소인수분해 한 후 https://www.acmicpc.net/problem/16496(큰 수 만들기) 아이디어를 활용해 정렬해준다. 다만 C++에서는 수가 ull 범위도 벗어나므로, string으로 저장해 큰 수 덧셈을 구현해야 한다.
성현이가 만들 수 있는 수는 그렇게 $O(\sqrt {n} + log^2{n})$에 구할 수 있고, 지훈이가 만들 수 있는 가장 큰 수는 어떻게 구할 수 있을까?
$N$보다 작은 $2^a$, $3 \times 2^a$ 중 가장 큰 값이 정답이다. 소인수가 4 이상이면 작아질 수밖에 없고, 3 이상이 2개 이상 있으면 33 < 222 이므로 항상 불리하기 때문이다.
E, F (Upsolving 예정)
'CF&AC&Open' 카테고리의 다른 글
| [Educational Codeforces #107] A~D번 풀이 (0) | 2022.06.23 |
|---|---|
| [Codeforces Round #714] A, B, C번 풀이 (0) | 2022.06.20 |