구사과

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 상태는 단순히 차를 몇 대 쓴 것만이 아니라, 마지막에 무슨 차를 썼는지 역시 저장해야 한..