BOJ 26410. Intersection of Tangents 답은 $(min(x_i), min(y_i))$ 입니다. 이 점에서는 $x$ 축에 평행한 접선과 $y$ 축에 평행한 접선을 그을 수 있습니다. 자명하다고 볼 수도 있고, 이런 저런 복잡한 접근이 정수 점을 잘 못 찾는다는 점에서 착안할 수도 있겠습니다. BOJ 26408. Game 쿼리당 $O(n)$ 먼저, 최적 전략에서 캐릭터는 최대 한번 이동함을 관찰할 수 있습니다. 어떠한 시나리오에서 두 명 이상이 이동을 선택했다고 합시다. 전략에 의해 마지막으로 이동을 선택한 사람이 그 게임의 승자가 됩니다. 그 경우, 그 전에 이동을 선택한 사람은 본인이 결론적으로 게임을 짐에도 불구하고 이동을 선택했기 때문에 가정에 모순입니다. 두 번째로, 승자는..
이 글에서는 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 ..
- Total
- Today
- Yesterday