구사과

IOI 2022 Day 1 대회가 종료되었다. 올해 대회의 개최지는 인도네시아에서 진행하며, 온라인 대회 역시 병행한다. 한국 팀은 온라인 참가를 결정하였기 때문에, 현재 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 장태환, 100 / 53 / 58, 211점, 27등 반딧불, 53 / 80 / 58, 191점, 37등 조영욱, 67 / 51.5 / 58, 176.5점, 44등 박상훈, 70 / 72 / 27, 169점, 50등 예년과 대비했을 때 성적은 대략 평이한 수준이고, 학생들의 점수대는 그렇게 높지도 않지만 금메달을 받기 힘들 정도로 점수가 벌어진 학생도 없다. 보통 한국 학생들의 성적이..

(2020/09/24 23:47 - 원문 작성) (2020/09/29 01:20 - 4번 문제 풀이를 추가했다.) (2022/08/02 02:13 - 5번 문제의 100점 풀이를 추가했다.) IOI 2020 Day 2 대회가 종료되었다. 한국 학생들의 최종 성적은 다음과 같다. 최은수, 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등 (은메달) 올해 ..

UCPC 2022에 사용했던 팀노트를 첨부한다. 기본적으로 예전 더불어민규당 팀노트를 기반으로 만들었는데, 당시랑 내가 지금 사용하는 코드베이스가 많이 달라서 내용은 꽤 많이 다른 것 같다. 당시에는 landscape 2-side로 만들어도 25장이 다 안 차서, 여백을 두더라도 가독성을 높이는 식으로 팀노트를 만들었는데. 이번에 저렇게 만드니까 50장이 넘게 나와서 도저히 진행할 수가 없었고, portrait / 2-side / 7pt 로 엄청나게 압축해서 넣었다. 2시간 정도 안에 급하게 만든 거라 여백 등등에서 부족한 점이 많으니, 실제 팀노트 구성 시에는 수정이 필요할 수 있다.

상위권 팀에 대해서 아는 정도만 적으면 초비상!!: koosaga, tlwpdus, khsoo01 우리가 우승할 수 있을 리 없잖아, 무리무리!: UCPC 2021 디펜딩 챔피언, 2020/2021 서울 리저널 챔피언 FSM (서울대, WF 규정에 따라서 올해 리저널 출전 가능할 수 있음) BabyPenguin: 2021 서울 리저널 BabyPenguin (KAIST, 올해 리저널 출전 가능) 🐟🐚🦂: cubelover, alex9801, kajebiii UCPC의 최신 동향: arnold518, karuna, blackking26 (서울대, 올해 리저널 출전 가능) DM 확인 부탁드립니다! 🙏: 2019/2020 서울 리저널 Ternion aHR0cDovL2Vyci5vLXIua3Iv: Lawali, l..

PA 2012. Mecze 두 선수가 경쟁하지 않았다는 것은, 두 선수가 항상 같은 팀에 있었다는 것과 동치입니다. 고로 각 선수가 무슨 팀에 있었는지를 크기 $M$ 의 배열에 저장하고, 배열들을 정렬한 후 중복 원소가 있는지를 체크하면 됩니다. 배열을 정렬하기 위해서는 배열간 비교가 가능한 vector 같은 자료형을 쓰거나 $M \le 50$ 이니 배열 대신 long long 자료형에 비트마스크로 저장하거나 등등의 방법이 있습니다. Petrozavodsk Winter 2022 Day 1 - Kyoto U Contest. Build The Grid 사진으로 대체합니다: 이러한 구성을 찾는 방법은 여러 가지가 있습니다. 저의 경우에는 그냥 백트래킹을 돌려서 조건을 만족하는 그리드를 찍어보고, 규칙을 찾았습..

(2023.10.20 - Def2->Def3 증명의 오류를 수정하고 Typesetting을 좀 손봤다.) 알고리즘에서 다루는 많은 문제들은 그래프 문제로 환원할 수 있는데, 일반적인 그래프에서 어떤 문제들은 효율적으로 해결이 불가능한 경우가 있다. 이러한 비효율성의 대표적인 예시는 NP-hard로, 어떠한 문제가 NP-hard일 경우 다항 시간으로 푸는 것이 아예 불가능할 가능성이 높다. 그 외에도, 최단 경로 문제와 같이 다양한 쿼리에 대해서 빠른 시간 안에 해결하는 것이 어려운 경우 등, 비효율성의 예시는 NP-hard에 한정되지 않는다. 이러한 비효율성에 당착했을 때 자주 취하는 전략은 환원한 그래프의 특수성에 의존하는 것이다. 예를 들어, NP-hard 문제들이라 하더라도 그래프가 직선, 트리, ..

82등으로 본선 진출 실패했습니다. ucpc 예선 1등해서 기분 좋았는데 느슨했던 멘탈에 긴장감을.. 5번 이러면 될 거 같은데..? 옛날에 민컷 이야기라는 글도 썼고 나름 컷 문제는 잘 푼다고 생각했는데 아닌가.. 디닉도 팀노트 없이 짤 수 있는데... i -> j 로 가는 간선이 있으면 source -> i로 가중치 b의 유향 간선 잇고 i -> sink로 가중치 a의 유향 간선 잇고 i -> j로 가중치 c - a의 유향 간선 잇고 j -> i로 가중치 c - b의 유향 간선 잇고 그러면 (i, j) 가 모두 source쪽에 있으면 (주거) a의 비용 (i, j) 가 모두 sink쪽에 있으면 (업무) b의 비용 i가 source, j가 sink쪽에 있으면 (c-a) + a = c의 비용 i가 sin..

(6/23 01:20: 7월 과외 마감하였습니다. 많은 성원에 진심으로 감사드립니다.) 안녕하세요. 구재현입니다. 학교 복학을 위해서 최근에 회사를 그만 두었는데, 2달 정도 여유 시간이 있어서 그동안 알고리즘 과외를 진행해 볼까 합니다. 프로필 글 작성 시간 기준으로 변동이 있을 수 있습니다. BOJ: koosaga (Rank 1, 11310 solved) solved.ac: koosaga (Rank 1, Master, 3255) Codeforces: ko_osaga (World Rank 13. Korea Rank 1, Legendary Grandmaster, 3315) Google Code Jam World Finals 2회 출전 (2021, 2020) Facebook Hacker Cup World ..

https://epubs.siam.org/doi/epdf/10.1137/1.9781611973099.139 Andreas Bjorklund는 그래프 이론에 대수적 방법을 접목시켜서 50년짜리 SOTA를 여럿 깬 것으로 유명하다. 최근에 논문 중 하나를 읽어볼 기회가 생겼는데 생각보다 훨씬 elementary한 방법이라서 놀랐다. 간단하게 요약하면 좋을 것 같아서 짧은 노트를 써 본다. 문제는 "그래프가 있고 K개의 정점이 마크되어 있을 때 이 정점들을 모두 지나는 최소 길이 simple cycle을 찾는 문제" 이고, 시간 복잡도 aim은 $O(2^k poly(N))$ 이다. 풀이는 다음과 같다. 먼저 찾을 사이클의 시작점을 $k$ 개 중 하나로 고정하자. 다음과 같은 walk $w = \{s, v_1,..