Notable Solved Problems 4호

Posted Jun 3, 2024 Updated Jun 3, 2024

By 7 min read

2024/03/02 ~ 2024/06/03

AI Network Scholarium I #D - Singularity of the Nim

님 게임인데, 어떤 층에서 동전을 취하면 다른 층에 동전이 매우 많이 추가됩니다.
잘 생각해 보면, 임의의 칸에서 x개의 동전을 지우면 무조건 1층에는 x개가 생깁니다.
그렇다면 1층만 생각하면 됩니다. 후공이 무슨 짓을 하던 선공이 1층이 mod $P+1$에서 0인 상태를 유지할 수 있습니다. 따라서 처음 경우에 1층이 mod $P+1$으로 0이 아니면 선공이 이깁니다.
반대면 후공이 이깁니다.

LGV 글에서도 다뤘지만, 답은 다음과 같습니다. $2*(_{M-2}^{N+M-4})^2-(_{N-1}^{N+M-4})\times(_{M-1}^{N+M-4})$

$C_1, C_2, \cdots, C_n$ 중 $m$개를 잘 골라 $L = \sum \min(C_i, k)$, $R = \sum C_i - L$이라 할 때 $L-R$을 최소화하는 문제입니다.
기본적으로 $L=mk$에서 시작합시다. 우리는 $C$를 정렬해 가장 작은 것을 고르거나 가장 큰 것을 고를 수 있습니다.
이때 선택에 따른 ‘이득’을 생각하면, 작은 것을 골라 얻는 이득은 $k-C_i$이고 큰 것을 선택하여 얻는 이득은 $C_j-k$입니다.
- (전자는 L을 작게 만들고 후자는 R을 크게 만듭니다.)
그렇다면, 왼쪽에서 몇 개를 고르고 나머지를 오른쪽에서 고른다고 할 수 있습니다. 양 끝에 있는 것을 고르는 것이 가장 이득이 큽니다.
이중 한쪽에서 몇 개를 가져오는지는 이분탐색으로 구해보면 됩니다. 왼쪽을 너무 적게 고르면 왼쪽을 고르는 것이 이득, 반대는 오른쪽을 고르는 것이 이득이므로, 그 사이 어딘가에 균형점이 있을 것입니다.

문제는 직접 확인하세요.
격자가 가장 촘촘할 때를 기준으로, 점의 xy 좌표합은 홀수입니다.
즉, 격자가 가장 촘촘할 때 두 xy 좌표의 합이 홀수이면 격자 위에 있습니다.
격자의 scale을 늘리면, 좌푯값이 scale의 배수이며 좌표합은 홀수의 scale배입니다.
따라서, xy 좌표합의 모든 홀수 인수에 대해 확인하면 $O(N \sqrt{x+y})$로 섭테 2를 통과할 수 있습니다.
섭테 3을 위해서는 scale의 경우의 수를 $\sqrt{x+y}$ 미만에 찾아야 합니다. 예를 들어, 전처리 $O(x \log x)$에 질의당 $O(k+\log x)$으로 소인수분해를 계산하면 됩니다. (단, $k$는 소인수의 개수)

유향 가중치 그래프에서 두 정점 간의 최단경로 문제를 간선을 $k$개 이하만 사용해서 풀어내는 문제입니다.
$n \leq 70$이므로, 네제곱 정도가 돌아갑니다. 따라서 출발 정점, 도착 정점, 출발 정점으로부터의 거리 3가지를 저장하는 dp를 만들고 네제곱 dp를 모두 하면 됩니다.

원순열에서 연속한 3개를 더해 만든 원순열이 주어지면 원래 답을 복원하면 되는 문제입니다.
크기를 3으로 나눈 나머지가 1이라면, 전체 합과 1개를 제외한 합을 모두 알 수 있으므로 아무 한 칸을 구할 수 있고 답을 구할 수 있습니다.
크기를 3으로 나눈 나머지가 2라면, 전체 합과 연속한 2개를 제외한 합을 알 수 있습니다. 즉 연속한 2개를 알 수 있는데, 연속한 3개도 알고 있으므로 아무 한 칸을 구할 수 있고 답을 구할 수 있습니다.
크기가 3의 배수라면, 인덱스를 3으로 나눈 나머지가 다른 칸끼리는 서로 별개로 움직일 수 있습니다. 따라서, 1번과 2번칸에만 1을 저장하고 채워본 다음, 음수가 나오지 않게 적절한 값을 더해주면 됩니다.
- 답이 존재함을 보장하기 때문에 아무렇게나 해도 됩니다.

This post is licensed under CC BY 4.0 by the author.