Aliens DP 공부중임

사실 Aliens DP 공부하는거 개 쓸모없다고 생각했음. 이거 쓰는 문제 대회에 나와봐야 저어어 뒤에 나올텐데

그 뒤까지 내가 도달하지도 못할거고 도달한다고 한들 시간 얼마 안남았을텐데 알아봐야 제시간안에 구현도 못할테니까.



https://atcoder.jp/contests/arc168/tasks/arc168_e

E - Subsegments with Large SumsAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp



그런데 최근 ARC-E에서 Aliens DP를 쓰는 문제가 나왔고, D까지 빨리 풀어서 E를 풀 76분의 넉넉한 시간이 있었지만

Aliens DP를 몰라서 이 문제 아예 접근조차 못하고 76분동안 멍때리고 나왔어서 이제 Aliens DP같은것도 공부해야겠구나... 싶어서 공부 시작했음.

어렵더라............


원래 목표는 Aliens DP를 푸는 함수 템플릿처럼 만들어서 대회중에 가져다 쓸 수 있게 만드는거였는데,

O(N^2logW)라고 설명한 글과 달리 Aliens DP를 쓰는 모든 문제가 DP최적화까지 가져다 써서 O(NlogNlogW)등을 요구하더라;;;

그것도 DP최적화 쓰는게 죄다 달라서 어떤건 Monotone Queue Technique, 어떤건 Convex Hull Trick, 어떤건 Segment Tree위에 올리는 테크닉쓰고

아예 템플릿으로 만드는게 불가능해보여서 그냥 대회중에 마주치면 최대한 빨리 풀 수 있게 많은 문제들 풀면서 손에 익혀두려고 하고있음

그래서 일단 2개를 풀었고 하나 더 풀려고 했는데......


https://www.acmicpc.net/problem/17439

Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net


못풀겠음 -_-

cost function에서 도저히 좋은 성질이 보이지 않아서 대충 태그 까보니까 Monotone Queue Technique 쓰더라고

그런데 사실 나 Monontone Queue Technique도 모름.... (위에 설명한것과 비슷한 이유로 알아봤자 쓸모 없다고 생각했기 때문에 공부를 안함)

그래서 Monontone Queue Technique 공부하고있음... 분명 Aliens DP 공부하고 있었는데 공부할게 끝이 없네



Aliens DP 구현이 왜이리 어려운지 모르겠다. 사실 DP최적화 + 이분탐색이 끝이라 익숙해지면 빠르게 코딩할만할텐데, 도저히 익숙해지지가 않음.

구현에 비직관적인 부분도 많고.(예를 들어, 이분탐색시 변수의 min,max 범위 설정, 반정수부분 탐색, 구하려는 함수의 convexity 증명등등)

관련 문제 읽기 시작한 시점부터 1시간 이내에 AC 받을 수 있을 정도까지 트레이닝 하려고 함(1시간 이내에 AC 못받으면 공부해봤자 대회중에 못푸니까)


힘들다