알고리즘 공부방

https://apio2019.ru/https://oj.uz/problems/source/389https://koosaga.com/232 내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...이번 년도의 문..

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) 의 상..