알고리즘 공부방

http://apio-olympiad.org/2016/https://oj.uz/problems/source/184https://koosaga.com/113 3. Gap Subtask 1 한번에 양 끝의 값 2개씩 알아간다고 생각하자. 지금 아는 끝값으로 쿼리를 날리면 그 다음 끝값 2개를 알 수 있다. 사용하는 쿼리의 개수는 ceil(N/2) 개로, 30점을 받 수 있다. Subtask 2 Subtask 2에서는 쿼리의 개수만 중요한 것이 아니라, 한 쿼리가 적은 수들을 덮고 있어야 한다. 만점을 얻기 위해서는 한가지 중요한 관찰이 필요하다.일단 첫번째 쿼리로 최소값과 최대값 s, e를 구했다고 생각하자. [s, e] 구간 안에 gap들은 N-1개가 있으니, max gap < (e-s)/(N-1) 의 상..

https://contests.ioi-jp.org/open-2018/index.htmlhttps://oj.uz/problems/source/351 역시 JOIOC는 어렵다. 문제 하나하나가 다 좋은 문제이고, 많이 생각할 수 있게 해주는 문제들인 것 같다.4일동안 1, 4번을 풀었고, 2번은 부분점수, 3번은 풀지 못하였다.Heavy Light Decomposition을 응용한 DP 최적화, Sqrt Decomposition 등 아직 내가 익숙하지 않은 개념들이 많이 이용되어서 더 어렵게 느껴진 것 같다. 나중에 이런 개념들을 잘 익힌 후에 꼭 다시 풀어봐야 할 문제들이다. 4. xylophone 순열이 하나 있고, 물어볼 수 있는 쿼리는 오직 어떤 구간 내의 최대값-최솟값만 물어볼 수 있을 때 2N 번..