Notable Solved Problems 1호

너무 CP쪽만 블로그를 올리는 것 같아서, PS한 내용도 올려보려고 합니다. 주기가 어느 정도가 될 지는 모르겠습니다. 1호니까 정해진 범위가 없죠? 대충 여름방학 전후를 시작점으로 해서 기억나는 것들을 다 적어보도록 하겠습니다.

JOI 2023 #2. Adertisement 2 (BOJ 27537)

• 수직선 위에 사람들이 있는데, 각 사람은 영향권의 범위를 가집니다. 한 사람이 책을 사게 되면 영향권 내에 있는 사람들이 모두 책을 사게 됩니다. (이 동작은 연쇄적으로 일어날 수 있습니다.) 이때 최초에 책을 받을 최소의 인원수를 구하는 문제입니다.
• 각 인물이 영향을 끼칠 수 있는 범위가 결정됩니다. 각 범위는 곧 구간입니다, 즉 시작점을 기준으로 정렬하고 스택을 만들어 스위핑하면 됩니다.
• 스위핑을 통해 영향권의 범위 사이 관계를 알 수 있으므로 풀이가 자명해집니다.
• JOI답게 문제 퀄이 좋은 것 같습니다.

JOI 2021 #1. Growing Vegetables is Fun 4 (BOJ 20984)

• 1번부터 n번까지의 칸에 식물을 기르고 있습니다. 각 식물에 물을 주면 키가 1씩 큽니다. 한 번 물을 줄 때는 연속한 몇 개의 칸에 대해 한 번에 물을 줄 수 있습니다. 식물 키가 단조증가 후 단조감소하도록 하게 하려면 물을 몇 번 주어야 하는지 구하는 것이 문제입니다.
• 코이스터디에서 누가 숏코딩을 한다고 해서 참전한 문제입니다. 현재 제 백준 내 순위는 2등입니다.\
• 두 연속한 칸의 크기 관계를 반전시키려면 물을 한 번 줘야 합니다. 키가 최대가 되는 칸에 대해 그 앞, 뒤쪽으로 물을 주어야 하는 칸의 수를 각각 앞에서 뒤로, 뒤에서 앞으로 스위핑하면서 DP로 구해주면 됩니다.

SUAPC 2023 #I. 폭탄 피하기 (BOJ 29157)

• SUAPC 오픈을 치기는 했는데, 이 문제 말고는 다 실버였어서 쓸 게 없습니다.
• 격자상에서 길찾기를 하는데 정점 20개 이하에 폭탄이 있습니다. 폭탄을 피해가는 경로의 수를 구하는 문제였습니다.
• 우선, 폭탄을 무시할 때 임의의 두 폭탄 사이 및 출발점, 도착점과 폭탄 사이를 오갈 수 있는 경우의 수를 전처리합니다. 22C2이므로 구하는 데 아무 시간 소요가 없습니다.
• 다음, 폭탄 20개 중 몇 개를 골랐을 때 이들을 모두 지나는 경로의 수를 구합니다. $2^{20}$개에 대해 전처리 덕분에 $O(1)$에 구할 수 있으므로 시간 안에 들어옵니다.
• 그리고 폭탄의 위치 관계에 따라 포배합니다.
• 조합론적으로 어느 정도 배경지식이 있다면 어렵지 않은 문제였다고 생각합니다.

SCUPC 2022 #F. 간단한 수학 문제 (BOJ 26269)

• 1부터 N까지로 이루어진(모두 한 번씩 등장해야 합니다) 길이 K 배열 중, 모든 i : 1…N에 대해 i 앞과 뒤에 등장하는 i-1의 수가 같은 배열을 생각합니다.
• 이중 사전순으로 X째인 것을 찾는 문제입니다.
• 몇 가지 관찰을 통해,
  • 배열의 길이가 짝수라면 단조증가함수가 대칭된 팰린드롬이 되고
  • 홀수라면 중간에 있는 수가 N이며 이를 빼면 길이가 짝수인 배열과 같아진다
• 는 것을 알 수 있습니다.
• 따라서 K/2의 배열에 모든 수가 나오면서 단조증가하도록 하는 배열을 사전순으로 나타내는 문제로 reduction할 수 있습니다.
• 수학에서 Factoradic 문제들을 풀듯이 풀면 됩니다. 중복조합을 잘 사용해야 합니다.

USACO 2020 Open Plat. #1. # Sprinklers 2: Return of the Alfalfa (BOJ 18871)

