2023 KSA Automata Winter Contest

2023 KSA Automata Winter Contest

A - 소수가 아닌 수

1e9

00:02 AC

 

B - 그래서 대회 이름 뭐로 하죠

단순 구현

00:07 AC

 

C - 수학 퀴즈

w^2 + w + 1 = 0 이므로 다음이 성립한다.

• w^2 = -(w + 1)
• w^3 = -(w^2 + w) = 1
• w^4 = w

00:16 AC

 

D - 2배 또는 0.5배

조건을 만족하는 수열은 항상 존재한다.

(i) N % 4 == 0

1 2 4 3 | 5 6 8 7 | ... |

(ii) N % 4 == 1

1 2 4 3 | 5 6 8 7 | ... | N

(iii) N % 4 == 2

1 2 4 3 | 5 6 8 7 | ... | (N - 1) N

(iv) N % 4 == 3

1 3 2 4 | 5 7 6 8 | ... | (N - 2) N (N - 1)

00:30 AC

 

에디토리얼 풀이는 매우 간결하다.

(i) N % 2 == 0

2 1 | 3 4 | 6 5 | 7 8 | 10 9 | ... |

(ii) N % 2 == 1

1 | 3 2 | 4 5 | 7 6 | 8 9 | 11 10 | ... |

 

E - 퀸 움직이기

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

dp[i][j][k][l] = 퀸을 i번 움직였고 마지막 이동이 j번 방향일 때 (k, l) 칸으로 보낼 수 있는 경우의 수

dp 배열을 naive하게 업데이트하면 서브태스크 3까지 맞는다.

서브태스크 4까지 맞으려면 누적 합을 이용하여 효율적으로 업데이트하면 된다.

00:53 AC

 

F - 멋진 부분집합

모든 수를 소인수분해하여 확인하면 서브태스크 2까지 맞는다.

01:19 AC

 

크기가 N / 2인 멋진 집합이 존재한다고 가정하자.

중복집합에서 임의의 원소를 선택하였을 때 해당 원소가 멋진 집합에 속할 확률은 1 / 2이다.

따라서 randomization을 이용하면 높은 확률로 문제를 해결할 수 있다.

01:23 AC

 

2912번에서 배운 테크닉인데 유용하게 잘 사용하였다.

 

G - 시그마 시그마 시그마 시그마

서브태스크 2는 별 도움이 되지 않으므로 생략한다.

다음과 같은 사실을 관찰할 수 있다.

• i < j일 때 max(A[i], A[j])는 (i * (N - j + 1))번 등장한다.

이를 이용하면 서브태스크 3을 해결할 수 있다.

01:39 AC

 

서브태스크 4까지 맞으려면 위의 식을 더 빠르게 계산해야 한다.

각 원소를 역순으로 보면서 다음을 계산해주자.

• sum1 = i < j and A[i] <= A[j]인 모든 j에 대하여 (N - j + 1) * A[j]의 합
• sum2 = i < j and A[i] > A[j]인 모든 j에 대하여 (N - j + 1)의 합

정답은 (i * (sum1 + sum2 * A[i]))만큼 증가한다.

sum1과 sum2는 각각 Fenwick Tree를 이용하여 빠르게 구할 수 있다.

02:02 AC

 

H - 깃발 꽂기

대회 중에 처음으로 푼 다이아 문제이다.

2-sat 문제처럼 보여서 급하게 2-sat을 공부하고 왔다.

아무튼 2-sat 문제로 모델링하면 서브태스크 2까지 맞는다.

03:13 AC

 

구체적으로는 다음과 같이 모델링할 수 있다.

• 지상 통로가 연결하는 두 정점 u와 v에 대하여 (u ∨ v)를 추가한다.
• 구름다리로만 구성된 그래프를 G라고 하자.
• G에서 동일한 연결 요소에 속하는 두 정점 u와 v에 대하여 (￢u ∨ ￢v)를 추가한다.

구름다리 모델링 과정에서 최대 O(N^2)의 간선이 추가되기 때문에 이 방법으로는 서브태스크 3을 해결할 수 없다.

 

위와 같은 상황을 At-Most-One Constraint라고 한다.

정해에서는 이를 위한 특수한 모델링 기법을 사용한다.

여러 기법이 존재하지만 간편하게 사용할 수 있는 것은 다음과 같이 두 가지이다.

• O(N)개의 추가 정점과 O(N)개의 간선을 사용하는 Ladder Encoding
• O(log N)개의 추가 정점과 O(N log N)개의 간선을 사용하는 Binary Encoding

얼핏 보면 간선의 개수가 적은 Ladder Encoding이 빠를 것 같지만 항상 그렇지는 않다.

아무튼 이러한 기법으로 간선의 개수를 줄이면 서브태스크 3까지 해결할 수 있다.

 

하지만 나는 대회 당일 2-sat을 처음 배웠고 이러한 기법을 알고 있을 리가 없다.

지금부터는 나의 꼼수 풀이를 소개한다.

나는 scc를 구할 때 kosaraju 알고리즘을 이용한다.

tarjan 알고리즘을 공부한 지 오래되어 동일하게 적용할 수 있는지는 모르겠다.

 

각 정점은 반드시 하나의 연결 요소에 속한다.

그리고 동일한 연결 요소에 속하는 두 정점 간에는 반드시 간선이 존재한다.

kosaraju 알고리즘의 동작 과정을 살펴보면 정점의 방문 여부가 중요하다는 것을 알 수 있다.

