알고리즘 공부방

문제 https://oj.uz/problem/view/JOI13_synchronization 문제 보기 - 동기화 (JOI13_synchronization) :: oj.uz JOI Co., Ltd.는 전 세계에 무려 $N$대의 서버를 두고 있습니다. 각 서버에는 중요한 정보의 일부가 저장되어 있고, 서로 다른 서버에는 서로 다른 정보가 저장되어 있습니다. JOI Co., Ltd.는 서버들끼리 정보를 공유하기 위해 서버들 사이에 정보를 양방향으로 교환할 수 있는 회선을 설치하고 있습니다. 정보들은 회선을 통해 여러 서버를 거쳐갈 수 있습니다. 각 서버는 고성능 동기화 시스템을 갖추고 있습니다. 두 서버가 서로 정보를 교환할 수 oj.uz 트리에서 처음에는 각 노드가 자기 자신만을 들고 있고, 각 시간마다 ..

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 번..