나는코더다 2022 송년대회 Open Contest

대회 리뷰/BOJ

나는코더다 2022 송년대회 Open Contest

hijkl2e 2023. 1. 24. 16:05

www.acmicpc.net

A - 시로코와 은행털기

knapsack dp

00:07 AC

E - 겨울 축제

감동 수치가 i인 팀 K개를 합치면 감동 수치가 (i + 1)인 팀이 만들어진다.

이러한 방식으로 최대한 많은 팀을 합치면 된다.

선택되지 않은 팀은 다시 K개의 팀으로 분할해야 한다.

00:47 WA

변수명을 혼동하였다.

00:49 AC

I - 다오의 행사 계획하기

LCA + 누적 합

01:20 AC

B - 캠핑하기

식을 정리하면 일차함수의 최댓값을 구하는 문제가 된다.

후보 함수를 적절히 관리하면서 해결하였다.

02:52 WA

수식에 오류가 있었다.

02:57 WA

여전히 수식에 오류가 있었다.

02:58 RTE

iterator 사용이 미흡하였다.

03:02 AC

정해는 cht인데 내 풀이의 아이디어도 cht와 굉장히 유사하였다.

이참에 cht를 공부하였는데 코드가 매우 깔끔해졌다.

F - infinite XYZ (not solved)

먼저 N개의 정점을 3N개로 분할할 수 있다.

원본 그래프에 사이클이 존재한다면 모든 query의 답은 1이 된다.

그렇지 않다면 매 query마다 사이클의 생성 여부를 확인해야 된다.

원본 그래프에 사이클이 존재하지 않는다면 해당 그래프는 dag이다.

dag에 간선을 추가하였을 때 사이클의 생성 여부를 확인하는 작업은 매우 어렵다.

실제로 가능한지도 모르겠다.

여러 방법을 시도하였으나 장렬히 전사하였다.

03:50 WA 04:20 WA 04:31 WA 04:32 WA 04:47 RTE

문제에 간과하기 쉬운 조건이 달려 있었다.

바로 한 정점에서 뻗어나오는 간선의 문자는 서로 겹치지 않는다는 것이다.

이 조건으로 인하여 원본 그래프에 사이클이 존재하지 않는다면 해당 그래프는 트리가 된다.

원본 그래프가 트리이므로 Euler tour technique으로 문제를 쉽게 해결할 수 있다.

H - 주고받기 (not solved)

우선 선물을 받지 못한 학생이 존재한다면 답은 0이 된다.

그렇지 않다면 주어지는 정보로 functional graph를 만들 수 있다.

이때 모든 정점은 반드시 임의의 사이클에 속하게 된다.

이제부터는 사이클의 크기와 개수만 보면 된다.

3번 규칙을 x번 반복하였을 때의 그래프를 Gx라고 하자.

이 문제는 GK가 주어졌을 때 가능한 G1의 개수를 구하는 문제로 변형할 수 있다.

이때 GK에서 임의의 사이클에 속하는 정점들은 G1에서도 동일한 사이클에 속하여야 한다.

G1에서의 임의의 사이클을 c1이라고 하자.

그리고 g = gcd(K, sz(c1))이라고 정의하자.

3번 규칙을 K번 반복하면 사이클 c1은 크기가 sz(c1) / g인 사이클 g개로 분할된다.

관점을 바꾸어 말하자면 GK에서 크기가 sz(c1) / g인 사이클 g개는 하나의 사이클로 합칠 수 있다.

변수명을 바꾸어 말하자면 GK에서 크기가 x인 사이클 y개는 크기가 xy인 하나의 사이클로 합칠 수 있다.

이때 y = gcd(K, xy)이므로 추가적으로 다음 조건을 만족하여야 한다.

K는 y의 배수여야 한다.
K / y와 x는 서로소여야 한다.

핵심적인 관찰은 모두 끝났고 이제 dp로 경우의 수를 계산하면 된다.

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

우선 사이클의 크기 x에 대하여 가능한 y를 모두 구한다.

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

dp[i] = 크기가 x인 사이클 i개를 합치는 경우의 수

가능한 모든 y에 대하여,

dp[i] += dp[i - y] * fact(y - 1) * pow(x, y - 1) * nCr(i - 1, y - 1);

에디토리얼에서는 다른 점화식을 사용하는데 많이 복잡하고 시간 복잡도도 크다.

그래도 공부할 가치는 충분하니 참고해보자.

D - 돌게임과 쿼리 (not solved)

(X + I)개의 돌을 하나의 묶음으로 생각하자.

이제 관찰에 관찰을 거듭하면 된다.

가져가는 묶음의 수가 결정되면 가져갈 수 있는 돌의 개수의 범위도 결정된다.
묶음의 수가 증가하면 돌의 개수의 하한과 상한 모두 증가한다.
하한과 상한 사이에 있는 모든 x에 대하여 x개의 돌을 항상 가져갈 수 있다.
x 또는 y(x < y)개의 묶음을 가져갈 때 N개의 돌을 모두 가져갈 수 있다고 가정하자.
이때 y개의 묶음을 가져갈 때의 최소 턴 수는 x개의 묶음을 가져갈 때의 최소 턴 수 이하이다.

