구사과

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

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

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

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개로 평균 이상의 성적을 거두었다. 전반적으로 금메달 컷 근처에서 점수가 형성되어 있어서, 조금만 잘 했으면 하는 아쉬움이 남기도 한다. 장태환 학생은 작년 첫 출전에서 동메달을 땄..

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 사진으로 대체합니다: 이러한 구성을 찾는 방법은 여러 가지가 있습니다. 저의 경우에는 그냥 백트래킹을 돌려서 조건을 만족하는 그리드를 찍어보고, 규칙을 찾았습..