ABC347 F - Non-overlapping Squares

Competitive Programming C++ AtCoder Algorithms

2024-03-31

공식 에디토리얼

문제 링크
https://atcoder.jp/contests/abc347/tasks/abc347_f

원문 링크
https://atcoder.jp/contests/abc347/editorial/9674

다음의 사실이 성립합니다.

평면 \(\mathbb{R}^2\) 위의 변과 축에 평행하고 서로 겹치는 점을 가지지 않는 (경계를 포함헤서) 정사각형이 \(3\)개 있을 때, 어떤 축에 평행한 직선 \(l\)이 다음의 조건을 만족한다.

• \(l\)은 어떤 정사각형과도 겹치는 점이 없다.
• \(l\)에 의해 나뉘어진 \(2\)개의 영역 모두 \(1\)개 이상의 정사각형을 포함한다.

증명
한 쪽 축을 골라, \(3\)개의 정사각형을 그 축 위의 열린 공간에 각각 사영합니다. (축 위의 어느 점이 구간에 포함된다 \(\Longleftrightarrow\) 그 점을 지나면서 축과 수직인 직선이 정사각형에 포함된다)
구간을 정점으로 하고, 구간이 겹치는 부분을 가질 때 두 구간 사이에 간선이 있는 그래프로 생각할 수 있습니다.
이 그래프가 비연결 그래프일 때, 고른 축에 수직인 조건을 만족하는 어떤 직선이 존재합니다. (구체적으로는, 연결성분들을 합쳐 \(1\)개의 열린 구간으로 만들고, 오른쪽 끝이 최소가 되도록 하는 것으로 얻어집니다.)
이 그래프가 연결 그래프라면, 연결성에 의해 간선의 수는 \(2\)개 이상이 되므로, 비둘기집 원리에 의해 차수가 \(2\)인 정점이 존재합니다. 이 정점에 대응하는 정사각형은 보고 있는 춗 방향에 남은 \(2\)개의 정사각형과의 겹치는 부분을 가지게 되므로, 다른 한 쪽의 축 방향으로는 어느 정사각형도 겹치는 부분을 가지지 않습니다. 따라서, 이 정사각형의 위쪽 또는 아래쪽과 일치하는 직선 중 적어도 하나는 조건을 만족합니다.

따라서, 고른 \(3\)개의 \(M \times M\)의 칸에 대해서도 다음 중 어느 하나가 성립합니다.

• 어떤 \(k\ (M \leq k \leq N - M)\)가 \((i, j)\ (i \leq k)\)의 부분과 \((i, j)\ (k < i)\)의 부분 양 쪽에 \(1\)개 이상의 정사각형을 포함하고, 경계에 걸치는 정사각형이 없는 것을 만족한다.
• 어떤 \(k\ (M \leq k \leq N - M)\)가 \((i, j)\ (j \leq k)\)의 부분과 \((i, j)\ (k < j)\)의 부분 양 쪽에 \(1\)개 이상의 정사각형을 포함하고, 경계에 걸치는 정사각형이 없는 것을 만족한다.

또한, \(2\)개의 정사각형이 포함되는 부분에 대해서도 마찬가지로 생각해보면, 최적해는 \(M \times M\)칸을, \(N \times N\)의 격자판을 \(3\)개로 나눈 다음의 방법들 중 하나의 경우에서, 각각의 영역에 정사각형이 \(1\)개씩 포함되도록 하는 것입니다. (그림에서의 길이의 비는 임의로 조정할 수 있습니다. 여기서 나누는 방법은 어느 한 쪽에 평행한 선분이 어떤 위치관계에 있는가로 구별됩니다.)

이들 \(6\)가지 경우 각각에 대해서, 그 모양에서 가능한 총합의 최댓값을 구한 뒤 그들의 최댓값을 구하면 문제의 답이 됩니다. \(2\)개 이상의 경우에 해당하는 \(M \times M\)칸의 배치도 있지만, 최댓값을 구하는 데 있어서는 문제가 되지 않습니다.

예를 들어, 다음의 \(2\)가지의 접근으로 이 문제를 풀 수 있습니다.

1. 각각의 나누는 방법에 대해, 선의 위치를 \(O(N^2)\)에 전처리하고, 각각의 부분에 포함되는 \(M \times M\)칸의 합으로 가능한 값을 구한다.
2. \(2\)개의 선으로 나뉜 영역에 들어가는 정사각형을 고정한 후, 많아야 \(10\)가지 정도 되는 경우에 대해 남은 영역의 최댓값을 계산한다.

각각의 접근에서, 직사각형 영역에 포함되는 정사각형 중 최대인 것을 구할 필요가 있습니다. 이 부분에서도 몇 가지 접근이 있습니다.

• \(2\)차원 세그먼트 트리나 \(2\)차원 희소 배열(Sparse Table)등을 이용해 전체 \(O((N \log N)^2)\)에 구한다.
• 필요로 하는 값들은 몇 가지로 정해져 있기에, \(O(N^2)\)에 이러한 모든 값들에 대해 전처리해 놓으면 \(O(1)\)이 되고, 이를 이용해 전체 \(O(N^2)\)에 답을 구한다.

\(6\)가지 경우의 나누는 방법을 위쪽 그림의 왼쪽 \(2\)가지와 오른쪽 \(4\)가지를 묶어 \(2\)가지 경우에서 애드 혹으로 푸는 방법도 있습니다.

선방했지만 FG는 어려웠다

이번 ABC는 CDE가 비슷비슷한 난이도로 나와서인지, 많이들 말린 모양…
다행히 E까지 잘 풀어냈지만, F가 이 모양이라…

많은 조건 분기를 해야 하는걸 안다고 했어도 구현량을 생각하면 시간 내엔 못 풀었을 것 같다.