NSP 6호

2024/10/19 ~ 2025/05/08

밀린 것을 처리하느라 쉽거나 재미없는 문제들은 최대한 버렸습니다. 플레 중반 이하의 문제, 대회 중에 푼 문제 중 대회에 대한 후기를 적은 적이 있는 문제, 내/외부검수로 참가한 (특히 경곽) 문제, 그냥 풀이가 노잼인 문제 등을 버렸습니다. 그럼에도 어려운 문제들이 많아서 분량이 조금 많습니다.

NWERC 2017 #J. Juggling Troupe

• 길이 N의 배열에 0, 1, 2 중 하나가 써져 있습니다. 2가 써져 있는 칸에 대해, 그 칸에서 2를 빼고 이웃한 칸에 각각 1을 더합니다. (이웃한 칸이 하나밖에 없러도 한쪽에만 1을 더합니다.)
• 이걸 모든 칸에 한 번씩 하는 것을 하나의 스텝이라 할 때, 2가 없어질 때까지 몇 번의 스텝이 필요한지 구하면 됩니다.
• 각 ‘2’가 어떻게 움직이는지를 확인하면 됩니다. 0으로 감싸진 어떤 subarray에 2가 하나 있다면, 열심히 움직인 뒤에는 2의 위치의 subarray 중심 기준 선대칭점에 0이 생깁니다.
• 그러므로 각 2에 대해 0이 어디로 가게 되는지를 적절히 셋 등으로 관리해주면 됩니다.

APIO 2024 #C. Magic Show

• ibm2006의 투스텝 문제입니다. 인터랙션은 다음과 같습니다:
  • A가 C에게 정수 $2\leq n\leq 5000$을 전달합니다.
  • C가 A에게 정수 $1\leq X\leq 10^{18}$을 전달합니다.
  • A가 C에게 정점 $n$개의 트리를 전달합니다.
  • C가 트리에서 최대 $[n-2]/2$개의 간선을 삭제하고, 남은 간선을 B에게 전달합니다.
  • B가 $X$를 맞춥니다.
• 즉, 트리에 큰 정수의 정보를 리던던트하게 잘 담아내는 것이 관건인 문제입니다.
• 정해는 존존나 어려운데, 사실 그냥 CRT를 잘 하면 됩니다. 2 이상 $n$ 이하의 모든 정수 $i$에 대해, $X$를 $i$으로 나눈 나머지와 $i$를 이어주면 트리가 만들어집니다.
• 여기서 간선을 어떻게 지워도 과반의 간선이 남기 때문에, $n$ 이하의 모든 소수에 대해 그 소수로 나눈 나머지가 저장됩니다. 따라서 $n$을 500 정도로 잡아도 매우 넉넉하게 문제를 해결할 수 있습니다.
• 여담으로, 푼 지 반년이 지난 지금도 맞힌 사람 탭과 숏코딩 탭 모두 제가 압도적 1등을 차지하고 있습니다. 왜일까요.

ICPC Seoul 2019 #C. Islands

