ABC336 F - Rotation Puzzle
Competitive Programming C++
2024-01-18
공식 에디토리얼
문제 링크
https://atcoder.jp/contests/abc336/tasks/abc336_f
원문 링크
https://atcoder.jp/contests/abc336/editorial/9077
이 문제는 중간에서 만나기(meet in the middle) 알고리즘을 통해 풀 수 있습니다.
먼저, \(20\)번 이하의 조작으로 목표로 하는 격자판의 형태를 만들 수 있는지 판정하는 방법에 대해 생각해봅시다.
\(1\)번의 조작에서 할 수 있는 조작의 종류는 4가지 밖에 없으므로, 어떤 격자판의 상태에서부터 \(K\)번 이하의 조작으로 만들 수 있는 상태는 많아야 \(4^K\)개 입니다. 거기에 더해 같은 부분에 대해서는 연속해서 회전 조작을 하면 원래대로 돌아간다는 점을 주의하면, 많아야 \(4 \times 3^{K - 1}\)개인 것을 알 수 있습니다. 하지만, 이 문제의 제약 조건 하에서 만들 수 있는 상태는 최대 \(4 \times 3^{19}(\simeq 5 \times 10^9)\)개에 달하기 때문에, 일반적인 브루트포스를 사용하는 것은 현실적이지 않습니다.
여기서, 조작이 \(180\)도 회전인 것으로부터, 반대의 조작을 하면 자기 자신으로 돌아오는 것에 주목해보면, \(K\)번 이하의 조작으로 목표로 하는 격자판을 만드는 것이 가능한 상태의 집합은, 목표로 하는 상태에서부터 \(K\)번 이하의 조작으로 만들 수 있는 상태의 집합과 일치합니다.
따라서, 처음 상태에서부터 목표로 하는 마지막 상태까지 각각 \(10\)번 이하의 조작으로 만들 수 있는 상태의 집합을 \(T, U\)라고 했을 때, \(T\)와 \(U\)가 교집합을 가지는, 즉, 처음 격자판의 상태와 마지막 상태의 어느 쪽으로부터도 10번 이내에 만들 수 있느 상태가 존재하는 때에, 그 상태를 경유하여 \(20\)번 이하의 조작으로 마지막 상태로 만드는 것이 가능하며, 반대로 교집합을 가지지 않는다면 불가능하다는 것을 알 수 있습니다.
그러면, 최소 횟수를 구하는 방법은 아까의 \(T, U\) 집합을 분할하는 것으로부터 마찬가지로 가능합니다.
\(i = 0, 1, …, 10\)에 대해, \(T_i\)를 처음의 상태로부터 \(i - 1\)번 이하의 조작으로는 만들 수 없지만 \(i\)번의 조작으로는 만들 수 있는 상태들의 집합이라고 정의합시다.(여기서 \(T_0\)은 처음 상태만 있는 집합입니다.) 마찬가지로 \(U_i (0 \leq i \leq 10)\)를 마지막 상태로부터 \(i\)번의 조작으로 처음 만들 수 있는 상태들의 집합이라고 정의하면, 답은 \(T_i\)와 \(U_j\)의 교집합이 있는 \((i, j)\)에 대해 \(i + j\)의 최솟값입니다.
실제로는 \(T_i\)와 \(U_i\)가 교집합을 가질 때, 정의에 의해 \(i + j = i’ + j’\)인 \(T_i’\)와 \(U_i’\)도 교집합을 갖는 것으로부터, 각 \(i + j\)의 값에 대해 \(1\)개의 조합만 확인되어도 충분하며, 예를 들자면 다음의 \(2\)가지만 확인해도 됩니다.
- \(i = 0, 1, …, 10\)에 대해 \(T_i\)와 \(U_0\)의 교집합이 존재하는가
- \(j = 1, 2, …, 10\)에 대해 \(T_{10}\)와 \(U_j\)의 교집합이 존재하는가
위의 예시 중에서 교집합을 가지는 경우가 있는 경우엔 각각 \(i\) 또는 \(10 + j\)가 답이 되며, 어느 쪽이든 교집합을 갖지 않는 경우엔 \(-1\)을 출력하면 됩니다.
시간복잡도를 계산하자면, \(K / 2\)번 이하의 조작으로 만들 수 있는 상태들을 모두 만드는 데는 격자판을 조작을 생각해서 \(O(3^{K / 2} \times N^2)\)가 됩니다. 거기에 더해서 집합에 대한 존재 유무의 판정에는 \(O(HW)\) 걸린다고 하면, \(1\)번 당 \(O(HW \log 3^{K/ 2}) = O(KWH)\)만큼 걸리며, 이 판정을 \(3 \times 4{K / 2 - 1}\)번 하게 되므로, 전체의 시간복잡도는 \(O(3^{K / 2} \times KHW)\)가 됩니다. 이번엔 \(K = 20, H, W \leq 8\)인 것으로부터 \(3^{K / 2} \times KHW \simeq 8 \times 10^7\)정도가 되어, 제한시간인 5초면 충분합니다.
또한, 각 칸에 쓰인 숫자로부터 \(1\)을 빼면 각 칸의 상태를 \(6\)bit로 관리할 수 있어(\(HW \leq 64 = 2^6\)이므로) 격자판의 상태는 많아야 \(6 \times 64 = 384\)bit로 나타내는 것이 가능합니다. 이를 이용해 격자판의 상태를 관리하는 방법을 생각해보면 더 빠르게 푸는 것도 가능합니다.
중간에서 만나기는 알았는데…
이전에 비슷한 문제를 푼 경험에서 중간에서 만나기인건 보고 알았으나,
문제는 그게 종료 10여 분 전이었다는 점과, 구현량을 따라갈 수 없었다는 점.
D에서 시간 까먹고 E에서 머리 싸멘 것이 풀 수 있었을 F도 못 풀게 한 것 같다.
다음엔 더 잘 해야지…