구사과

이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수 있는지 역시 생각해 보면 좋을 것이다. 이 자료구조에 대해서는 예전 코드포스 글을 통해서 한번 들어보고 메모만 해 놓았으..

이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 별 일 없다면 상위 3팀이 진출할 것이다. 서울대학교: C14H9Cl5 KAIST: BabyPenguin (World Finals 진출 확정) 숭실대학교: NLP (World Finals 진출 매우 유력) POSTECH: 000102 (World Finals 진출 가능성 약간 존재) 고려대학교: I hate PS 코로나19로 인해 2020 World Finals가 1년 반 정도 연기된 관계로, 2022 및 2023 World Finals는 이집트에서 한번에 진행한다. 서울대학교 1등 팀인 C14H9Cl5는 FSM과 동일한 멤버로 구성된 팀으로, 이번 대회를 통해 2022, 2023 World Finals의 진출 자격을 모두 얻었다. World ..