• 길이 $N$의 두 원순열이 있습니다. 이 원순열을 원 위에 그린 다음 어떤 순열을 제시해서 그 순열의 순서대로 원 위의 점을 방문하는 것을 생각할 수 있습니다. 두 원순열에 대해서, 두 경로가 각각 자신과 교차하지 않도록 하는 순열을 찾거나 찾을 수 없음을 보이면 되는 문제입니다.
• 어떤 ‘부분경로’, 즉 전체 경로의 연속한 일부 구간, 은 두 원순열 모두에서 연속한 구간을 차지합니다.
• 그러므로 제곱 풀이를 구현하는 것은 쉽습니다. 모든 정점을 순회하면서, 그 정점을 시작점으로 하여 추가할 수 있는 정점이 나올 때마다 하나씩 추가합니다. (두 원순열 모두에서 지금까지의 부분경로에 인접해 있는 수가 나온다면 그 정점을 추가할 수 있습니다.)
• 여기서 상수를 자르기 위해 다음을 추가합시다: 어떤 부분수열을 체크하여 그 부분수열을 사용할 수 없음을 확인할 때마다, 그 부분수열에 있는 모든 점은 다시 탐색하지 않습니다.
• 시작점이 $i$일 때 답이 있고, 시작점이 $j$일 때 $i$를 포함하는 답을 구할 수 있으면, 시작점이 $j$일 때도 답을 구할 수 있습니다. 그러므로 위와 같은 최적화를 해도 된다는 사실은 어렵지 않게 알 수 있습니다.
• 이때, 어떤 정점을 탐색하려면 그 정점에서 시작하거나 그 정점에 해당하는 A나 B 위의 점의 이웃한 점에서 접근해야 합니다. 따라서 위와 같이 풀이하면 아무리 커도 $O(5N)$에 풀 수 있습니다. 그래서 놀랍게도 위 최적화는 $O(N)$입니다.

NEERC Northern Subregional 2018 #L. LED-led Paths

• DAG가 주어집니다. 각 간선을 3가지 색으로 채색하되, 같은 색이 42번보다 많이 연속하는 path가 생기지 않아야 합니다.
• indegree가 0인 정점에서 시작해서 bfs하면서 탐색한 순서대로 정점을 오더링합시다. 그러면 모든 path는 수가 작은 점에서 큰 점을 향합니다.
• 40진법으로, 두 정점의 1600의 자리부터 다르면 빨간색, 40의 자리부터 다르면 초록색, 1의 자리만 다르면 파란색으로 칠합시다. $40^3=64000$이므로, 빨간색 경로는 최대 40의 길이를 가지고 초록/파란색은 39를 가집니다. 따라서 문제가 풀립니다.
• COCI 2020/2021 Contest 4 #3. Hop을 같은 방법으로 풀 수 있습니다.

SUAPC 2022 #G. AND, OR, XOR

• 길이 $N$의 수열과 정수 $K$가 주어지면, AND, OR, XOR가 K인 수열 위의 서로 다른 두 수의 쌍의 개수를 연산별로 계산하면 됩니다.
• XOR는 값 하나에 대해 나머지 값이 정해지므로 쉽게 풀 수 있습니다.
• AND는 $K$의 비트를 모두 포함하는 $A$의 원소에 대해서만 해결하면 되며, 이때 그러한 수에서 $K$를 다 빼면 $K=0$인 경우의 문제를 푸는 것과 같습니다. SOS DP를 딸깍하면 됩니다.
• OR는 뒤집으면 AND와 같으므로, 똑같이 풀면 됩니다.

ICPC Yokohama 2024 #I. # Greatest of the Greatest Common Divisors

• 수열이 주어집니다. 쿼리로 수열의 부분구간이 주어지면, 그 구간에서 두 수를 뽑아 얻을 수 있는 gcd의 최댓값을 출력해야 합니다. 수열의 길이와 쿼리의 수와 각 값의 최댓값은 모두 10만입니다.
• 10만 이하의 모든 수에 대해, 수열의 $1$~$i$번째 수들 중에서 그 수를 약수로 가지는 오른쪽에서 첫 번째, 두 번째 값의 위치를 관리합시다.
• 그러면서 각 쿼리를 오프라인으로 처리하면 됩니다. 오른쪽에서 두 번째 값이 구간의 왼쪽 끝보다는 오른쪽에 있기만 하면 그 수를 gcd로 갖는 두 값이 존재하는 것입니다.
• 위를 세그트리 같은 걸로 관리하면 됩니다.

SUAPC 2025 Winter #H. 완전 그래프와 쿼리

• $N$개의 정점이 있습니다. 여기에 다음과 같이 간선을 추가할 수 있습니다:
  • 정점 하나와 어떤 수 $x$를 잡아서, $x$와 서로소인 모든 정점과 정점을 잇거나 $x$와 서로소가 아닌 모든 정점과 정점을 잇습니다.
