-
Suffix Automaton
Suffix Automaton 문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는...
-
Introduction to APSP Conjecture and BMM Conjecture
Introduction to APSP Conjecture and BMM Conjecture 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 “쉽다” (algorithm) 내지는 “어렵다” (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다. 어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 “어려움을 증명하는” 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 “어떠한 문제는 풀...
-
Segment Tree Beats와 Kinetic Segment Tree
Segment Tree Beats와 Kinetic Segment Tree 이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수...
-
ICPC World Finals 2021 풀이
11월에 ICPC World Finals 2021에 참가했습니다. 이후 11월 말까지 한 문제를 제외한 나머지를 모두 풀었고, 이 글에서 모든 문제의 풀이를 정리합니다. 최근 3년과 달리 상대적으로 쉬운 (플래티넘 하급 이하) 문제가 좀 더 많이 나왔는데, 그것들을 푸느라 더 어려운 문제에 쓸 시간이 부족했습니다. A: Crystal Crosswind 바람의 방향이 $(w_x, w_y)$, 가장자리의 집합이 $S$라고 하면 다음과 같은 정보를 얻습니다. (1) $(x, y) \in S$일 경우, $(x, y)$은 분자고, $(x - w_x, y - w_y)$는 빈칸입니다. (2) $(x,...
-
2022 ICPC Seoul Regional
2022 ICPC Seoul Regional ICPC 서울 리저널 측이 공식 풀이를 제공하지 않아서 2020년부터 ICPC 리저널의 비공식 풀이를 작성하고 있다. 이번에도 그 때와 같이 2022 ICPC Seoul Regional의 문제를 풀어보는 시간을 가진다. 올해 문제의 난이도는 작년과 유사한 수준으로 꽤 어려운 편에 속한다. 체감상은 작년보다도 약간 더 어려운 느낌인데, 스코어보드로는 그렇게 보이지 않는다는 점에서 참가 팀의 수준이 높아졌다고 느꼈다. 일부 문제들은 구현했으며, Github 에 icpc22_ 로 시작하는 이름으로 AC 코드를 업로드하였다. 문제 풀이 한 줄 요약 A:...
-
2021 ICPC Seoul Regional
2021 ICPC Seoul Regional 이 글에서는 2021 ICPC Seoul Regional의 문제 풀이를 다룬다. 올해 문제는 예년 비해서 상당히 어렵게 출제된 편이다. 거의 모든 해에서 우승 팀이 모든 문제를 풀었고, 그렇지 않은 해 (2015, 2018 등) 에도 웬만하면 한 문제 빼고 다 풀었다는 점을 감안하면 상당히 이례적이다. 다만 모든 문제를 푸는 난이도는 솔직히 2018년이 더 어렵지 않나 싶다. 솔직히 말해서 문제가 자꾸 봤던 유형에서 계속 재탕 삼탕하는 느낌이 너무 강하다. 어느 정도야 그럴 수 있겠지만 올해는...
-
Top Tree로 Dynamic Tree 관리하기
Top Tree로 Dynamic Tree 관리하기 이 글을 읽기 이전에 동적 계획법을 최적화하는 9가지 방법 (4/4) 의 “Dynamic Tree DP” 단원을 이해하는 것이 좋다. 이 글은 해당 내용을 잘 이해하고 있다고 가정하고 설명한다. 그래프의 특수한 경우인 트리는 PS를 포함한 알고리즘 전반에서 자주 활용되는 구조이다. 트리는 일반적인 그래프에 비해 여러 방면으로 효율적으로 관리할 수 있다. 이러한 방법은 그 자체로도 관심의 대상이 되며, 그래프 문제를 풀 때도 다양하게 응용할 수 있다. 너무나도 중요하다는 사실이 잘 알려져 있으니, 구태여...
-
2020 ICPC Seoul Regional
Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: Let Us Win ICPC WF (World Finals 진출 확정) KAIST: Everybody (World Finals 진출 매우 유력) 고려대학교: 1_Hoeaeng_2_Hawawang (World Finals 진출 예상) 숭실대학교: 181920 (World Finals 진출 가능성 있음) 성균관대학교: we need sleep 올해 서울 리저널은 관전자 입장에서 재밌게 볼 만한 요소가 아주 많은 대회였다. 그래서 관전 포인트도 좀 긴 편이다. 온사이트였으면 재밌었을 것 같은데 참 아쉽다. 서울대학교 내전. 올해 서울대학교는 예년처럼...
-
IOI 2020
IOI 2020 IOI 2020 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 최은수, 100 / 100 / 100 / 100 / 93.00 / 100, 593.00점, 2등 (금메달) 송준혁, 75 / 100 / 100 / 100 / 92.62 / 65.32, 532.94점, 12등 (금메달) 임성재, 44 / 100 / 41 / 100 / 92.24 / 100, 477.24점, 30등 (은메달) 반딧불, 32 / 100 / 53 / 21 / 80.14 / 100, 386.14점, 61등 (은메달) 올해 한국 학생들의...
-
2019 국제정보올림피아드(IOI) 문제 풀이
IOI 2019 Day 1 IOI 2019 Day 1 대회가 종료되었다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 김세빈, 100 / 40 / 100, 240점, 8등 - 25등 윤교준, 100 / 40 / 72, 212점, 26등 - 59등 임유진, 100 / 40 / 72, 212점, 26등 - 59등 이온조, 100 / 64 / 38, 202점, 60등 올해도 미국의 Benjamin Qi가 만점인 300점을 3시간 30분만에 얻었다. 문제가 쉽지 않았음에도 불구하고...
-
프로그래밍 대회를 개최하기 위한 10가지
프로그래밍 대회를 개최하기 위한 10가지 이 글은 Ajou Programming Contest(2016-19 APC), 경인지역 6개대학 연합 프로그래밍 경시대회(2016-19 shake!), 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회(2016 UCPC)를 운영했던 제 경험을 토대로 작성되었습니다. 프로그래밍 대회를 개최하려는 분들께 조금이나마 도움이 되었으면 하는 마음으로 대회를 맡으며 경험했던 시행착오를 모아 필요한 10가지를 정리해보았습니다. 어디까지나 제 개인의 경험에 기반한 내용으로 대회를 열기 위해서는 이래야 한다!가 아닌 아래 과정을 고려해보자는 의미로 읽어주시면 좋겠습니다. 일의 진행 순서로 나열하긴 했지만 모든 과정은 유기적입니다. 대회의...
-
2019 한국정보올림피아드(KOI) 중/고등부 문제 풀이
2019 한국정보올림피아드(KOI) 중/고등부 문제 풀이 중등부 1번. 신기한 수 Subtask 2 (100점) 숫자 $N$ 이 주어지면, 해당 수의 일의 자리에 적힌 수는 $N \mod 10$ 이 된다. 이후 숫자를 10으로 나눠주면, 십의 자리, 백의 자리… 에 있던 수들이 모두 일의 자리, 십의 자리로 움직인다. 고로, 이를 반복하면 $O(\log N)$ (입력에서는 최대 8번) 의 단순 연산으로 $N$의 자릿수 합을 알 수 있다. 어떠한 수 $A$ 가 어떠한 수 $B$ 로 나누어 떨어지는 것은, $A$ 를 $B$...
-
shake! 2019 본선 출제 후기
shake!는 경인지역 6개 대학(아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교 ERICA)의 학생들이 참여하는 대회입니다. 예선을 통해 각 학교 대표 10명이 선발되고, 본선에는 60명의 대표들이 모여 대회를 치룹니다. 이 포스트는 2019년 shake! 본선(7월 7일에 열림)의 출제위원을 맡으면서 있었던 일들과 결과에 대한 후기를 다룹니다. 기타 운영에 관해서는 참여하지 않았기에 후원사 찾기, 출제진이 구성되는 과정 등은 다루지 않습니다. 출제진은 koosaga님과 ainta님, spectaclehong님, 그리고 메인 운영진인 Acka님과 저(hojoon0205)로 이루어졌습니다(모두 acmicpc.net 아이디 기준입니다). 혹시 이 대회의 문제들을 풀어보고 싶으신 분들은 백준...
-
번사이드 보조정리(Burnside Lemma)
서론 Burnside Lemma(번사이드 보조정리)는 Group action에서 나오는 정리입니다. 여기서 말하는 Group이란 대수학에서의 Group을 의미합니다. Competitive Programming에서 아주 가끔씩 경우의 수를 세는 문제에서 활용이 되나 객관적으로 나올 확률은 굉장히 낮다고 볼 수 있습니다. 이 글 자체는 Group Theory의 기초부터 차근차근 설명을 할 예정이지만 만약 Group Theory에 대해 이전에 전혀 공부를 한 적이 없다면 안타깝게도 이론적 배경을 이해하는 것이 불가능에 가까울 것입니다. 대신 이론적 배경을 이해하지 않고 하단의 실제 문제에서 Burnside Lemma를 사용하는 예시만을 익혀두어도 괜찮습니다. 배경...
-
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...
-
2018 고려대학교 프로그래밍 경진대회 (KCPC) 출제 후기
이 포스트는 2018년 고려대학교 프로그래밍 경진대회 출제 과정에 있었던 일들과 대회의 지향점 및 결과 및 사견을 다룹니다. 원래 대회가 끝나고 바로 쓰고 싶었으나 대회 1주일 후가 기말고사이기도 했고 준비가 워낙에 힘들었기 때문에 한 달이 지난 지금 쓰게 되었습니다. 우선 본 대회를 성공적으로 마무리해주신 운영진과 출제진에게 감사하다는 말을 드리고 싶습니다. 또, 본 대회의 규모 확장에 필수불가결한 기여를 해주신 Startlink, sooho, wishket, NAVER D2, vcnc, 삼성 소프트웨어 멤버십, 고려대학교 정보대학 SW중심대학, 정보보호학부 및 정보보호대학원과 관계자 분들께 감사의...