mhy908의 PS 블로그 mhy908의 PS 블로그

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

1. Examinations 학생별로 (S, T)가 입력으로 주어지는데, 이것을 쿼리와의 일관성을 위해(S, T, S+T)의 tuple로 해석하자. 쿼리 (X, Y, Z)가 들어오면, S>=X&&T>=Y&&S+T>=Z인 쌍의 개수를 출력하는 것이 문제이므로, 둘다 내림차순으로 적절히 정렬한 다음 2d update와 query로 문제를 풀어주자. 쿼리에 대한 분할정복+펜윅 스위핑을 하면 O((N+Q)log^2(N+Q))에 AC. 2. Naan 일단 각 사람별로 각각 한 조각에 sum/N씩 있도록 처음부터 잘라준다. 사람 i에 대한 j번째 조각의 끝점을 A[i][j]라 하겠다. A[i][j]는 유리수. (유리수끼리의 비교함수를 작성할때 overflow를 조심하도록 하자...) 이제 greedy하게 조각을 처..