• 이를 통해 완전 그래프를 만드려면 필요한 쿼리의 최소 수를 구하는 문제입니다.
• 2의 배수를 모두 모아봅시다. 이것들이 완전 그래프를 이루도록 하려면 적어도 2의 배수 중 하나를 제외한 모든 값에 대해 2번 쿼리를 실행해야 합니다.
• 3의 배수를 모두 모아봅시다. 마찬가지로 하나를 제외한 모든 값에 2번 쿼리를 돌려야 합니다.
• 이를 반복하면 적어도 합성수의 개수만큼은 쿼리를 돌려야 합니다.
• 홀수를 모두 모아봅시다.

ICPC Yokohama 2022 #G. Remodeling the Dungeon

• 격자 그래프에서 간선이 몇 개만 남아있는 트리가 주어집니다. 여기서 간선 하나를 지우고 하나를 추가해서 왼쪽 위에서 오른쪽 아래로 가는 최단경로의 길이를 최대화하고 싶습니다.
• (트리는 어쨌든 연결그래프이므로, 존재하는 모든 간선을 추가하는 것을 시도할 수 있습니다.) 추가할 수 있는 모든 간선에 대해, 그 간선을 추가하고 다른 간선 하나를 삭제하여 얻을 수 있는 최장경로를 생각할 수 있습니다.
• 새로 추가된 간선을 사용할 수 없는 경우만 걸러주면, 일반적으로는 기존 경로에 포함되어 있고 새로 추가된 간선의 경로가 사용하지 않는 간선을 하나만 자르면 새로운 최댓값을 얻을 수 있습니다.
• 예외 경우라 함은 새로 추가된 간선을 이쪽으로 사용하나 저쪽으로 사용하나 최단경로값이 같은 경우입니다.

SWERC 2021-2022 #B. Drone Photo

• $n\times n$의 배열에 서로 다른 $n^2$개의 수가 들어가 있습니다. 여기서 xy축에 평행한 직사각형의 네 꼭짓점을 이루는 네 명을 골랐을 때, 두 작은 값이 직사각형의 한 변을 이루고 있는 것의 수를 구하는 문제입니다.
• 어떤 직사각형이 이를 만족한다면, 네 꼭짓점에 해당하는 네 수 중 크기 순으로 두 번째, 세 번째의 수는 무조건 이웃한 두 수 중 하나보다 더 작고, 하나보다 더 큽니다.
• 그런 정점의 수를 세면 됩니다. 빈 배열에 가장 작은 수부터 하나씩 넣는다고 생각하고 계산하면 제곱에도 어렵지 않게 풀 수 있습니다.

제2회 피갤컵 #J. 피돌이 vs 피붕이

• DAG의 정점에 돌이 몇 개씩 있습니다. 2명이 이 위에서 돌을 움직이는 게임을 합니다. 매 턴에서, 한 정점의 돌을 DAG가 가리키고 있는 정점으로 1개 혹은 2개 움직일 수 있습니다. 움직일 수 있는 돌이 없으면 패배합니다. 누가 이기는지 찾으면 됩니다.
• 추가 조건으로, 각 정점의 outdegree는 2 이하입니다.
• DAG이므로 outdegree가 0인 정점이 존재할 겁니다. 그런 정점에는 돌이 몇 개 있는지 생각하지 않아도 됩니다.
  • 그런 정점에서는 돌을 움직일 수 없기 때문입니다.
  • 모든 정점에 $a$라는 값을 선언해서, outdegree가 0인 정점의 $a$를 0으로 둡시다.
