qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

2022년부터 IOI 금메달을 받은 학생들을 대상으로 캠프를 진행했는데, 그동안 일정이 되지 않아서 참석하지 못했다. 24년 캠프는 2025년 1월 19일부터 24일까지 홍콩에서 진행됐고, 22-24년 금메달을 초청했다. 대한민국에서는 나랑 이동현, 조영욱 셋이서 참가하게 되었다. IOI 금메달 외에도 EGOI 금메달과 HKOI 금메달을 추가로 초청해서 코치 포함 50명 정도가 참가했다.Day 1 (1/19)아침 9시 비행기를 타고 홍콩으로 갔다. 6시 반에 공항에 도착했는데, 기내에 들고 가도 되는 작은 캐리어를 굳이 수하물로 부치겠다고 줄을 서다가 8시에 겨우 짐을 부치고 8시 50분쯤에 비행기를 탈 수 있었다. 출국장에서 계속 딜레이가 발생해서 새치기할지 백 번 정도 고민하다가 안 했다. 홍콩에 도..

올해 고등학교 3학년을 마치고 내년에 대학교에 입학하게 되었다. 21년부터 23년까지는 거의 모든 시간을 PS에 쏟아부었지만 올해는 PS 말고도 꽤 다양한 일이 있었던 것 같아서 회고록을 간단하게 적어보고자 한다.PS올해는 PS를 많이 하지 않았다. KOI와 선발고사를 응시하지 않았고, NYPC는 나이제한에 걸려서 참가하지 못했다. 작년 IOI가 끝나고 나서부터 PS를 일시적으로 접기로 결심했고 그 이유는 크게 다음과 같다: 1. PS가 좀 재미없어졌다. 예전에는 문제 풀고 코드 짜는 게 되게 재밌었는데, 대회를 잘 쳐야 한다는 압박이 꽤 심해져서 부담이 많이 됐다. 특히 23년 IOI 때 거의 망할 뻔했다가 겨우 살아나서 그 이후로 대회 치는 게 좀 무섭게 느껴졌다.2. 고등학교 3학년이라서 입시에 집..

https://deepmind.google/discover/blog/alphageometry-an-olympiad-level-ai-system-for-geometry/ AlphaGeometry: An Olympiad-level AI system for geometry Our AI system surpasses the state-of-the-art approach for geometry problems, advancing AI reasoning in mathematics deepmind.google 최근 구글 딥마인드에서 mo 기하 문제를 푸는 AI를 발표했다길래 궁금해져서 직접 설치하고 실행해봤다. https://github.com/google-deepmind/alphageometry 에서 설치할 수 있..

8/28 ~ 9/4에 헝가리에서 열린 IOI 2023에 한국 국가대표로 참가했다. 한국 팀 멤버는 박상훈(qwerasdfzxcl), 반딧불(79brue), 이동현(lisifu/kizen), 이성호(puppy/windva)였고, 작년에 비해 꽤 강한 멤버였기 때문에 4금을 노려볼만하다고 생각했다. 나와 동현이는 금메달을 받았고, 딧불이와 성호는 은메달을 받으면서 2금2은의 성적을 기록했고, 국가 순위 5등을 했다. 작년에도 IOI에 참가했지만 코로나 이슈로 온라인으로 참가하게 되어서 대회만 치고 끝났는데, 올해는 오프라인으로 직접 헝가리도 가고 여러 행사나 관광을 즐길 수 있어서 매우 좋았다. 솔직히 말하자면 관광은 별 거 없어서 재미없었고 공통 관심사를 가진 외국인 친구들을 많이 만날 수 있었던 것이 너..

CEOI 2016을 돌았다. 0:00 ~ 1:47 1번과 2번을 읽었다. 1번은 나이브가 쉽고 풀태는 바로 안 떠올라서 2번을 읽고 풀었다. 나이브랑 풀태 모두 자꾸 틀려서 시간을 많이 날렸다. 처음에 dnc opt 풀이랑 덱dp 풀이를 내서 둘다 짰는데 둘다 틀린 풀이였다. 100점 받으려면 대충 비트스트링 들고 다니면서 적당히 dp 돌려주면 O(NTS)에 문제를 해결할 수 있다. 1:47 ~ 3:34 3번을 읽었다. input 노드 루트개 / output 노드 루트개 연결하는 노드들을 만들고 연결하면 47점을 받을 수 있다. 100점을 받으려면 이를 다중으로 해주면 된다. i번째 층의 노드는 input 노드 P^(i/k)개, output 노드 P^((k-i)/k)개를 연결하는 노드라고 놓으면 추가 노..

BOI 2022 Day 1을 돌았다. 0:00 ~ 0:17 1번 문제를 읽었다. 순열을 쿼리로 날리면 inversion 개수를 알 수 있을 때 N번 이하의 쿼리로 원래 순열을 복원해야한다. 순열을 N번 rotate하면서 넣으면 각 원소의 등수를 알 수 있기 때문에 쉽게 풀린다. 0:17 ~ 1:05 2번 문제를 읽었다. 섭태 풀이가 대부분 쉬웠고 100점 풀이도 쉬울 것 같아서 조금 고민해보기로 했다. 시작에서 끝으로 가는건 최적화하기 까다로워서 거꾸로 끝에서 시작으로 가는 방식을 생각해봤고 문제가 더 간단해졌다. 스파스테이블을 이용한 100점 풀이를 바로 짰고 AC를 받았다. 1:05 ~ 3:52 3번 문제를 읽었다. 가중치가 -M이상 M이하의 정수로 bound되어있을 때 M에 대한 다항시간으로 냅색을..

ROI18에서 4문제 뽑아서 5시간동안 돌았다. 1. Decryption 2. Quick sort 3. Quantum teleportation 4. Addition without carry 0:00 ~ 0:14 1번 읽고 바로 짜서 맞았다. 0:14 ~ 1:52 234번을 읽고 3번을 고민했다. 대충 다익스트라를 이용한 세제곱/64 풀이랑 제곱로그/64 풀이를 냈다. 일단 나이브인 세제곱/64를 짜고 디버깅을 했더니 67점이 긁혔다. 제곱로그/64를 짜고 100점을 받을까 생각해봤지만 x좌표나 y좌표 같은 점이 있으면 안 되는 풀이라는걸 깨닫고 그냥 넘어갔다. 1:52 ~ 2:07 4번은 섭태가 너무 많아서 일단 2번 버블소트로 50점을 긁었다. 2:07 ~ 2:54 2번을 좀 더 고민하니 대충 로그복잡..

USACO 23 us open 골드 123번 / 플래 13번으로 구성된 5문제 셋을 5시간 동안 돌았다. 문제 번호는 순서대로 붙어있다. 0:00 ~ 1:00 초반 1시간에는 문제를 다 읽고 바로 풀이가 보이는걸 짜려고 했다. 근데 풀이가 명확히 보이는건 없어서 일단 1번을 생각해봤다. 키를 배치하는 전략을 찾는 것은 어려울 것 같아서 다른 방향으로 생각해보다가 거꾸로 돌리면 되지 않을까 라는 생각을 하게 되었다. 그 아이디어가 핵심이었고 정방향 / 역방향 탐색을 해주면 문제가 쉽게 풀린다. 1:00 ~ 1:30 2번을 고민했다. 2번과 4번이 컨셉이 같은 문제인데 2번이 요구하는게 적어서 더 쉬울 것 같았다. 조금 고민하니까 2번 풀이가 나왔고 금방 짜서 맞았다. dp를 잘 돌리면 된다. 1:30 ~ ..