따라서 이미 방문한 정점을 끝점으로 하는 간선은 고려하지 않아도 된다.

 

위의 관찰로부터 간선을 실제로 구성하는 대신 가상으로 관리하는 아이디어를 떠올릴 수 있다.

어차피 중요한 것은 정점들의 방문 여부이고 모든 간선이 실제로 존재할 필요는 없다.

Union-Find와 queue를 이용하면 간선을 실제로 구성하지 않으면서 본래 방문하려고 한 모든 정점을 방문하도록 할 수 있다.

03:44 AC

 

구현도 더럽고 범용적인 풀이는 아니므로 위에서 설명한 모델링 기법을 공부하는 것을 권장한다.

 

I - 이상한 판 뒤집기 게임 (not solved)

풀이가 예술적이다.

에디토리얼을 참고하자.

 

J - 팬케이크 탑 (not solved)

편의를 위하여 p = p / q라고 재정의한다.

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

dp[i][j][k] = i개의 팬케이크 중 j개의 팬케이크가 상했고 마지막 팬케이크는 (k ? "상했을" : "상하지 않았을") 확률

이를 계산하면 서브태스크 2까지 맞는데 대회 중에는 틀렸다.

03:57 WA    03:59 WA

 

H번을 풀고 대략 15분 정도가 남았었고 급하게 코딩에 들어 갔다.

급하게 코딩하다 보니 두 가지 잔실수를 범하였고 대회가 종료될 때까지 원인을 찾지 못하였다.

 

첫 번째 실수는 점화식의 계산 과정에서 나왔다.

dp[i][0][0] = dp[i - 1][0][0] * (1 - p) % MOD;

이전 팬케이크가 상하지 않았을 때 다음 팬케이크도 상하지 않았을 확률은 p이다.

따라서 위의 식에서 (1 - p) 대신 p를 사용해야 한다.

 

두 번째 실수도 점화식의 계산 과정에서 나왔는데 연산 도중 답이 음수가 되는 상황이 생겼다.

아래와 같은 문장을 추가하여 이를 방지할 수 있다.

ans = (ans + MOD) % MOD;

정확히 대회 종료 10초 전에 이를 알아차렸는데 10초는 너무 짧은 시간이었다.

어차피 첫 번째 실수를 고치지 않아 WA는 확정이었다.

 

이제 서브태스크 3을 풀어 보자.

각 팬케이크를 위에서부터 차례대로 확인하자.

이때 한 종류의 팬케이크가 (N + 1) / 2번 등장하는 순간 그 아래에 있는 팬케이크의 종류와는 상관 없이 결과는 확정된다.

따라서 문제에 다음과 같은 조건을 추가할 수 있다.

• 한 종류의 팬케이크가 (N + 1) / 2번 등장하는 순간부터는 그와 반대되는 종류의 팬케이크만 등장한다.

위의 조건을 추가하더라도 답은 변하지 않는다.

 

상한 팬케이크가 더 많다고 가정하자.

추가된 조건에 따라 상한 팬케이크의 개수는 정확히 (N + 1) / 2개이다.

맨 위에 있는 팬케이크와 상한 팬케이크(마지막 것 제외) 바로 밑에 있는 팬케이크는 p의 확률로 상한다.

따라서 상한 팬케이크가 더 많다면 (N + 1) / 2개의 팬케이크는 p의 확률로 상한다.

 

이번에는 상하지 않은 팬케이크가 더 많다고 가정하자.

추가된 조건에 따라 상하지 않은 팬케이크의 개수는 정확히 (N + 1) / 2개이다.

상하지 않은 팬케이크(마지막 것 제외) 바로 밑에 있는 팬케이크는 (1 - p)의 확률로 상한다.

따라서 상하지 않은 팬케이크가 더 많다면 (N - 1) / 2개의 팬케이크는 (1 - p)의 확률로 상한다.

 

잘 생각해보면 문제를 다음과 같이 변형할 수 있다.

• (N + 1) / 2개의 팬케이크는 p의 확률로 상하고 (N - 1) / 2개의 팬케이크는 (1 - p)의 확률로 상한다.
• 이때 상한 팬케이크가 더 많을 확률을 구하시오.

N개의 팬케이크 중 p의 확률로 상하는 것 하나를 제외한 (N - 1)개의 팬케이크만을 고려하자.

그리고 (N - 1)개의 팬케이크 중 상한 팬케이크와 상하지 않은 팬케이크의 개수가 동일하지 않다고 가정하자.

이때 개수의 차이는 2 이상이므로 나머지 한 개의 팬케이크의 종류와는 상관 없이 결과는 확정된다.

또한 (N - 1)개의 팬케이크 중 상한 팬케이크가 많을 확률과 상하지 않은 팬케이크가 많을 확률은 동일하다.

 

이번에는 (N - 1)개의 팬케이크 중 상한 팬케이크와 상하지 않은 팬케이크의 개수가 동일하다고 가정하자.

이 경우에는 나머지 한 개의 팬케이크의 종류에 따라 결과가 결정된다.

(N - 1)개의 팬케이크 중 두 종류의 개수가 동일할 확률을 k라고 하면 답은 다음과 같이 계산할 수 있다.

ans = (1 - k) / 2 + k * p;

 

k는 다음과 같이 구할 수 있다.

int n = (N - 1) / 2;

for i = 0; i <= n; ++i

    k += nCr(n, i)^2 * p^(2 * i) * (1 - p)^(2 * (n - i));

 

끝

끝