오늘 3월 19일은 대회가 두개나 있었다.. CROC 2016새벽에 했던 대회. 출제진에 대한 걱정이 컸었다. 저번 Div1D의 심슨 어쩌구에 대한 강한 기억이 아직도 (...) 물론 난 그 때 B도 못풀었지만 말이다. (그리고 폭풍 -118) CC부터 풀었다. 부분 합 + 이진탐색을 쓰는 쉬운 문제. 6분 AC. http://codeforces.com/contest/645/submission/16785733 B그리디. 일반식을 쓸까 하다가 BIT 짜는게 더 빠를거 같아서 그렇게 했다.9분 AC. http://codeforces.com/contest/645/submission/16786132 A당황스러웠던 문제. 쉬운 방법이 있을법도 하다 싶었지만, 그냥 백트래킹을 짰다.14분 AC. http://cod..
Network (ICPC Seoul Regional 2007)https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=283&page=show_problem&problem=1903처음에 DP로 접근했다 시간을 많이 날렸다. (DP 풀이는 잘 모르겠다.) 대충 이런 그리디를 짜서 live archive AC를 먹였는데, 데이터를 믿을 수 없는 저지이기 때문에 (...) 반례가 있다 싶으면 지적해주길 바란다. * 리프 노드를 깊이가 큰 순으로 정렬해서 처리한다. * 처리중인 노드에서 거리 K 이하에 서버가 없으면 노드의 K번째 조상에 서버를 지어준다. 아니면 넘어간다. 복잡도는 O(N^2)이다. Superset ..
http://www.codeforces.com/contest/484/problem/E질의를 볼 때 모든 길이 w의 subsegment를 다 볼거라는 생각으로는 진전이 없다. 대신, 답을 정해놓는 식의 binary search를 유용하게 쓸 수 있다. binary search로 접근해보자. 질의의 답이 H[i]라고 가정했을 때, 구간 [l, r] 내에서 주어진 조건을 만족하려면, H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이가 W 이상이어야 한다.즉 문제는 구간 [l, r] 내에서 H[i] 이상의 원소들로만 이루어진 연속 최대 구간의 길이를 구하는 것으로 정리되었다. 크게 두가지 방법이 있다. * 1. Persistent Segment Tree기본적으로 구간 [l, r] 내에서 연속 최대 구간..
- Total
- Today
- Yesterday