leo020630의 블로그

엠바고가 풀리지 않아 설명이 불친절한 점 참고해주기 바랍니다. 예선 대회 중에 점수를 알려주지 않는 대회는 18년도 KOI 이후 굉장히 오랜만이었기 때문에 감회가 새로웠다. 아직 문제에 대해 자세한 후기를 쓰면 안되는 것 같아 설명은 생략하도록 하겠다. 나는 1, 2번에서 만점을 받고, 3번을 대부분 맞았다. 하지만 4번에서는 정확히 풀었으나 특정 issue로 대부분 틀리게 되었고, 5번은 대충 맞는 것 같은 풀이를 냈더니 대충 3분의 1 정도를 맞았다. 결과는 48등으로, 턱걸이로 본선에 진출할 수 있었다. 본선 완전하지는 않으나, 예선보다는 훨씬 나은 환경에서 본선을 진행하였다. 1번을 30분정도 걸려서 풀고, 2번도 비슷한 시간을 소모해서 풀었다. 그 후 3번과 4번을 봤는데, 3번은 예제를 이해할..

셋은 CERC 2019를 사용하였으며, 팀원 간 거리가 멀어 아쉽게도 연습은 3컴 체제로 진행하였다. 내가 뒤, slah007 선배가 가운데, qjatn0120 선배가 앞을 보고 시작했다. ~0:19 나는 I, qjatn0120 선배는 A, slah007 선배는 F를 잡고 시작했다. F의 AC가 13분에 먼저 나왔으며, 나는 할만해 보였던 I를 계속 잡아 19분에 AC를 띄웠다. ~0:30 이후 qjan0120 선배의 A AC가 나왔다. 나는 J를 잡았으며, slah007 선배는 E를 잡은 것 같다. ~0:41 J를 다 짜서 냈더니 틀렸다. 바로 반례가 있음을 깨닫고 성의 없는 커팅을 해서 냈는데 바로 맞았다. 정확한 이유는 몰랐지만 어쨌든 기분이 좋았다. 대회 끝나고 솔루션을 찾아보니 대충 제곱근 분할..

굉장히 오랜만에 CP 카테고리에 글을 쓴다. 오늘의 PS와 경계가 모호해진 것 같긴 하지만, 오늘은 이것 외에 문제풀이 활동을 하지 않아서 그냥 여기 적겠다. ABC 259 A. Growth Record (0:03, +) *34 평소 A번치고 헷갈려서 솔브가 약간 늦었다. 문제는 쉽다. B. Counterclockwise Rotation (0:08, +) *180 이런 걸 왜 내지? 잘 회전변환 해 주면 된다. C. XX to XXX (0:14, +1) *451 두 문자열을 묶음으로 본 후 잘 비교해주면 된다. 인덱싱 실수로 한번 틀렸다. D. Circumferences (0:22, +) *947 이런 걸 왜 내지? 2. 조건에 따라 원들이 겹친다면 Union Find로 묶어주면 된다. E. LCM on..

13:00~15:30 모비스 본선 16:30~18:30? 천코대 오픈콘 23:35~01:35 에듀코포 를 쳤다. 모비스 대회에 대한 후기는 생략하도록 하겠다. 제6회 천하제일 코딩대회 본선 Open Contest 2시간 늦게 참여하기도 했고 중간에 자리를 몇 번 비워서 진지한 마음으로 치지는 않았다. 아마 종료때까지라도 했으면 F는 풀었을 것 같다. A. Gravity Hackenbush 지문 낚시 문제이다. 각 플레이어가 초록색 간선을 최대한 많이 쓰는 것이 최적이므로 이를 토대로 비교해주면 된다. C. Merge the Tree and Sequence Split the SSHS 문제와 세팅이 비슷하다. 간선을 묶는 것은 그때와 같이 하면 되고, 남은 부분은 간선을 묶는 것에 비하면 크게 어렵지 않다...

열심히 올리던 오늘의 PS 글을 이번 주에는 쉬었다. 물론 그 동안 문제를 풀지 않은 것은 아니다. 열심히 풀었지만, 푼 문제들의 대다수가 새로운 알고리즘 학습 용도의 기본 문제들이거나 풀이를 대강 알고 있던 문제들이라서 글을 써도 쓸 말이 없을 것 같아 쓰지 않았다. 이런 방식이 마냥 좋다고 생각하지는 않지만, 대회 시즌이기 때문에 하나라도 더 아는 것이 중요하다 생각해서 이것저것 배워보았다. 그 덕에, 티어는 정말 쭉쭉 올랐다. 덕분에 1주일만에 레이팅 50을 올리면서 solved.ac 티어를 D2로 높일 수 있었다. D2로 올려준 문제는 Slope Trick 튜토리얼으로 유명한 13323,13324 BOJ 수열 1,2 이다. 추가로, 내가 속한 대학의 랭킹 1등 분, 고등학교의 랭킹 2등 친구가 모..

