구사과

[2015/07/24 MCMF 보강] [2016/10/03. 옛날에 썼던 글이라 내용을 대폭 보강해서 다시 올린다. 이 글은 "정리하는" 개념의 글이니, 문제나 알고리즘에 대한 구체적인 설명은 따로 찾길 바란다.] [2016/10/14 잡설을 추리고 증명 관련 부분을 개별 글로 뺐다. 증명 뿐만 아니라 "답을 출력하는" 일이 필요하다면 해당 글 참고] 유량(flow) 관련 문제는 대부분 유량을 흘릴 수 있는 경로를 찾고 그 경로에 유량을 보내줌으로써 해결한다. 비슷비슷해서 난 별로 차이가 없는 줄 알았는데 얼마전 DFS로 maxflow의 증가경로를 찾으면 안된다는 얘기를 듣고 멘붕함. 이 기회를 통해서 정리하려 한다. 여담으로, 프로그래밍 콘테스트 챌린징의 네트워크 유량 부분에 굉장히 중요하고 쉽게 배우..

(Autoamerican, 1980)

푼지 몇달 된 것도 있고 얼마 전에 푼것도 있다. ONTAK2010. Garden https://www.acmicpc.net/problem/8468 쉽게 생각할 수 있는 아이디어는 N^2개의 행을 잡고, 행 각각에서 교집합을 잡아서 O(N) 루프를 돌리는 것이다. N^3의 끔찍한 시간 복잡도를 가지기에 여기서 포기하기 쉽지만, 놀랍게도 sqrt decomposition을 통해서 큰 차이 없이 N^1.5 정도에 풀 수 있다. 행 R에 대해서, Xi == R을 만족하는 i의 개수가 N^0.5 이상일 경우 heavy row라 하고, 아닐 경우 light row라고 하자. 두가지 방법으로 문제를 해결한다. * 두 행 쌍 중 하나라도 light row일 때를 세주자. light row를 하나 잡고, 고를 수 있는..