증명은 나름 직관적이므로 생략한다. 일부 증명은 에디토리얼에서 확인할 수 있다.

이제 위의 관찰을 바탕으로 풀이를 완성해보자.

먼저 묶음의 수 Y를 결정해야 하는데 이는 이분 탐색으로 구할 수 있다.

구체적으로 가져갈 수 있는 돌의 개수의 하한이 N 이하가 되는 묶음의 수 중 최댓값을 구하면 된다.

이제 Y를 바탕으로 최소 턴 수를 결정해야 하는데 이 역시 이분 탐색으로 구할 수 있다.

구체적으로 가져갈 수 있는 돌의 개수의 상한이 N 이상이 되는 턴 수 중 최솟값을 구하면 된다.

이러한 값이 존재하지 않는다면 답은 Y가 된다.

이렇게 매 query마다 이분 탐색 두 번으로 답을 구할 수 있다.

수식이 약간 복잡하므로 실수하지 않도록 조심해야 한다.

G - 수열과 구간과 구간과 구간과 쿼리 (not solved)

이분 탐색 문제로 바꾸어서 생각해보자.

avg(A[x .. y])이 M 이상이 되는 x, y가 존재하는지 확인하면 된다.

S[i] = sum(A[1 .. i])로 정의하고 식을 정리하면 다음과 같아진다.

avg(A[x .. y]) >= M

sum(A[x .. y]) / (y - x + 1) >= M

sum(A[x .. y]) >= M * (y - x + 1)

S[y] - S[x - 1] >= M * y - M * (x - 1)

S[y] - M * y >= S[x - 1] - M * (x - 1)

양변 모두 일차함수 형태이므로 Segment Tree + cht로 최댓값 또는 최솟값을 찾으면 된다.

(Li Chao Tree를 말하는 것이 아니다)

구체적으로 Segment Tree의 각 노드에서 해당 구간이 포함하는 직선들을 관리하면 된다.

Merge Sort Tree와 어느 정도 유사한 면이 있다.

C - 합의 곱의 절댓값의 최댓값 (not solved)

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

dp[i][j] = A[1 .. j]에서 |S[1] * S[2] * ... * S[i]|의 최댓값

결론만 말하자면 dnc opt가 가능하다.

엄밀한 증명은 상당히 복잡하지만 나름 직관적으로 보이기는 한다.

증명은 에디토리얼을 참고하자.

여담으로 cht 풀이도 가능하다고 한다.

J - 통역사 (not solved)

편의를 위하여 도시의 번호는 2번부터 시작하고 i번 도시는 i번 언어를 사용한다고 가정하자.

N과 K 역시 각각 N + 1과 K + 1로 생각하면 된다.

p가 K보다 커지면 K의 p진법 표현은 [K]가 되고 이러한 p에 대하여 적절한 q는 존재하지 않는다.

따라서 2 이상 K 이하의 p만 고려하면 된다.

naive 풀이는 다음과 같이 구현할 수 있다.

for p = 2; p <= K; ++p

a = K의 p진법 표현

q = max(a) + 1

while true

x = a를 q진법으로 해석한 결과

if x > N then

break

cost[x] = min(cost[x], p + q++)

naive 풀이는 TLE를 받는다.

일반적으로 naive 풀이는 크게 도움이 되지 않는다.

하지만 이 문제는 naive 풀이를 약간만 개선시키면 AC를 받을 수 있다.

아쉽게도 개선에 필요한 관찰이 쉬운 편은 아니다.

Step 1

K의 p진법 표현은 두 자리 이상이다.

그런데 p진법 표현이 세 자리 이상이 되는 p는 O(sqrt K)개 이하이다.

따라서 두 자리인 경우만 개선하여도 충분하다.

Step 2

K의 p진법 표현을 [a b]라고 할 때 (p + 1)진법 표현은 다음과 같이 나타낼 수 있다.

if a <= b then [a (b - a)]

else [(a - 1) (b - a + p + 1)]

Step 3

K의 p진법 표현이 [a b]이고 (p + 1)진법 표현이 [a (b - a)]라고 가정하자.

그리고 i진법 표현에서 가능한 x의 집합을 X_i라고 하자.

이때 X_p는 X_p+1의 부분 집합이다.

Step 4

K번 언어를 i번 언어로 통역하는 (p, q)가 여러 개 존재한다고 가정하자.

이때 p1 < p2이면 q1 < q2를 만족한다.

따라서 이미 업데이트된 x는 고려하지 않아도 된다.

다시 말하자면 X_p+1의 원소 중에서 X_p에 포함되지 않는 원소만 고려하면 된다.

이를 이용하여 naive 풀이를 개선할 수 있는데 구체적으로는 다음과 같이 구현할 수 있다.

K의 p진법 표현이 두 자리인 경우 cost[x]를 업데이트함과 동시에 vst[x]를 a로 업데이트한다.

이미 vst[x]가 a라면 x를 포함한 이후 모든 원소들은 이미 업데이트가 완료되었다는 뜻이다.

따라서 업데이트를 중단하고 그다음 p에 대하여 시도하면 된다.

티스토리