220916 문제 풀이 기록

P5 | 10651 - Cow Jog

풀이 시간: 약 30분

시도 횟수: 2회

체감 난이도: P5

풀이 쓸 의향: 下

풀이

입력값 쿼리인 입력 a, b에 endpoint e=a + b*t에 대해, multiset 및 lower_bound를 활용하여 지금까지 등장한 endpoint 중 현재 endpoint보다 작은 최대인 endpoint 없애고 현재 endpoint 넣기. 정답은 multiset size

여담: 태그를 보니까 LIS(nlogn)이던데, 생각해보니까 그렇게 풀어도 되긴 할듯 하다...만 위 풀이가 구현이 너무 쉽기 때문에 위 풀이로 풀었음. 처음에는 pq로 가장 작은 값 빼내려고 했는데, 틀리고 나서 생각해보니까 그러면 안됐음. 어쩐지 너무 쉽더라...

 

 

 

P3 | 10650 - Marathon

풀이 시간: 45분

시도 횟수: 4회

체감 난이도: P3(구현 많음)

풀이 쓸 의향: 下

풀이

합 segtree로 I부터 J까지 거리를, 최댓값 segtree로 I+1부터 J-1까지 각 checkpoint를 skip할때의 최대 이득을 관리하며 쿼리 수행하기

여담: 하나의 checkpoint를 수정해도 전체에서 자기 자신과 주변 두 개의 checkpoint에만 영향이 간다는 아이디어를 활용하는 문제. 처음에는 총 거리를 부분합으로 구현했다가 틀렸고, 나머지 두번은 sum segtree를 더할때 max segtree와는 다르게 i==1일때는 안더하고 i==n일때는 더해야 한다는 점을 망각했다가 틀림.

 

 

USACO 2014 December Gold 풀이 끝!