구사과

1. 작은 새각각의 쿼리가 그다지 연관성이 없어보이니, 그냥 K가 고정됐다 치고 각 문제를 독립적으로 풀어보자. 결국 쿼리당 O(n)에 해결하면 되니 말이다. O(n^2) 동적 계획법은 다음과 같이 어렵지 않게 할 수 있다. dp(i) = 1번에서 i로 오는 데 필요한 최소의 힘든 점프 수라 하면, 그 전 위치를 j라 했을 때에 대한 식으로 동적 계획법 표를 채울 수 있다. 기본적으로 dp(j)를 가져올 수 있지만, 만약 H_j Ei라는 것은, 어떠한 시간에 Si에 있다가, 그 후에 Ei에 있고, 그 다음에 Si에 다시 돌아와야 한다는 것을 뜻한다. 그렇다면, 최소 Ei -> Si로 한번은 거꾸로 가는 것이 필요하다는 것을 뜻한다. (거꾸로 간다는 것은 돌아온다는 것을 함의한다.) 이들을 [Ei, Si]..

1. 레이저원점을 지나는 직선이 해당 선분을 맞추려면 기울기가 어떠한 수의 구간 사이에 있어야 한다. 그러니 2차원 평면에 직선을 쏴서 선분을 맞춘다고 생각하지 말고, 수직선에 구간이 있는데 점을 몇 개 넣어서 구간들을 덮는다고 생각해보자. 모든 점들이 1사분면 위에 있고 x/y축에 닿지도 않기 때문에, 각 구간은 어떠한 분수와 분수 사이의 폐구간으로 쉽게 표현할 수 있다. 하지만, 더 간단하게 분수가 아닌 정수로 생각해 줄 수도 있다. 각 분수의 정확한 값이 아닌 대소 관계만이 중요하기 때문이다. 고로 좌표 압축을 통해 분수를 적당한 0 - 2n-1 사이의 정수로 바꿀 수 있다. 이제, 0 ~ 2n-1 사이의 정수를 시작점 끝점으로 가지는 n개의 폐구간이 있을 때, k개의 실수를 골라서 최대의 구간을 ..

(5/1 16:53 초판)(5/4 LM 풀이 추가, RST 약간 수정)(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가) 범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다. 팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다. 사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다. 후기는 그냥 좀 재미있던 것만 간략..