구사과

A 단순 구현 문제. 물어보는게 복잡해서 약간의 전처리를 했다. 모든 자연수의 진약수의 합을 전처리하면 짧게 할 수 있었다. B 물어보는 게 모든 가방의 평균 중 몇 번째의 어쩌구 같은 아주 복잡한 무언가였다. 특히 가방의 개수가 많으면 사실상 관리가 불가능한 수치이다. 그런데 가방의 개수가 많으면 첫 번째 / 두 번째로 큰 가방만 남겨두고 나머지는 그냥 다 합쳐주면 된다. 그러니까 최적해에서 가방이 많지 않을 거라고 짐작할 수 있고 그 원리에 입각해서 생각하면 된다. 그런 식이었다. 더 정확하게는 기억이 나지 않는다 (...) $(K+1)/2$ 를 올림하고 내림하는 걸 헷갈려서 한번 틀렸다. C 애드혹 문제도 기출 패턴이 있고 웰노운이 있다. 이 문제 와 비슷하게 해결할 수 있다. D 재밌게 풀었다. ..

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

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시간 정도 안에 급하게 만든 거라 여백 등등에서 부족한 점이 많으니, 실제 팀노트 구성 시에는 수정이 필요할 수 있다.

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