우리 팀 "내 이름은 무면허 라이더 김범수 나로 말할 것 같으면" 은 9솔브, 페널티 780분으로 12위를 차지하였다. 팀명은 해당하는 팀원분이 카톡을 읽지 않아 저렇게 결정되었다. 팀명에 대한 불만이 많으신 것 같지만, 적어도 나는 스코어보드 첫 페이지에 저 팀명을 올릴 수 있게 되어서 좋다. 결과에 대한 회고는 뒤에서 하고, 우선 시간 별 진행 상황을 정리해보도록 하겠다. 문제 배분은 코포 레이팅 순대로 qjatn0120 선배가 앞 4문제, 내가 가운데 3문제, slah007 선배가 마지막 3문제를 보기로 했다. ~0:03 A 2분 안에 못풀면 벌금이라느니... 팀명을 첫 페이지에 올려야 한다느니.. 같은 이상한 소리를 하다 대회가 시작되었다. 서버 이슈로 인해 접속이 약간 지연되었다. qjatn01..

셋은 SUAPC 2021s을 사용하였으며, 지난 주와 마찬가지로 3시간 3컴으로 진행하였다. 오전에는 모비스 대회도 쳤지만, 민형사상 처벌이 무섭기 때문에 생략하도록 하겠다. 내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다. ~0:09 뒤 네 문제를 스윽 봤을 때, 쉬워보이는 문제가 없었다. 뭘 잡을지 고민하던 중 A와 F의 AC가 나왔다. ~0:12 이후 slah007 선배가 D가 쉽다 해 가서 풀었다. 세팅이 지난 셋에 있던 문제와 같아 빨리 풀이가 나왔던 것 같다. ~0:23 이후 뒤 문제들 중 그나마 쉬운 K를 잡았다. 쉬운 문제는 아니었지만, 앳코더에서 본 적이 있었던 문제라서 풀이를 빨리 찾을 수 있었다. 바로 짜서 AC ~0:35 이후 C와 E의 AC가 ..

오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: https://www.acmicpc.net/category/detail/2355 2020 Sogang Programming Contest (Master) www.acmicpc.net 순서를 섞었기 때문에 실제 대회 번호와는 차이가 있다. 우선은 내가 푼 순서대로 정리할 예정이다. 20300 - 서강근육맨 (실제 대회 B, 위 스코어보드에서는 C) A, B가 바로 풀 문제는 아닌 것 같아 C를 잡았다. 짝수일 때는 정렬해준 후 맨 앞과 맨 뒤를 차례대로 매칭해주면 되는데, 홀수일 때는 잘 생각이 나지 않는다. 친절하게도, 제곱 풀이가 가..

어제는 노느라 문제를 풀지 못했다. 오늘은 플레 랜덤 문제를 몇 개 풀었다. 20670 - 미스테리 싸인 볼록다각형 이분탐색 문제를 연습하고 싶어 풀었다. 다각형을 위 아래로 나누는 방법과 각도로 나누는 방법 두 가지가 있는 것 같다. 이거 말고 접선 긋는 문제도 있는데, 한번 연습해 볼 계획이다. 18373 - N!!!...! mod P K가 크면 답이 0이 될 것이라고 추측할 수 있다. 그러면 경우의 수가 몇개 남지 않는데, 이를 열심히 짜주면 시간 초과를 받는다. (12!~=5e8)!을 구하는 게 1초 안에 돌아가지 않는 것 같다. 도저히 모르겠어서 열심히 풀이를 찾았는데, FFT를 쓰는 어려운 풀이와 윌슨 정리라는 걸 쓰는 풀이가 있었다. 티어를 봐선 FFT는 절대 아닌 것 같아서 윌슨 정리를 공..

오늘의 랜덤 검색 태그는 아래와 같았다. 변태라고 생각할 수도 있지만, 그게 아니라 내가 약하다고 생각한 분야를 모았더니 저렇게 됐다. 공평하게 각 태그에서 하나씩 골라서 풀었다. 18862 - 이제 다시 시작이다 기하인 척 하는 자료구조 문제이다. 식 정리를 열심히 하면 넓이를 4가지 경우에 따라 이차함수 꼴으로 계산할 수 있다. 다행히도 좌표의 범위가 주어져 있으니, seg[a]를 \(ex,ey\)와의 거리가 \(a\)인 스피커의 개수로 정의하자. 이러면 4가지 경우의 범위를 잘 나눠준 후 1, \(a\), \(a^2\)의 누적합을 저장하는 펜윅 트리로 답을 구해줄 수 있다. 11406 - 책 구매하기 2 플로우 기본 문제이다. 2814 - 최소인수 기본적인 풀이는 1557번 등과 비슷하다. 이분 탐..