2022 제1회 미적확통컵

2022 제1회 미적확통컵

A - 연속인가? ?

단순 수학

00:01 AC

 

B - 수열의 극한값

정리하면 b와 c만으로 구성된 공식이 나온다.

00:09 AC

 

G - 균등분포와 정규분포

0 또는 1에 가까운 값의 개수를 세면 된다.

00:18 AC

 

H - 방향 정하기

한 점씩 결정해나간다고 생각하면 매우 단순한 공식이 나온다.

00:23 AC

 

I - 빙고

기댓값의 선형성을 이용하여 잘 계산하면 된다.

00:51 AC

 

C - 함수와 최소 스패닝 트리

모든 간선에 대하여 a는 동일하므로 간선의 가중치는 일차함수로 생각할 수 있다.

이때 두 일차함수의 교점에서 두 간선의 우열 관계가 뒤집히게 된다.

모든 교점에 대하여 적분값을 나누어서 계산해주면 된다.

분수 계산이 자주 등장하므로 분수 자료형을 정의하는 것을 권장한다.

01:29 WA    01:30 WA    01:33 WA    02:09 WA    02:13 AC

 

WA를 받은 이유는 다음과 같다.

• 실수 자료형을 사용하여 실수 오차가 발생하였다(추정).
• 모듈러 연산 과정에서 실수를 많이 하였다.

두 간선을 비교할 때 두 시점의 평균값을 이용하면 보다 쉽게 구현할 수 있다.

 

더 이상 풀 수 있는 문제가 없다는 확신이 들었다.

배고파서 밥 먹으러 갔다.

 

D - 다항함수의 적분과 쿼리 (not solved)

정리하면 다음과 같은 결론을 도출할 수 있다.

ans_0_1 = 3A_1 + 3A_0

ans_0_2 = 2A_2 + 8A_1 + 2A_0

ans_0_3 = 2A_3 + 8A_2 + 5A_1 + 3A_0

ans_0_4 = 2A_4 + 8A_3 + 4A_2 + 8A_1 + 2A_0

ans_0_5 = 2A_5 + 8A_4 + 4A_3 + 8A_2 + 5A_1 + 3A_0

ans_0_6 = 2A_6 + 8A_5 + 4A_4 + 8A_3 + 4A_2 + 8A_1 + 2A_0

...

규칙을 찾아서 적절히 업데이트해주면 된다.

 

두 개의 Fenwick Tree로 관리할 수 있다.

첫 번째 Fenwick Tree에서는 다음 값을 관리해준다.

8A_1 + 4A_2 + 8A_3 + 4A_4 + 8A_5 + ...

두 번째 Fenwick Tree에서는 다음 값을 관리해준다.

4A_1 + 8A_2 + 4A_3 + 8A_4 + 4A_5 + ...

 

E - 연립방정식 (not solved)

구글링해서 풀었는데 무슨 말인지 모르겠고 알고 싶지도 않다.

 

J - 살얼음판 걷기 (not solved)

두 사람이 동일한 칸을 밟지 않고 1번 칸에서 N번 칸으로 이동하는 경우의 수를 구하면 된다.

1 < i < N인 i에 대하여 i번 칸은 다음과 같은 선택지가 있다.

• 두 사람 모두 밟지 않는다.
• 첫 번째 사람이 밟는다.
• 두 번째 사람이 밟는다.

따라서 다음과 같은 점화식을 세울 수 있다.

dp[i][j] = 첫 번째 사람과 두 번째 사람이 각각 i번 칸과 j번 칸에 있는 경우의 수

이때 max(i, j)번 칸을 포함하여 모든 이전 칸은 더 이상 사용할 수 없다.

 

각 상태 전이 횟수가 O(K)번이므로 TLE를 받는다.

누적합 배열을 정의하거나 점화식을 다음과 같이 변형할 수 있다.

dp[i][j] = dp[i - 1][j] + (첫 번째 사람과 두 번째 사람이 각각 i번 칸과 j번 칸에 있는 경우의 수)

 

K - 당근과 채찍 (not solved)

임의의 경우에 대하여 기분 변화 그래프를 그려보자.

이때 최솟값이 시작점이 되도록 배열을 적절히 회전시키면 문제의 조건을 만족하게 된다.

전체 경우의 수는 C(a + b, a)이고 배열을 회전시키는 경우의 수는 (a + b)이다.

따라서 답은 C(a + b, a) / (a + b)가 된다.

 

L - 이항분포에서 가장 큰 직사각형 (not solved)

먼저 각 막대의 높이를 계산해야 한다.

수가 굉장히 작아지거나 커질 위험이 있기 때문에 log를 씌워서 계산해야 한다.

lgamma 함수를 이용하면 계승의 log 값을 계산할 수 있다.

 

높이를 구한 후에는 각 query에 대하여 가장 큰 직사각형을 찾아야 한다.

이는 매우 어려운 문제인데 다음과 같은 문제의 성질을 이용하면 보다 쉽게 풀이할 수 있다.

• 각 막대의 높이는 증가하다가 감소하는 형태이다.
• 평균과 거리가 먼 막대는 높이가 0에 가깝다.

수학적으로 계산하였을 때 평균과 1100 이상 떨어진 막대의 높이는 0으로 간주하여도 무방하다.

따라서 O(N^2) dp가 가능한데 다음과 같은 점화식을 세울 수 있다.

dp[i][j] = max((j - i + 1) * minv, dp[i][j - 1], dp[i + 1][j])

 

F - 이차함수와 직선 (not solved)

Pass

 

끝

끝