• 게임 이론스러운 발상을 통해, $a[i]=0$인 정점으로 갈 수 없는 모든 정점의 $a$를 0으로 둡시다.
• 만약 갈 수 있다면, 그 정점에서 바로 이어져 있는 모든 정점 중 가장 큰 $a$값에 1을 더해서 그 정점의 $a$값으로 사용합시다.
  • 추가 조건에 의해, ‘그 정점에서 바로 이어져 있는 모든 정점’이라 해봤자 최대 두 개입니다. 만약 a값이 0이 아니라면, 그 두 개 중 하나는 0이어야 하므로 다른 하나의 값에 1을 더한 것이 a값이 됩니다.
• 이제 DAG에서 돌 하나를 a값이 0인 정점으로 옮기는 것은, 그 돌을 없애버리는 것과 마찬가지입니다.
• 따라서 게임의 규칙을 다음과 같이 쓸 수 있습니다:
  • 매 턴에서, a>0인 아무 정점의 돌을 하나 없애거나
  • 그 정점이 향하고 있는 a>0인 다른 정점 (무조건 1개 이하입니다!) 으로 돌을 1개 혹은 2개 옮길 수 있다.
• 그렇다면 모든 정점의 유효한 outdegree가 1 이하이므로, 주어진 DAG는 이제 포레스트입니다.
• 따라서, 포레스트를 이루는 모든 트리에서 그런디 수를 구해서 nim-add해주면 답을 얻을 수 있습니다.
• 트리에서 그런디 수를 구하는 방법은, 작은 트리에서 몇 번 계산해보면 구할 수 있습니다.
• 저도 증명해보지는 않았지만, 어쨌든 수는 다음과 같이 구할 수 있습니다:
  • 루트 노드에서부터 각 정점까지의 거리를 $l$이라 할 때,
  • 모든 정점에 있는 돌의 개수에 각각 $2^{l+1}$을 곱합니다.
  • 그 값을 모든 정점에 대해 다 더한 다음 3으로 나눕니다.
  • 그 값이 트리 하나에서의 그런디 수입니다.
• 그래서 그런디 수를 모두 구한 뒤 XOR하면 답을 구할 수 있습니다.

NWERC 2022 #F. Faster Than Lignt

• 좌표평면 위에 축에 평행한 직사각형 $n$개가 주어집니다. 이 직사각형들에 모두 접하거나 만나는 직선이 존재하는지 확인하고, 있으면 찾는 문제입니다.
• 직사각형의 대각선을 그어봅시다. 직선이 두 대각선 중 하나 이상과 만나는 것이 직선이 직사각형과 만나는 것과 동치입니다.
• 모든 직사각형에 대해 기울기가 양수인 대각선, 음수인 대각선이 있습니다. 이때 직선의 기울기가 양수라면 기울기가 음수인 대각선과는 무조건 만나야 합니다. 마찬가지로 직선의 기울기가 음수라면 양수 대각선과 만나야 합니다. 따라서, 모든 직사각형에 대해 기울기가 양수인 대각선 $n$개를 지나는 직선 혹은 음수인 대각선 $n$개를 지나는 직선이 존재하는지 찾으면 됩니다.
• 기울기가 양수인 대각선의 양 끝점만 모아 봅시다. 이들으로 그린 대각선을 정확히 통과하는 직선이 존재하는 것은, (대각선의 양 끝점 중 더 위에 있는 점들)으로 만든 볼록 껍질과 (아래에 있는 점들)으로 만든 볼록 껍질이 만나지 않는 것과 동치입니다.
• 따라서, 주어진 직사각형들에 대해 위쪽 점들만으로 컨벡스 헐을 두 개 만들고 아랫쪽 점들이 각 컨벡스 헐에 포함되어 있는지를 계산해보면 문제를 풀 수 있습니다.

IOI 2023 Day 1 #2. Longest Trip

