구사과

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점을 득점했었다 (...) 그래서 안 짜증났다. 후기는 그냥 좀 재미있던 것만 간략..

1. Fenced In (Platinum)독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번..

1. Digit DivisionSi = 주어진 숫자의 i자리 prefix를 mod M으로 나눈 나머지라고 하자. Si 배열은 선형 시간에 쉽게 계산할 수 있다.주어진 숫자들을 적당히 나눈 partition이 대충 [i1 + 1, i2] / [i2 + 1, i3] / [i3 + 1, i4] / ... / [i_{k-1} + 1, i_k] 와 같이 생겼다고 하자. 물론 i1 = 0, i_k = N이다. 이 partition이 올바르려면, 모든 1 이상 k 미만의 idx에 대해서 S_{i_{idx + 1}} = S_{i_ idx} * 10 ^ (i_{idx + 1} - i_idx) (mod M)을 만족해야 한다. 이 때, S_{i1} = 0 (mod M)임을 알 수 있다. 고로 S_{i2} = 0 (mod ..

https://docs.google.com/spreadsheets/d/1-kY6uiLOo1AKSBCSjbpGRBZbIldO_3dg6oTRKIJzT-g/edit#gid=0주요 OI 문제들을 연도별로 정리해서, Google Docs 문서로 정리해 보았다. 저렇게 표까지 만든 건 IOI 2017 멘토 / 합숙 교육에서 사용하기 위함이었고, 추후 교육에서도 사용될 수 있을 것 같다. 이 표가 가장 유용할 만한 타겟은 IOI를 국가 대표 레벨에서 대비하는 학생들이라고 생각한다. 하지만, ICPC 세계 대회 등 굳이 정보올림피아드를 준비하지 않는 입장에서도 충분히 풀어볼만한 문제들이라고 생각한다. 나의 경우만 해도 여전히 저러한 문제들을 ICPC 문제들보다 우선해서 공부하고 있다.공부에 유용한 자료가 되길 바란다...

1. 평균값 수열수열의 초항 S1을 결정했다 하면, S2 ... SN까지 모든 숫자들이 도미노처럼 결정된다. S_{i+1} = 2 * m_i - S_i 이기 때문이다. 고로, S1을 결정하면 모든 수열의 원소를 알 수 있고, 이들이 단조 증가 하는지만 체크해 주면 된다. 모든 S1을 다 해 볼 수 없으니, 대신 S1 = x라고 두고 부등식을 계속 쓰는 식으로 x가 답이 될 필요 충분 조건을 찾아보자. 이렇게 했을 때, 수열은 {x, 2m1 - x, 2m2 - 2m1 + x, 2m3 - 2m2 + 2m1 - x ... } 과 같은 형태로 구해진다. 단조 증가한다는 것은 인접한 항들이 모두

1. Vouchers각각의 상자에 voucher의 번호를 적어놓은 후, 모든 배수를 순회하는 단순한 접근법으로 접근한다면, 쿼리당 O(n)의 시간이 걸리고 시간 초과가 날 것이다. 하지만, 에라토스테네스의 체만 생각해 봐도 줄일 여지가 충분하다. 모든 배수들을 열거하는 데 드는 시간은 O(n)이 아니라 O(n / a_i) 이기 때문이다. 고로 쿼리로 주어지는 모든 숫자가 다르기만 해도 O(nlgn) 시간 복잡도를 보장할 수 있다. O(n/1 + n/2 + n/3 + ... + n/n) = O(nlgn)이기 때문이다.쿼리로 같은 숫자가 여럿 들어온다 하더라도 문제가 크게 달라지지 않는다. X번 쿼리로 가져간 최대 번호의 상자가 last_X번이라면, 다음 번에 볼 때 X ~ last_X 번의 상자들은 볼 필..

1. Mountain RoadA 타입 차와 B 타입 차를 분리시키고 생각해 보자. 각각의 그룹에서 먼저 도착한 순서대로 차들을 처리해야 하니, A 차가 현재 몇 대 까지 / B 차가 현재 몇 대 까지 처리되었는지 정도의 상태로 DP를 돌려보자.A와 B가 항상 교차해서 나온다면 단순히 끝나는 시간만을 고려해주면 되겠지만, 실제로 A 차가 연속하거나 B 차가 연속할 경우에는 일련의 추가적인 규칙들이 있다. 고로, 현재의 DP 상태에서 연속한 A 차를 추가하거나, 연속한 B 차를 추가해서 새로운 DP 상태의 시간을 계산해야 한다. 또한, 마지막에 A를 썼는데 거기에 연속한 A 차들을 추가하면 계산이 꼬이니, 현재의 DP 상태는 단순히 차를 몇 대 쓴 것만이 아니라, 마지막에 무슨 차를 썼는지 역시 저장해야 한..

1. 텔레점프아이디어의 큰 틀은 생각보다 간단하다. 다만 이를 실제로 완성하는 건 꽤 까다로운 문제이다. * 먼저 처음에 A 에지 하나와 B 에지 모두를 소모해서, 앞 부분의 점을 다 연결 시켜준다. 1 - 2 / 1 - 3 / 2 - 4 / 3 - 5 ... * 이제 A 에지와 C 에지만이 남았다. B 에지로 만든 path의 두 끝 점 중 하나는 버리고 (즉 시작점으로 하고), 나머지 하나를 이어나갈 것인데, P / P + 3 / P + 6 ... 이런 식으로 이으면 중간에 공백이 생기니, A 에지를 하나 사용해서 P + 1 - P + 2를 이어주고, P + 1 / P + 4 ... 혹은 P + 2 / P + 5 ... 를 계속 이어준다. C 에지를 전부 소모할 때까지 이를 계속한다. * 남은 에지들은..