Codeforces Round #345

http://codeforces.com/contest/650

A

x같은거 + y같은거 - 둘다같은거

3분 AC

B
문제를 읽다가 내가 제대로 읽은건지 긴가민가해서, 시간을 너무 낭비한 문제. (큰 차이는 없었지만..) 시작 점을 binary search하던지, 답을 binary search 하던지, two pointers를 쓰던지...

16분 AC

C
tourist가 10분 안에 풀기에, 적어도 코딩은 쉬운 문제이구나라고 생각했는데, 결국 코딩이 쉬운 방법은 찾지 못했다. 그런 사람들 보고 함부로 문제 평가하지 말아야.. ㅠㅠ. 약간의 WA끝에 pretest를 통과.

풀이도 썩 쉽지는 않다. 같은 행 - 열에 있는 점들간에 그래프스럽게 에지를 이었다 생각하고 dfs하는게 풀이. 꽤 까다로운 문제였고 그런 의미에서 B만큼 많은 사람이 풀었다는 건 충격적이었다.

57분 AC

D
LIS + 쿼리라 자료구조 문제 냄새가 났고 그쪽으로 펜대를 열심히 굴리니 풀이가 보였다. 코딩이 쉽지 않을거 같아보였지만 그래도 할수 있을거 같아서 시작.

하지만 시행착오가 상당했다. 나의 경우에는 2D range query 자료구조가 필요해서 persistent segment tree를 짰는데 (그것도 참 고생하면서..) 초반에 WA난건 그렇다쳐도 결국 메모리 복잡도때문에 MLE가 나더라. 한번 더 줄여봐도 여전히 MLE.

시간이 아주 촉박했지만 (15분 남음) 그냥 persistent segtree를 밀고 (...) 이런 문제가 보통 그렇듯이 쿼리 정렬하면서 스위핑하는 식의 풀이를 시도했다. 다행이 이걸 좀 빨리 짰고 통과했다.

풀이도 코딩도 쉽지 않은 문제였는데 이거 역시 60명이 맞았다. 코포 무섭다.

115분 AC

E은 못읽었다.

결과
35등해서 2534 + 38 = 2572다. 2500대를 유지할수 있어서 좋았음. 대회가 6-8시라는 애매한 시간대라서 (일주일 전에 이랬으면 참 좋았는데) 편의점 도시락으로 석식을 때웠는데, 보람이 있어서 다행이었다.

메모리 제한이라... persistent segtree의 단점을 찾은 느낌이다 ㅠㅠ 앞으로 조금 가려서 써야겠다.

IGM 찍고싶다.