Notable Solved Problems 2호

2023/10/20 ~ 2023/11/13

JOISC 2008/2009 #2-1. Abduction

• (1,1)에서 (n,m)까지 격자를 따라 움직이면, 방향을 틀 때 왼쪽이나 오른쪽으로 돌 수 있습니다. 이것의 배열이 주어질 때 가능한 경로의 수를 구하는 문제입니다.
• 배열을 기반으로 출발의 방향과 도착의 방향을 알 수 있습니다. 따라서 모든 회전 전후의 이동 방향을 알 수 있게 됩니다.
• 가로/세로의 이동은 각각 독립적입니다. 따라서 가로 이동으로 가능한 경우의 수를 DP로 구하고 세로로 같은 방법으로 구해 곱하면 됩니다.

IOI 2022 Practice #1. Magic Cards

• N개의 수 중 K개를 임의로 고르면, 한쪽에서는 K개 중 하나를 빼고 다른 쪽에서는 그 하나를 맞추는 투 스텝 문제입니다.
• K개의 선택은 조합이고 투스텝의 전달은 순열이므로 경우의 수를 잘 맞출 수 있습니다. 입력 제한 조건을 보면 무조건 정보 전달이 가능함을 보일 수 있습니다.
• Subtask 1과 2는 노가다를 통해 정보 전달을 위한 일대일함수를 구할 수 있습니다.
• Subtask 3은 K-1개의 수열이 120개이므로 이것만 있어도 정보 전달이 충분히 가능합니다.
• Subtask 4의 경우 이것이 불가능합니다. K-1개의 수열은 5040개, N은 10000입니다.
• 비둘기집의 원리에 따라 K개 중 mod K-1으로 같은 두 수를 찾을 수 있습니다. 둘의 차이가 5000 아래면 그 중 작은 것을, 아니면 더 큰 것을 남기고 나머지를 뺍니다. 그러면 N을 반으로 줄인 셈이 되므로 구할 수 있습니다.
• 정말 마음에 들었습니다. 한 5시간쯤 들여 푼 것 같습니다.

USACO 2018 December Platinum #1. Balance Beam

• 길이 N의 수열에서, 각 칸에서 멈추거나 50%의 확률으로 왼쪽/오른쪽으로 이동하기 중 하나를 고를 수 있을 때, 가장 큰 수로 떨어지고자 하면 그 기댓값을 구하는 문제입니다.
• 현재 칸이 그 사이에 있도록 두 칸을 고르면, 그 두 칸 중 하나에 도달할 때까지 계속 이동하는 전략을 취할 수 있습니다. 이때 기댓값은 ‘두 칸의 내분점’에 해당합니다.
• 최대한 기댓값이 높은 두 개를 잡아서 거기까지 이동하는 전략을 취하면 됩니다. 그럼 직관적으로 컨벡스 헐이 나옵니다.
  • 컨헐임을 관찰하면 최적성에 대한 증명도 매우 간단해짐을 확인할 수 있습니다.
• 이것도 아이디어가 정말 좋은 것 같습니다. 조합론에 기하가 붙을 줄 누가 알았겠습니까?
• 근데 실수오차가 좃입니다.

POI 1996/1997 Stage 3 #4. Monochromatic Triangles

• (8907. 네온 사인 및 17275. 부족 전쟁과 같은 문제입니다. 79brue님이 추천해 주셨습니다.)
• 간선을 2개 색으로 칠한 그래프에서 monochromatic한 삼각형의 개수를 구하는 문제입니다.
• 임의의 점을 고르면 그로부터 빨간 간선과 파란 간선이 나갑니다. 둘의 수를 곱하면 non-monochromatic의 개수가 나옵니다.
• 이러한 방식으로 모든 점에서 계산하면 non-mono가 각각 정확히 두 번씩 세집니다. 따라서 non-mono의 수를 구할 수 있습니다.
• 완전 그래프이므로, 이를 통해 mono의 개수를 구할 수 있습니다.
• 이상의 발상과 구현을 7분만에 해서 기분이 좋았습니다.

KUPC 2023 Open #M. 우정은 BFS처럼, 사랑은 DFS처럼

• (아레나로 열린 대회였는데 10등대를 해서 ss+이 나와 기분이 좋았습니다.)
• BFS ordering과 DFS ordering의 차의 합이 최대가 되는 그래프를 출력하는 구성적이었습니다.
• 상당히 직관적으로 이러한 그래프를 찾을 수 있었습니다: 1과 2를 연결하고, 절반은 1에 잇고 절반은 2에 잇습니다. 그렇게 하면 $(n-1)(n-2)/2$개를 구할 수 있으며 이가 최대입니다.
• 플5를 줬는데 플3까지 올라갔습니다.

SASA PC 2023 #M. 하이퍼 삼각형 자르기