• 어떤 그래프가 있습니다. 이 그래프는 특수한데, 아무 세 정점이나 잡아도 그 세 정점 사이에 간선이 1개 이상 있음이 보장됩니다. (3개 이상인 경우, 2개 이상인 경우가 각각 1번, 2번 서브태스크입니다.) 이때, 그래프 위의 최장경로를 구하면 됩니다.
• 그래프의 최장경로는 NP입니다. 그래프가 가지는 특수성을 이용해 최장경로를 구해야 할 것 같습니다.
• 1번 서브태스크: 모든 간선이 다 연결되어 있습니다. 그러므로 주어진 그래프는 완전 그래프이며, 아무 순서로 N개의 정점을 출력해주면 됩니다.
• 2번 서브태스크: 아무 세 점을 골라도, 그중 두 개의 간선이 존재합니다. 그래프를 대충 그려보다 보면 이때도 그래프가 충분히 dense함을 알 수 있기 때문에, hamiltonian path가 있을 것이라 추측할 수 있습니다.
  • 정점을 하나씩 추가하면서 어떤 간선이 추가되어야 하는지 확인하는 방법이 꽤 직관적이기 때문에, 수학적 귀납법으로 이를 construct할 수 있는지 확인하는 것이 자연스럽습니다.
  • 1번부터 K번까지 정점들이 순서대로 path를 이루고 있다고 가정합시다. 만약 K+1번 정점이 K번 정점과 연결될 수 있는 경우 둘을 연결하면 path를 만들 수 있습니다. 그렇지 않은 경우, K번 정점과 K+1번 정점을 포함하는 삼각형이 간선 두 개를 가져야 하기 때문에 1~K-1번 정점이 모두 K번 정점과 K+1번 정점에 연결되어 있습니다. 따라서, 1, 2, …, K-2, K+1, K-1, K 등의 방법으로 path를 연장할 수 있습니다.
• 60점: 아무 세 점을 골라도, 그중 한 개의 간선이 존재합니다. 연결 컴포넌트가 3개 있을 수 없습니다.
• 연결 컴포넌트가 2개인 경우를 생각합시다. 한 쪽에서 정점 하나, 다른 쪽에서 정점 둘을 잡으면 같은 쪽에 있는 두 정점 사이의 간선이 무조건 존재합니다. 따라서 연결 컴포넌트가 두 개라면 두 컴포넌트는 클리크를 이루며, 그중 더 큰 것에서 경로를 구성하면 됩니다.
• 연결 컴포넌트가 1개인 경우를 생각합시다. 당연히 모든 정점을 포함하는 경로가 있지 않을까 하는 생각을 하게 됩니다. 2번 섭테에서 했던 것처럼 수학적 귀납법으로 이를 construct할 수 있으면 좋겠습니다.
• 크기 K의 그래프가 완전그래프 2개이거나 해밀턴 경로를 가지는 상황에서, 정점을 하나 추가해 봅시다.
• 원래 그래프가 두 개의 완전그래프였던 경우, 새로운 정점과 두 컴포넌트의 정점을 하나씩 선택하면 하나의 간선이 추가되어야 합니다. 즉
  • 원래의 두 그래프가 사실 하나의 완전그래프였고 K+1번째 정점이 독립적으로 완전그래프를 이루거나,
  • K+1번째 정점이 두 왼전그래프 중 하나의 정점이 되어 더 큰 완전그래프를 이룹니다.
  • (간선이 하나보다 많아서 두 그래프가 하나로 합쳐지는 경우도 생각할 수 있으나, 수학적 귀납법을 쓸 수만 있으면 되므로 고려할 필요는 없습니다.)