• 문제 설명은 생략하겠습니다.
• 한 꼭짓점에서 반대 꼭지점까지 가는 경로를 만들 때, 경로에 생기는 모든 코너에 대해 그 코너 안쪽으로 스프링클러를 설치하면 됩니다.
• 즉, 코너의 인코스 쪽으로 양이 없도록 하는 경로의 개수를 구하면 됩니다.
• 해당 코너에서 오른쪽으로 가느냐, 아래로 가느냐 둘을 나눠 DP를 짭니다. 그렇게 하면 임의의 점이 코너일 때와 그렇지 않을 때를 구분하여 DP할 수 있습니다.
• 그렇게 해서 잘 풀면 됩니다.

JOISC 2020/2021 #4-1. Event Hopping 2 (BOJ 21793)

• 역시 문제는 생략합니다.
• 아이디어만 간략하게 설명하자면, 구간 집합에서 임의의 구간으로부터 그 구간과 겹치지 않는 오른쪽의 구간 중 가장 왼쪽에 있는 것을 유향으로 잇는다고 합시다. 그렇게 하면 구간 집합이 루트 노드를 향하는 트리 혹은 포레스트가 됩니다.
• 이 포레스트 내에서 가장 긴 line graph를 잡으면 이 그래프상의 정점의 집합은 가장 큰 독립집합입니다.
• 이걸 스파스 테이블로 만듭니다. 그러면 다음이 가능합니다:
  • 임의의 범위에 대해, 그 범위 내에 있는 구간 중 종점이 가장 이른 것을 하나 잡을 수 있습니다.
  • 그 정점에서부터 스파스를 타고 루트 쪽으로 올라갑니다. 범위 내에 있는 것중 가장 루트에 가까이 있는 것을 찾는 데에 로그 시간이 걸립니다.
  • 따라서 로그 시간이면 범위 내에서 최대 독립집합을 찾을 수 있습니다.
• 이걸 잘 써서 푸는 문제입니다. 아이디어가 정말 좋은 것 같습니다.

HPEC 2023 Intermediate #H - 발전 장치 (BOJ 29815)

• 파스칼의 삼각형 모양의 피라미드 위를 태양이 비추고 있습니다. 태양이 비추는 칸은 전력을 발전하며, 그렇지 않은 칸은 그 위로 인접한 칸들의 전력 생산의 합만큼 전력을 생산합니다. 이때, 발전하는 칸은 전력을 높이에 따라 다르게 생산합니다. 높이에 따른 발전량은 높이가 높을수록 생산량이 많은 등차수열로 주어집니다. 이때 임의의 칸의 발전량을 구하시오.
• 대충 맨 위칸의 발전량을 a, 등차수열의 공차를 b라고 합시다. 임의 칸의 발전량을 ax-by 꼴로 나타낼 수 있다는 사실을 어렵지 않게 찾을 수 있습니다.
• x의 값은 파스칼의 삼각형 모양을 띕니다. 따라서 nCr 계산 1회로 구할 수 있습니다.
• y는 좀 다른데, 칸이 낮아질수록 사이드 칸의 값이 늘어나기 때문입니다. 잘 생각해보면, 이때의 ‘새로운 파스칼의 삼각형’은 파스칼의 삼각형 여러 개의 합의 모양을 띕니다.
• 이것을 정리해보면 하키스틱을 사용할 수 있는 형태입니다. 따라서, nCr 계산 2회로 구할 수 있습니다.
• 팩토리얼과 그 modular inverse를 전처리하면 각각 O(1)에 구할 수 있습니다. 전처리에 O(nlogn)이 걸립니다.

NCPC 2016 #H - 최고의 대장장이 토르비욘 (BOJ 13361)

• 직사각형 몇 개가 있습니다. 이들을 붙여서 가장 긴 검을 만들 것입니다. 유일한 조건으로, 갈수록 그 너비가 줄어들어야 한다는 것이 있습니다.
• 만약 모든 길이가 서로 달랐다면, 그냥 붙이면 되는 실버 문제입니다. 문제가 같은 길이이므로, 이를 생각합시다.
• ‘너비’에 해당하는 것이 서로 다른 값으로 총 n개 필요합니다. 이들을 최소가 되게 잡으면 됩니다.
• 따라서 다음을 할 수 있습니다:
  • 모든 가로세로 길이 합을 계산합니다.
  • 같은 길이가 있는지를 조건으로 union-find합니다.
  • 각 union에서 서로 다른 가장 작은 길이를 뽑습니다.
  • 그 합을 가로세로 전체합에서 뺍니다.
  • 그러면 답이 됩니다.
• 문제 낸 사람이 천재인 것 같습니다. 이런 생각을 도대체 어떻게 하는 건지 잘 모르겠습니다.