PS 일지 (2021.11.18)

23570. Grid Triangle

Platinum 3

문제 분석

ICPC Regional Seoul 2021 E번이었다.. 대회 중에 못 푼게 너무 한이 돼서 진짜 열심히 업솔빙한 문제였다.

우선 문제 조건부터 정리를 해보자. 문제에서는 Grid Triangle을 다음과 같이 정의한다.

There exist three different positive integers $X$, $Y$, $Z$ such that for every pair of the three points of the triangle, you can rotate and translate the cuboid of size $X × Y × Z$ in parallel with the grid system so that the pair are diagonally opposite (and so the farthest way) vertices of the cuboid.

번역을 해보자면 다음과 같다.

삼각형의 세 점의 각 쌍에 대해서 세 개의 다른 $X$, $Y$, $Z$ 가 존재해서 그 변을 적절히 돌리거나 이동시켰을 때 격자에서 $X × Y × Z$ 직육면체의 대각선에 평행하게 만들 수 있어야 한다.

여기서 직육면체의 대각선은 어떤 면의 대각선이 아닌 직육면체에서 가장 먼 두 점을 잇는 대각선을 의미한다.

문제는 $\{(x, y, z)| -A ≤ x ≤ A, -B ≤ y ≤ B, -C ≤ z ≤ C\}$를 만족하는 점으로 이루어진 Grid Triangle의 개수를 찾는 문제였다.

풀이

일단 세 점 중 하나는 무조건 원점이므로 다른 두 점이 갖춰야 할 기본적인 조건에 대해서 생각해보자.

만약 한 점이 $(x, y, z)$라고 할 때, 다른 한 점은 $(\pm y, \pm z, \pm x)$ 뭐 대충 이런 식으로 될 것이라고 기대할 수 있다. 같은 축에 같은 숫자가 오면 안되기 때문이다. 그러면 여기에서 우리는 $x<y<z$일 때, $x+y$가 $z$라고 예상할 수 있다.

이제 문제는 다음과 같이 바뀐다.
$\{(x,y,z)∣−A≤x≤A,−B≤y≤B,−C≤z≤C\}$ 에서 $x+y=z$인 순서쌍의 개수를 찾으면 된다.

여기부터가 중요한데, 케이스가 꽤 많이 나뉜다.. 문제를 풀기 위해 해결해야할 가장 중요한 세 가지 경우만 나열하고 글을 마무리 하려 한다.

풀이를 직접 알려줘버리면 너무 쉽게 끝나기 때문이다..

1. 입력
   3 6 6
   출력
   80
2. 입력
   3 9 9
   출력
   80
3. 입력
   3 4 4
   출력
   64

내가 이 세 개를 체크를 안해서.. 8번이나 (대회 포함 13번..) 절었기 때문에.. 앞으로 푸실 분들은 이 케이스들을 꼭 체크해보면 좋을 것 같다...

고찰

icpc 본선 후기를 따로 쓸 게 없다.. 내가 맡은 문제가 이거 하나였고.. 이거 하나를 못풀었었다.. 굉장히 아쉽고.. 또 아쉬운 대회였다..