• 원래 그래프가 path를 포함했다면, K+1번째 정점과 path 위의 연결되지 않은 아무 두 점을 선택합니다.
  • 만약 K+1번째 정점이 간선을 가지지 않는다면 기존 그래프 위에 간선이 하나 추가됩니다. 즉, K+1번째 정점이 기존 그래프와 간선을 하나도 가지지 않는다면 기존 그래프는 완전그래프입니다.
  • 그렇지 않다고 하고, K+1번째 정점이 path 위의 X번째 정점과 연결된다고 합시다.
    • X-1, X+1, K+1번 정점을 보면, K+1번째 정점이 path 위의 두 정점 중 하나에 연결되는 경우 path를 만들 수 있습니다. 그렇지 않다면 X-1번과 X+1번 정점이 연결되어 있습니다. 이때 X-1번이나 X+1번 정점이 기존 그래프에서 path의 끝점인 경우에도 path를 만들 수 있습니다.
    • 두 정점 모두 양 끝단이 아닌 경우, X-2, X+2, K+1번 정점을 봅니다. K+1번째 정점이 path 위의 두 정점 중 하나에 연결되는 경우, X-1번과 X+1번 사이의 간선 덕분에 path를 만들 수 있게 됩니다.
    • 그렇지 않은 경우, 또 X-2와 X+2 중 하나가 기존 그래프의 끝점인지 확인하고 X-3, X+3번 정점으로 넘어갑니다. 이를 계속 반복하다 보면 언젠가는 끝점에 도달하게 되므로, 항상 K+1번째 정점을 포함하는 새로운 path를 만들 수 있습니다.
• $q=32640=256C2$을 모두 사용하면 모든 간선 정보를 확인할 수 있으며, $O(VE)$가 넉넉히 돌아가는 시복입니다. 따라서 위의 작업을 그대로 구현해도 TLE를 받지 않을 수 있습니다. 따라서 여기까지 하면 60점을 받을 수 있습니다.
• 이제부터 쿼리를 줄여야 더 높은 점수를 받을 수 있습니다. 한 가지 아이디어로, K+1번 정점과 path 위에서 X번 정점 제외 최초로 인접하는 정점을 찾기 위해 이분 탐색을 사용할 수 있습니다. 그렇게 하면 각 정점을 $\log(N)$번에 추가할 수 있으므로, 아마 70점까지 올릴 수 있을 겁니다. 저는 1시간 30분 정도 고민해서 여기까지 왔습니다. 그러나 풀테를 맞기에는 충분하지 못합니다. 다른 방법을 찾아봅시다.
• 어차피 그래프가 완전그래프 2개이거나 hamiltonian path를 포함한다는 사실은 증명했습니다. 그러므로, 그래프를 구성하는 과정에서 굳이 완벽한 path를 관리하지 않아도 될 수도 있습니다. 두 path가 사실 하나일 수도 있고, 각각 완전그래프를 이룰 수도 있다는 사실을 감안하면서 path 두 개를 관리해 봅시다.
• 새로운 정점이 들어올 때, 두 path의 양끝점과 새로운 정점 3개 점을 선택합니다. 그중 하나의 간선이 존재하므로, 이를 이어주면 두 개의 path가 유지됩니다. 따라서 2N번 이하의 간선으로 두 개의 path를 만들 수 있습니다.
• 마지막에 두 path를 합쳐주어야 합니다. 일단 합칠 수 있는지 확인해 줍시다. 합칠 수 없다면 더 긴 path를 그대로 출력하기만 해도 답입니다.
• 합칠 수 있다면, 그 다음으로는 양 끝단의 두 점씩 사이에 간선이 있는지 확인해 줍시다. 만약 있다면, 세 번의 추가 연산으로 path를 완성할 수 있습니다.
• 만약 없다면, 두 path는 사실 cycle입니다. 그러므로 두 cycle 사이에 간선이 딱 하나만 있으면 됩니다. 두 cycle에서 각각 이분 탐색하면 그러한 간선을 찾을 수 있으며, $2\log(N/2)$번의 연산을 사용합니다.
• 이렇게까지 하면 $2N+2\log(N)$번 정도의 연산으로 답을 찾을 수 있으며, 85점을 획득할 수 있습니다.
• 만점을 위해서는 상수를 조금 더 잘라줘야 합니다. 그레이더가 비적응적이므로, 두 path를 관리하는 부분에서 정점 추가 당 연산 횟수를 최악 2회에서 평균 1.5회로 줄여서 랜덤으로 뚫어줄 수 있습니다.