본문 바로가기

분류 전체보기

 (54)
2026 ICPC APAC Championship 후기 이번에 처음으로 국제대회에 나가보았다. 아시아 챔피언십을 가서 어떤 것을 했는지 알아보자!팀소개우리 팀은 Fox is Cute로, (송씨, 세린, 나)가 한 팀이다.세린은 카이스트 가을대회에서 루비4를 풀 정도로 자료구조를 잘한다. 나는 애드혹 및 조합론에 강하다. 한때 군대에서 폐관수련을 위해 Atcoder ARC를 20라운드 정도 버추얼을 돈 경험이 있다. 예전에 랜덤디펜스를 조금 해서 그런지 종이에 구현을 정리했다가 키보드를 잡고 빠르게 구현하는 것을 잘한다. (구현이 맞는다는 보장은 없다. 이럴때는 프린트 디버깅을 하고 시간을 하염없이 보낸다) 그리고 문제를 풀 때 증명을 하는 것을 중요하게 생각한다.송씨는 그냥 구현도 잘하고 문제도 잘 풀고 강하다. 유럽 챔피언십 버추얼을 돌 때 어려운 문제를 ..
2026 국가대표 1차 선발고사 출제 후기 이번 선발고사에 출제한 문제들의 이야기를 들어보자. 스포일러가 다수 있다.1. 균형잡힌 수열문제 만들기때는 군대에 있던 시절(언제였는지는 기억 안 난다) 중국 코드포스 라운드에서 998244353개의 양산형 특이한 꼴의 개수 세기 문제들이 나오는 것을 보고 나도 날먹을 하고 싶어서(...) 특이한 꼴을 만들었다. 그것이 바로 균형잡힌 수열인데, 생각보다 양산형 문제가 아니었고 쿼리를 넣었을 때 나름 재미있게 풀려서 문제 리스트에 넣어두고 있었다. 서브태스크 만들기OI 계열의 문제를 만들려면, 서브태스크를 만들어야 한다. $Q=0$은 당연히 들어가는 서브태스크이다. $O(NlogN)$에 푸는 것이 자명하지 않을 수 있기 때문에 $O(N^2logN)$에 문제를 푸는 서브태스크도 만들어줬다. $A_i \le ..
2025년 회고록 2026년이 된지 무려 7일이나 되었지만, 지금 아니면 정말 늦을 거 같아서 2025년 회고록을 써본다. 문제 풀이 루비로 빨갛게 빛나던 2024년과 다르게, 이번 해에는 루비를 3개만 풀었다. 크게 3가지 이유가 있는데, 첫번째는 마스터를 찍어서 더 이상 올릴 티어가 없다는거고, 두번째는 평소에 루비를 열심히 풀어도 대회장에서 다이아 하위에서 말리기 때문에 대회 성적을 올리는 측면에서 다이아를 푸는 능력이 더 시급하다고 생각했기 때문이다. 세번째는 군대처럼 ps가 가장 재미있는 세상에 살고 있지 않기 때문이다. 그래도 다이아 상위를 무서워하지 않는 점에서 ps 실력에 대해 어느 정도 만족을 하고 있다. 나의 약점 중 하나가 구현을 빠르고 정확하게 못한다는 것이다. 그 이유를 코드의 길이가 긴 것으로 생..
2025 ICPC Seoul Regional 본선 후기 이번에도 Fox is cute 팀으로 나갔다. 팀원은 SongC와 serin이다. 모두 코드포스 기준 레드 이상이라서 나름 잘하는 팀이라고 생각한다. 팀연습카이스트 가을대회에서 2등을 했다. 세린의 H번 버저비터가 인상적이었다.SEERC 2024를 돌아 1위 성적을 냈다.지금와서 찾아보니 최근 2달간 별로 팀연습을 안한거 같다. 아시아 퍼시픽 챔피언십까지는 좀 해야겠다. 개인 ps시험기간때 ps를 완전히 놓았다가 시험기간이 끝나고 다시 재활을 시작했다.UCPC 2025 문제들을 모두 풀어봤다. 생소한 알고리즘들을 좀 써서 나름 교육적인 셋이었다고 생각한다. 이거 푸는데 2주 걸렸다.icpc 직전에 기출을 좀 공부하고 갔다. 2022 icpc때 현장에서 풀었던 empty quadrilateral, long..
2025 KAIST 15th ICPC Mock Competition 후기 카이스트 가을대회를 쳤다. Fox is cute 팀으로 쳤다. 팀원은 SongC, serin이다. 이번에는 외부인 팀들이 정말 많이 와서 대회장이 북적거렸다. 고등학생 팀들도 오고 흥미로웠다. 내가 JKLM, serin이 중간, SongC가 앞부분을 보기로 했다. 0:00 ~ 1:00누가봐도 무서운 J번을 빠르게 스킵, K번을 (이상한 그래프 카운팅 문제인 줄 알고) 스킵하고 L번을 봤는데 그냥 앳코더 카운팅 문제였다. 팀원들한테 대충 풀릴거 같다고 말하고 풀이 구상에 들어갔다. 그 사이에 팀원들이 A/B를 잡고 풀었다.0:18, 0:28 (A WA +2) 0:29 (A AC)0:25 (B AC) L번 구체화를 마치고 구현에 들어갔다. 그런데 생각보다 코드가 꽤 길었고, 예제가 안 돌았다. (예제가 꽤 ..
250917 연습 최근에 문제풀이를 열심히 하고 있다. 1. 랜덤디펜스다이아를 찍었다.적당히 잘 풀었다. N과 M은 그냥 개못해서 못 풀었고, Even Three is Odd는 풀이를 복잡하게 내서 사망했다. 나머지는 무난하게 잘 풀었다. p3-d4 난이도에 오니까 국밥이 많다는 것 빼고 문제 풀이 좋은 것 같다. 2. 팀연습NWERC 2024를 올솔했다. 나하고 세린이 B를 잡으면서 엉엉 울고 있을 때, 송씨가 트리에서 풀어보라고 했고, 아이디어가 발전되어서 풀렸다. G와 I는 그냥 송씨가 혼자서 풀었다. 그저 GOAT NWERC 2022는 나와 송씨가 2인팀으로 돌았다. 내가 G에서 말렸다. 그래도 어찌 풀기는 했다. K와 L을 송씨가 밀어줬다. F는 풀었으면 좋았겠지만 게을러서 (그리고 기하가 무서워서) K를 맞추..
Lawson Algorithm을 통한 Delaunay triangulation 구하기 본 글은 평면 위 점들의 집합을 가장 안정적이고 균일한 삼각형들로 분할하는 Delaunay Triangulation을 종합적으로 탐구한다.먼저 보로노이 다이어그램과의 관계 및 '빈 외접원 속성'을 통해 들로네 삼각분할의 수학적 정의를 명확히 하고, 이어서 고전적인 구축 방법인 Lawson's algorithm을 분석한다.마지막으로 이 알고리즘이 왜 항상 정확한 결과를 보장하는지를 증명하기 위해 2차원에서의 문제를 3차원으로 lifting하는 우아한 기법을 사용한다.1. Delaunay triangulation의 정의와 최적성평면에 분포된 유한한 점의 집합을 겹치지 않는 삼각형들로 분할하는 triangulation은 계산기하학의 근본적인 문제 중 하나로, 유한요소해석, 컴퓨터 그래픽스, 지형 모델링 등 다..
SCPC 2025 후기 SCPC에서 상을 이미 2번 받은 나는 더 이상 상을 받을 수가 없다. 그래서 이번 scpc는 오프라인 대회장에 가는 것을 위해서 치기로 했다. 예선 1차이때는 몰입캠프 중에 있었다. 1차는 조금만 풀면 통과해서 밤에 대충 쳤다. 만점을 받았다.예선 2차꽤나 어려웠다... 1번 2번은 쉽게 풀었는데 3번에서 막혔다. 스위핑을 하는 복잡한 풀이가 나와서 오랜 시간 구체화만 하다가, 이 문제를 이렇게 풀게 되었다가는 디버깅만 하다가 끝날 것 같다는 생각이 들었다. 그래서 4번에서 서브태스크 2를 긁기로 했다.설상가상 4번 서브태스크도 왜인지 모르게 틀렸다. 중간에 멘탈이 나가서 잠깐 샤워를 하고 왔다. 차분하기 읽어보니까 내가 점수 조건을 잘못 읽었다는 것을 깨달았다. 지문에 있는 기준은 d_G(x, y) ..

티스토리툴바