NSP 5호

2024/06/04 ~ 2024/10/01

너무 많이 문제가 밀려서, 따라잡기 위해 상당수의 문제를 버렸습니다. 마음이 아픕니다.

SUAPC 2021 Winter #F - 성싶당

• 길이 $N$의 이진수는 $2^N$개가 존재합니다. 이들을 적절히 배열해, 인접한 두 수를 and한 값의 총합이 최소가 되도록 수를 배열하는 방법을 구하는 문제입니다.
• 길이 $N$에서 작동하는 임의의 배열을 구성적으로 찾으면 됩니다.
• 길이 $N$의 이진수의 배열 ${A_x}$을 찾았다고 할 때, 길이 $N+1$의 이진수의 배열을 만드려면,
• ${A_x}$에 $A_{2^N}+2^N$, $A_{2^N-1}+2^N$, $\cdots$, $A_1+2^N$을 순서대로 추가하면 됩니다.

JOIGSC 21/22 Day1 #2 - JOIG Tour

• 수직선의 $(0,10^6)$ 범위에 $J$, $O$, $I$, $G$가 각각 몇 개씩 있습니다. ‘초기 위치’에서 $J, O, I, G$를 순서대로 하나씩 지나서 ‘최종 위치’로 가는 최소 길이 경로를 구하면 됩니다.
• 어떤 위치에서 다음 알파벳으로 이동할 때, 그 위치에서 왼쪽 혹은 오른쪽으로 가장 가까운 곳으로 가도 됩니다.
  • 라는 발상은 어렵지 않았던 것 같습니다. 직관적으로는 어렵지 않게 증명할 수 있습니다.
• 알파벳 4개밖에 없으므로 16가지 경우만 체크하면 됩니다.
• 전처리로 모든 알파벳에 대해 그 다음으로 이동할 수 있는 알파벳의 두 경우를 구해놓으면 됩니다.

JOIGSC 21/22 Day2 #2 - Airport

• 공항에 비행기가 내리고 뜨는 데 걸리는 시간과 착륙 스케줄이 각각 주어질 때, 제한된 활주로에서 띄울 수 있는 비행기의 개수를 최대화하는 문제입니다.
• 시간 간격을 일고 있으면 그 사이에 넣을 수 있는 이륙의 개수는 고정입니다.
• 활주로를 사용할 수 있는 시간을 멀티셋으로 관리(단, 나중에 추가될 조건을 pq로 관리)하면 회의실 배정과 비슷하게 그리디하게 풀 수 있습니다.

USACO January 2023 Gold #3 - Moo Route

• Dyck path에서 직선 $y=x-a$ 직선과 딕 경로의 교점이 $a$값에 따라 배열으로 주어집니다. 이때 방향을 최소로 바꾸는 경로의 개수를 구하면 됩니다.
• $A_i < A_{i+1}$이라면 $i \rightarrow i+1$로 올라오는 모든 경로가 $i+1 \rightarrow i+2$로 올라가고, 반대도 그렇습니다. $A_i > A_{i+1}$라면, $i+1 \rightarrow i+2$의 모든 경로가 그 직전의 $i \rightarrow i+1$에서 이어집니다.
• 즉, 모든 $i<n$에 대해 $A_i<A_{i-1}$이면 답에 $(^{A_{i-1}}{A{i}})$을 곱해주면 되고, $A_i>A_{i-1}$이면 중복조합 $A_{i-1} H (A_i-A_{i-1})$을 곱해주면 됩니다.

Baltic OI 2009 #5 - Triangulation

• 볼록다각형을 삼각분할하여 몇 개의 색으로 칠했을 때, 다각형을 양쪽에 한 가지 색이 모두 들어가는 일이 없도록 자르는 방법의 개수를 구하는 문제입니다.
• 이때 삼각분할에서 각 삼각형은 색상을 가지는 정점으로, 변은 간선으험 고2 - 순서 섞기
• 어떤 deque가 있어서, 앞이나 뒤에서 원소를 하나씩 빼서 뺸 순서대로 deque를 다시 만들 수 있습니다. 이때 deque를 정렬하기 위한 연산 수를 묻는 문제입니다.
• 수가 증가하고 감소하는 것만 보면 됩니다. 정확히는, 연산을 통해서 증가하거나 감소하는 부분을 inverse해줄 수 있고, 그러면 연산을 할 때마다 증가-감소의 inverse가 하나씩 없어집니다.
• 따라서 그 개수만큼 연산을 하면 지워집니다. 그걸 출력하면 됩니다.

ICPC Tsukuba Regional 2015 #I - Routing a Marathon Race

• 대충 정점이 40개짜리인 그래프에서 최단경로를 구하는데, 그 비용이 최단경로 위에 있는 정점으로부터 거리가 1 이하인 모든 정점의 가중치 합과 같습니다.
• 40이 너무 크기 때문에 일단 나이브가 돌지 않는 것은 확실합니다. 여기서 한 가지 가지치기 전략을 생각해볼 수 있습니다:
• (DFS를 돌면서,) 모든 정점에 대해, 지금까지 달려온 정점 중에서 인접해 있는 정점의 수를 구합니다. 이것이 2 이상이면 그 정점은 탐색하지 않아도 됩니다.
• 이걸 하면 정말 개쩔게도 시복이 $O(3^{N/3})$임이 보장되어서 문제가 풀립니다.
• 저는 jhnah님 블로그를 보고 증명을 이해했습니다. 궁금하시면 가서 읽어보시면 나름 신기할 겁니다…

