SciOI 2022 Open Contest

SciOI 2022 Open Contest

A - 카드 뽑기

식을 정리하면 답은 mul(각 수의 등장 횟수 + 1) - 1이 된다.

00:12 AC

 

D - 직육면체

각 면의 면적은 p의 배수가 되므로 적어도 두 변의 길이는 p의 배수여야 한다.

00:21 AC

 

C - 점수 내기

Fenwick Tree로 눈물의 똥꼬쇼를 펼쳤다.

01:09 WA

WA의 원인을 찾지 못해서 stress test를 돌렸고 계산 과정에서 사소한 오류가 있음을 발견하였다.

01:30 AC

 

정해는 dp를 이용하는데 Fenwick Tree 풀이보다 훨씬 간단하다.

다음과 같은 배열 A와 psum을 정의하자.

A[i] = 점수가 i인 학생의 수

psum[i] = sum(A[1 .. i])

 

A와 psum 배열을 이용하여 다음과 같이 dp 배열을 계산할 수 있다.

dp[i] = 점수가 i인 학생이 낸 금액 / y

구체적으로는 다음과 같이 계산할 수 있다.

dp[i] = dp[i + x] + A[i + x] + N - psum[i];

 

B - 최대 점수

왼쪽 구간과 오른쪽 구간을 각각 (비용, 이득) 단위로 분할하여 관리하자.

비용은 점수의 누적 합의 최솟값이며 이득은 현재 누적 합에서 비용을 뺀 것이다.

이득이 양수가 될 때마다 분할하면 된다.

01:42 WA

overflow가 발생하였다.

01:44 WA

그리고 변수명을 혼동하였다.

01:47 AC

 

G - 지뢰 피하기

풀이가 생각나지 않아서 몇 가지 휴리스틱을 시도하였다.

02:29 TLE    02:33 WA    03:26 TLE    03:33 TLE

문득 이분 탐색 + 변형된 bfs 풀이가 떠올랐다.

03:51 AC

이분 탐색이 불필요해 보였는데 실제로 이분 탐색 없이 해결할 수 있다.

에디토리얼에서는 dijkstra를 변형하여 사용하라고 하는데 내가 볼 때는 pq를 사용하는 bfs에 더 가까워 보인다.

 

E - 앤디 공격하기 (not solved)

knapsack dp로 변형할 수 있다.

모두 같은 방향을 보도록 좌표를 적절히 변형하면 보다 간편하게 구현할 수 있다.

 

I - 생물 연구 (not solved)

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

dp[i][j] = 정점 i를 루트로 하는 서브트리에서 깊이가 j인 정점의 개수

모든 정점 u에 대하여 u가 최소 공통 조상인 집합의 개수를 세어보자.

정점 u를 루트로 하는 서브트리에서 모든 깊이 d에 대하여 경우의 수를 세면 된다.

경우의 수는 u의 모든 자식 정점 v에 대하여 mul(dp[v][d - 1] + 1) - sum(dp[v][d - 1]) - 1이 된다.

 

위의 풀이는 O(N^2)이므로 개선이 필요하다.

다음과 같은 배열 H를 정의하자.

H[i] = 정점 i를 루트로 하는 서브트리의 높이

모든 정점 u에 대하여 자식 정점 v를 H[v]가 큰 순으로 정렬하자.

그리고 정렬된 자식 정점들을 각각 A[u][1], A[u][2], ..., A[u][deg(u)]라고 하자.

 

단순하게 생각해보면 H[A[u][2]]를 초과하는 깊이에 대해서는 고려하지 않아도 된다.

따라서 각 정점 u에 대한 연산 횟수는 H[A[u][2]] + sum(H[A[u][2 .. deg(u)]])번이 된다.

기존 풀이에 비하여 연산 횟수는 H[A[u][1]] - H[A[u][2]]만큼 줄어든다.

미미한 차이처럼 보이지만 시간 복잡도는 O(N^2)에서 O(N)이 됨을 증명할 수 있다.

정렬 과정에서 log가 붙어 최종 시간 복잡도는 O(N log N)이 된다.

 

시간 복잡도 증명은 다소 괴랄하다.

hld의 아이디어와 유사한데 자세한 증명은 에디토리얼을 참고하자.

 

아직 dp 배열이 O(N^2)이기 때문에 추가적인 개선이 필요하다.

정점 u에 대한 계산 과정에서 추가적인 연산 없이 dp[u]를 만들 수 있는데 그 방법은 다음과 같다.

