이번 라운드는 할말이 별로 없는듯.. 푼 순서대로 서술한다 A 이 라운드가 dynamic scoring 인줄 몰랐다 맨 처음엔. 내가 너무 싫어하는 lexicographical + bracket 의 연속이라 정말 풀기 싫었는데 5분만에 E번을 푸는 사람이 나오면서 아 이거 dynamic scoring이구나를 깨닫고 던졌다. 결국 라운드 끝날 때 A가 가장 어려운 문제로 확인. 솔직히 딱 봐도 어려워 보인다. E 5분만에 AC가 나와서 아 저거 복붙충 아니냐 **.. 은 농담이고. 쉬운가 싶어서 바로 봤다. (다만 3~5분 AC는 복붙이 맞는 거 같다) 처음 문제를 봤을때는 풀수 없음을 증명하는게 빠르지 않을까 (...) 하고 당황했는데 제약 조건을 본 후 그냥 평이하게 풀리는 문제임을 확인했다. 20분 ..
http://poj.org/problem?id=2104https://www.acmicpc.net/problem/7469 1. Naive - O(MNlgN)더 이상의 자세한 설명은 생략..O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ; 2. Query Sorting - O(NlgN + M*N^0.5*lgN)http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4때문에 역시 자세한 설명은 생략.간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..
pdf로 대신한다.
- Total
- Today
- Yesterday