구사과

이 글에서는 Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams의 Conditional Hardness for Sensitivity Problems 라는 논문을 요약한다. 이론 전산에서 Dynamic algorithm은, 입력 데이터에 작은 변화가 점진적으로 가해지더라도 데이터에 대해 물어볼 수 있는 특정한 문제들의 답을 그대로 보존하는 알고리즘을 뜻한다. 예를 들어서, 그래프의 "연결성" (connectivity) 를 보존하는 dynamic algorithm은 입력 그래프에 간선 추가와 제거가 이루어질 때 $s - t$ 간에 경로가 있는지 여부의 쿼리를 반환할 수 있다. 최근 이루어진 여러 연구를 통해서 Dyna..

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 ..

근사 알고리즘(Approximation algorithm)은, 문제에 대한 최적해를 제공하지는 못하나, 최적해에 근접한 해(근사해)를 빠른 시간에 찾는 알고리즘이다. NP-Complete인 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없는데, 이러한 문제를 회피하는 여러 방법 중 가장 많이 연구되는 방법 중 하나가 근사 알고리즘이다. 근사 알고리즘의 목표는, 최적해에 근접함이 보장된 해를 다항 시간에 찾는 것이며, 가능하다면 그 보장의 정도를 최대한으로 끌어오는 것이다. 모든 문제가 근사 알고리즘으로 쉽게 해결되었으면 정말 좋았겠지만 당연히 세상 일이 그렇게 되지는 않는다. 어떠한 문제들은 $P \neq NP$ 인 이상 최적해를 다항 시간에 구할 수 없을 뿐만 아니라, 근사 알고..

2015년 정도부터 vim에서 코딩을 해 왔으니 vim만 한 7년 정도 써왔다. vim을 사용하는 이유는 웬만한 환경에서는 사용할 수가 있고 (IOI에서 사용할 수 있는 개발 도구가 그렇게 많지 않다), 설정 난이도가 낮고, 버그가 없어서이다. 요즘 내가 참가하는 대회는 SCPC를 빼면 다 내 컴퓨터로 개발이 되는 편이고, SCPC는 윈도우 환경이라 vim을 지원하지 않는다. 개발 환경이나 도구 설정에 시간 쓰는걸 정말 싫어해서 딱히 바꿀 생각은 안 했는데, 최근 linter가 있으면 좋을 것 같다는 생각이 들어서 VS Code를 설치해서 사용하고 있다. 초기 설정에 시간이 좀 들어서, 기록용으로 환경설정법을 메모해 둔다. 확장 프로그램 * C/C++ * C/C++ Extension Pack * C/C+..

라이브 영상을 찾아보다가 건졌는데, 세션 자체가 앨범으로 올라와 있었다. 마무리 베이스라인이 정말 좋았는데, 분명히 내가 알고 있는 노래인 것 같았는데 무엇인지는 결국 기억해내지 못하고 댓글을 보고 알았다. 사실 그렇게 자주 듣는 노래는 아니었는데 그렇게 따로 떼어놓고 보니 완전히 새롭게 들렸다. 영국적임을 그렇게 강조하던 밴드의 음악적 조상이 무엇인지 다시 생각해 보게 된 기회. 같은 앨범에서 커버했던 곡. 와이즈 블러드는 처음 들었을 때 감정에 친 파도가 너무 커서, "한동안은 다시 못 듣겠다" 라는 생각이 들 정도로 인상깊은 아티스트였다. 곧 신보가 나올 것 같던데 크게 기대된다. 그 외 재밌게 들은 것.

Codeforces에 올린 글을 보관 목적으로 블로그에도 올립니다. 한글 번역 계획은 없습니다. I recently solved some problems that involved the concept of Lyndon decomposition. Honestly, most of them were too hard to understand for me. I'm just trying to think out loud about things I've read, so I can learn ideas or better takes from smarter people? Note that I will omit almost all proofs as I can't do that. I believe all unproven cla..

IOI 2022 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 장태환, 100 / 53 / 58 / 100 / 93.05 / 55, 459.05점, 22등 (금메달) 조영욱, 67 / 51.5 / 58 / 100 / 99.78 / 55, 431.28점, 26등 (금메달) 반딧불, 53 / 80 / 58 / 34 / 100 / 55, 380.00점, 38등 (은메달) 박상훈, 70 / 72 / 27 / 34 / 96.10 / 55, 354.10점, 42등 (은메달) 한국 학생들은 금메달 2개, 은메달 2개로 평균 이상의 성적을 거두었다. 전반적으로 금메달 컷 근처에서 점수가 형성되어 있어서, 조금만 잘 했으면 하는 아쉬움이 남기도 한다. 장태환 학생은 작년 첫 출전에서 동메달을 땄..