• dp 배열은 vector로 구현하며 값은 역순으로 저장한다.
• dp[i][j] = 정점 i를 루트로 하는 서브트리에서 깊이가 (H[i] - j)인 정점의 개수
• 정점 u에 대한 계산 과정에서 dp[H[A[u][1]]의 값을 dp[u]의 값으로 업데이트한다.
• 계산을 마친 후 swap(dp[u], dp[H[A[u][1]])로 dp[u]를 완성한다.

Euler tour technique + 이분 탐색으로도 풀이할 수 있다.

 

H - 영어 시간 (not solved)

잘 관찰해보면 다음과 같은 사실을 발견할 수 있다.

• 모든 점은 왼쪽에서 오른쪽으로 이으며 왼쪽 y 좌표가 증가하는 순으로 잇는다고 가정하자.
• i번째 점까지 이었을 때 오른쪽 점 중 현재 연결된 점의 y 좌표의 최댓값을 maxy라고 하자.
• 이때 i + 1 < maxy가 되는 경우 i + 1 >= maxy가 될 때까지 연결되지 않은 점을 차례로 연결해야 한다.

이를 이용하여 다음과 같은 점화식을 세울 수 있다.

• dp[i][0] = 처음 2 * i개의 점 중 (1, i)와 (2, i - 1)을 제외한 모든 점을 연결하는 경우의 수
• 이때 (2, i)와 연결된 점을 (1, y)라고 할 때 y는 (i - 2) 이하여야 한다.
• dp[i][1] = 처음 2 * i개의 점 중 (2, i)와 (1, i - 1)을 제외한 모든 점을 연결하는 경우의 수
• 이때 (1, i)와 연결된 점을 (2, y)라고 할 때 y는 (i - 2) 이하여야 한다.
• dp[i][2] = 처음 2 * i개의 점을 모두 연결하는 경우의 수

상태 전이는 간단하므로 생략한다.

 

위의 내용을 이해하였다면 O(N^2) 상태 전이는 쉽게 구현할 수 있다.

하지만 N이 크기 때문에 O(N)에 상태 전이를 마쳐야 한다.

문제가 되는 상태 전이는 [2, 0], [1, 0], [2, 1], [0, 1]이다.

누적 합으로 해결될 듯 보이지만 이미 연결된 선분들 때문에 단순하게 해결되지는 않는다.

 

에디토리얼에서도 구체적인 풀이는 언급하지 않으므로 나의 구현을 설명하고자 한다.

그리고 문제가 되는 상태 전이는 거의 유사하므로 [2, 0]만 설명하고자 한다.

사실 dp[i][0]은 두 개의 경우로 나누어 생각할 수 있다.

(2, i)와 연결되는 점을 (1, y)라고 하자.

 

(i) y가 이미 결정된 경우

y < k < i인 k에 대하여 (1, k)는 (2, k - 1)과 연결되어야 한다.

이를 만족하면 dp[y - 1][2]에서 dp[i][0]으로 상태가 전이된다.

 

(ii) 그렇지 않은 경우

y < k < i인 k에 대하여 (1, k)는 (2, k - 1)과 연결되어야 한다.

그리고 (1, y)와 연결된 점은 존재하지 않아야 한다.

이를 만족하는 모든 y에 대하여 dp[y - 1][2]에서 dp[i][0]으로 상태가 전이된다.

 

이렇게 나누어서 생각하면 누적 합을 적용하기 쉬워진다.

나는 추가적으로 sum과 cnt 배열을 정의하였는데 이들의 역할은 다음과 같다.

• sum[0] = 선분 {(1, i), (2, i - 1)}이 유망하고 (1, i - 1)과 연결된 점이 존재하지 않는다면 dp[i - 2][2]를 누적한다.
• sum[1] = 선분 {(2, i), (1, i - 1)}이 유망하고 (2, i - 1)과 연결된 점이 존재하지 않는다면 dp[i - 2][2]를 누적한다.
• sum[2] = (1, i - 1)과 연결된 점이 존재하지 않는다면 dp[i][0]을 누적한다.
• sum[3] = (2, i - 1)과 연결된 점이 존재하지 않는다면 dp[i][0]을 누적한다.
• cnt[0] = 선분 {(1, i), (2, i - 1)}이 유망하다면 증가시킨다.
• cnt[1] = 선분 {(2, i), (1, i - 1)}이 유망하다면 증가시킨다.

경우에 따라 적절히 초기화해주면 된다.

 

F - 공격 릴레이 (not solved)

Pass

 

J - 비밀 기지 (not solved)

Pass

 

끝

끝