ICPC Croatian Programming Contest 2019 #G - # Golema Gozba

• 길이 $2N$의 사이클이 한 색당 두 정점씩 $N$개의 색으로 칠해져 있습니다. 이 정점을 두 집합으로 나눠야 하는데,
  • 같은 색으로 칠해진 정점은 다른 집합에 속해야 하고,
  • 연속한 3개의 정점이 같은 집합에 속할 수는 없습니다.
• 그런 해를 하나 구성하면 됩니다.
• 같은 색으로 칠해진 정점들 사이를 빨간색 간선으로 잇고, (1,2), (3,4), …의 정점들 사이를 파란색 간선으로 잇습니다.
• 그러면 모든 정점이 빨간색 간선 하나, 파란색 간선 하나와 연결됩니다. 따라서 이 $2N$개 정점으로 이루어진 그래프는 이분그래프입니다(반드시 연결되어 있진 않을 수도 있습니다).
• 문제가 풀립니다.

제4회 kriiicon #12 - 트리

• 순서가 있는 정점 $N$개짜리 트리 중, 몇 개의 간선이 주어지면 그 간선을 모두 포함하는 트리의 수를 계산하는 문제입니다.
• Prüfer sequence라는 게 있습니다. 모든 Labeled tree는 이 수열 하나로 대응할 수 있습니다.
• 이때, ‘수열에 어떤 정점에 나타나는 횟수’는 그 정점의 차수에서 1을 뺀 것과 같습니다.
• 간선이 주어지면, 그 간선들로 연결된 모든 정점을 축약해 얻을 수 있는 트리를 생각할 수 있습니다.
• 그러한 트리의 수를 구하고, 각 축약에 대해 연결되는 다른 간선들이 각각 어떤 정점에 연결되는지 그 정점의 차수에 따라 구할 수 있습니다. (여기서 Prüfer sequence를 쓰면 됩니다.)
• 식을 정리해서 계산하기 쉬운 형태로 바꾸면 됩니다.

Romanian IOI 2017 Selection Day1 #1 - Rooms

• 유파를 구할 수 있는 격자 하나가 주어집니다. 쿼리로 그 격자의 부분 사각형이 주어지면, 사각형에 조금이라도 속한 분리집합의 수를 구하면 됩니다.
• $O(Q(N+M))$이 넉넉히 돌기 때문에, 쿼리가 주어질 때마다 가장자리의 모든 격자칸을 볼 시간이 있습니다.
• 모든 유니온에 대해 아무 칸이나 하나 잡아서 X표를 해두고, 쿼리별로 주어진 사각형 내부에 있는 X표만 세 봅시다. 그럼 쿼리에 완전히 포함된 유니온의 수는 무조건 셀 수 있습니다.
• 까먹고 안 세는 쿼리가 있다면, 모두 가장자리에 걸쳐있는 유니온입니다. 가장자리의 모든 격자칸에 대해, 그 유니온의 X표가 사각형 밖에 있다면 하나씩 더해줍니다.
• 그러면 쿼리에 완전히 포함된 유니온과 조금만 포함된 유니온의 X표를 모두 세었으므로, 각 쿼리의 답을 구했습니다.

IOI 2024 #5 - Mosaic

• 문제는 백준을 참고하시기 바랍니다.
• 나이브만 짜도 12점은 받을 수 있습니다.
• $x<3\,\text{or}\,y<3$인 곳들을 모두 채웠다고 가정합시다. 나머지 칸들은 $a[i][j]=a[i-1][j-1]$임을 관찰할 수 있습니다.
• 그렇다면, 각 질의에서 어떤 범위는 그 범위를 왼쪽 위 방향으로 대각선으로 올릴 때의 $a[0][j]\,or\,a[i][0]$으로 만들 수 있습니다.
• 누적합을 잘 짜주면 됩니다. 이때 연속한 부분배열에서 각 원소를 쓰는 횟수는 1씩 늘어나거나 줄어다는 감소수열이므로, 두가지 누적누적합을 모두 구해 두어야 합니다.

KAIST 12th ICPC Mock #G - Permutation Arrangement

• 길이 20만의 순열이 주어지는데, 일부만 차 있고 나머지 칸은 비워져 있습니다.
• 인접한 두 원소의 차이가 1인 경우가 없도록 모든 칸을 잘 채우면 됩니다.
• 만약 연속하지 않도록 8칸이 비워져 있다면, 남은 수가 무엇이던간에 홀의 결혼 정리에 의해 채울 수 있는 방법이 무조건 존재합니다.
• 따라서, 빈칸이 15개 이상 있다면 무조건 채울 수 있습니다: 빈칸이 15개 남을 때까지 아무렇게나 채우고 나머지는 비트필드 DP 돌리면 됩니다.
• 그렇지 않은 경우에는 전부 다 비트DP 돌리면 되므로, 문제를 항상 풀 수 있습니다.