CEOI
-
CEOI 2009 Day 2 SolutionsCEOI 2020. 3. 24. 14:11
1. Logs 문제 제한부터 log를 용납하지 않겠다는 의지가 보인다. 일단 가장 처음 행부터 아래 행까지 스위핑을 해보자. 각각의 열마다 자신을 포함하여 위로 몇개의 연속한 1이 있는지 관리하는데, 이를 H[j]라 하겠다. 각각의 칸마다 H[j]를 구하는 것은 각 행마다 O(M)이면 충분하고, (바로 윗 행의 정보를 토대로 빠른 계산 가능) 이를 내림차순으로 정렬하면 답을 구할 수 있다. 문제는 시간복잡도가 O(NMlogM)이어서 TLE를 받게 된다. 이때 한가지 관찰을 해야되는데, H[j]는 항상 1씩 증가하거나 0이 되는 연산밖에 없어, 0이 되는 j를 앞으로 빼주기만 하면 윗 행의 정보를 토대로 O(M)에 정렬된 상태를 유지해 줄 수 있다는 것이다. 이를 이용해 O(NM)에 AC. 추가로, 입력받..