• (퍼솔했습니다!!!!!!!!! 너무 기분이 좋았습니다!!!!!!!!!! GM분들 루비분들 마스터분들 선배분들보다 먼저 풀었습니다!!!!!!!!)
• m차원의 정(m+1)포체를 각 차원으로 n등분한 것에서 정(m+1)포체의 개수를 구하는 문제입니다.
• 우선, 임의의 차원에서 역방향 삼각형이 있음을 증명해야 합니다. 이는 입력 3 4를 그리는 것을 시도하면 알 수 있습니다.
• 정방향 하이퍼삼각형을 세어 봅시다.
  • 평면에서, $1+2+3+…+i={(i+1)}C2$를 $1 \leq i \leq n$의 모든 i에 대해 더하면 됩니다. 즉 ${n+2}C3$입니다. (i는 삼각형의 크기가 됩니다.)
  • 3차원에서는 이 식(${i+2}C3$)을 $1 \leq i \leq n$에 대해 모두 더하면 됩니다. 즉 ${n+3}C4$입니다. (역시나 i는 크기입니다.)
• 일반화하면, 정방향 하이퍼삼각형은 ${n+m}C{n+1}$개 있습니다.
• 역방향 하이퍼삼각형을 세어 봅시다.
  • 예제 입력 1에서 크기 1의 역하이퍼삼각형은 세 줄 총 6개 있습니다. 그렇다면 만약 정방향이었다면 총 개수는 6+3+1=10개 있어야 하지만, 실제로는 크기 2의 역삼각형이 1개밖에 없어 6+1=7개 있습니다.
  • 확장해 볼까요? 입력 2 6에 대해, 정방향 삼각형은 $8C3=56$개 있습니다. 역방향 삼각형은, 크기 1이 $6C2=21$개, 크기 2가 $4C2=6$개, 크기 3이 $2C2=1$개로 총 28개입니다.
  • 2차원 한정으로 일반화하면, 역방향 삼각형은 $nC2+{n-2}C2+{n-4}C2+…$개 있습니다.
  • 3차원에서 생각해봅시다. 입력 3 3에 대해, 역방향 하이퍼삼각형은 1개 있습니다. 다음 그림에서, 빨간색 삼각형(정방향 하이퍼삼각형 중 2층의 밑면 3개 사이에 있는 면)을 밑면으로 하는 역방향 하이퍼삼각형이 존재합니다.
  • (그림)
  • 그렇다면, 크기 2의 역방향 하이퍼삼각형은 언제 출현할까요?
  • 자명하게도, 위 입력을 두 배로 키워 3 6으로 만들면 됩니다! 그렇게 하면 위 그림을 등분한 형태가 되니까, 중간에 크기 2의 역방향 하이퍼삼각형이 1개 나올 것이고 그것이 최소입니다.
  • 따라서, 삼차원에서($m=3$에서) 역방향 하이퍼삼각형은 $nC3+{n-3}C3+{n-6}C3+…$개 있습니다.
• 일반화하면, 입력 m n에 대한 역방향 하이퍼삼각형은 $nCm+{n-m}Cm+{n-2m}Cm+…$개 있습니다.
• 즉, 입력 m n에 대한 답은 ${n+m}C{n+1}+nCm+{n-m}Cm+{n-2m}Cm+…$입니다.
• 다음과 같이 증명할 수 있습니다. 충분히 엄밀한 증명은 아닌 것 같습니다.
  • 정방향 하이퍼삼각형은 직관적이므로 쉽게 증명할 수 있습니다.
  • 역방향 하이퍼삼각형을 세기 위해, 하이퍼삼각형을 기울여서 하이퍼삼각형이 하이퍼직각이등변삼각형이 되도록 합시다. 더 엄밀히 하여, 입력 m n에 대해 $(0, 0, …, 0), (n, 0, …, 0), (0, n, …, 0), (0, 0, …, n)$을 꼭짓점으로 가지는 하이퍼삼각형을 생각합시다.
  • 최초의 역하이퍼삼각형은, 위 하이퍼삼각형에 완전히 포함되는 차원 $m$의 하이퍼큐브로 만든 코너-하이퍼직각이등변삼각형입니다.
  • 이러한 하이퍼큐브는 하이퍼공간대각선의 길이가 $\sqrt{m}$입니다. 한 변의 길이가 $n$인 $m$차원 하이퍼삼각형의 대각선 길이가 $\sqrt{n}$이므로, $m=n$일 때 크기 1의 역하이퍼삼각형이 최초로 정확히 1개 나옴을 알 수 있습니다.
  • 따라서, 크기 $k$의 역하이퍼삼각형이 최초로 나오는 시점은 $n=km$이며 이때 이러한 역하이퍼삼각형은 단 하나 존재합니다.
  • 각 크기의 삼각형의 개수는 정방향 하이퍼삼각형을 세는 것과 같은 방법으로 셀 수 있습니다. 크기 $k$의 역하이퍼삼각형은 각 축에서 $n-km$만큼 움직일 수 있고 차원이 $m$개이므로, 그 개수는 ${n-km}Cm$입니다. 이를 모든 $k$에 대해 계산하면 됩니다.
• Proof by AC 했습니다. 아무튼 퍼솔입니다.