본문 바로가기

전체 글

(84)
2022 UCPC 예선 후기 우리 팀 "내 이름은 무면허 라이더 김범수 나로 말할 것 같으면" 은 9솔브, 페널티 780분으로 12위를 차지하였다. 팀명은 해당하는 팀원분이 카톡을 읽지 않아 저렇게 결정되었다. 팀명에 대한 불만이 많으신 것 같지만, 적어도 나는 스코어보드 첫 페이지에 저 팀명을 올릴 수 있게 되어서 좋다. 결과에 대한 회고는 뒤에서 하고, 우선 시간 별 진행 상황을 정리해보도록 하겠다. 문제 배분은 코포 레이팅 순대로 qjatn0120 선배가 앞 4문제, 내가 가운데 3문제, slah007 선배가 마지막 3문제를 보기로 했다. ~0:03 A 2분 안에 못풀면 벌금이라느니... 팀명을 첫 페이지에 올려야 한다느니.. 같은 이상한 소리를 하다 대회가 시작되었다. 서버 이슈로 인해 접속이 약간 지연되었다. qjatn01..
220701 팀 연습 셋은 SUAPC 2021s을 사용하였으며, 지난 주와 마찬가지로 3시간 3컴으로 진행하였다. 오전에는 모비스 대회도 쳤지만, 민형사상 처벌이 무섭기 때문에 생략하도록 하겠다. 내가 뒤, slah007 선배가 앞, qjatn0120 선배가 가운데를 보고 시작했다. ~0:09 뒤 네 문제를 스윽 봤을 때, 쉬워보이는 문제가 없었다. 뭘 잡을지 고민하던 중 A와 F의 AC가 나왔다. ~0:12 이후 slah007 선배가 D가 쉽다 해 가서 풀었다. 세팅이 지난 셋에 있던 문제와 같아 빨리 풀이가 나왔던 것 같다. ~0:23 이후 뒤 문제들 중 그나마 쉬운 K를 잡았다. 쉬운 문제는 아니었지만, 앳코더에서 본 적이 있었던 문제라서 풀이를 빨리 찾을 수 있었다. 바로 짜서 AC ~0:35 이후 C와 E의 AC가 ..
오늘의 PS (19) - 220630 오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: https://www.acmicpc.net/category/detail/2355 2020 Sogang Programming Contest (Master) www.acmicpc.net 순서를 섞었기 때문에 실제 대회 번호와는 차이가 있다. 우선은 내가 푼 순서대로 정리할 예정이다. 20300 - 서강근육맨 (실제 대회 B, 위 스코어보드에서는 C) A, B가 바로 풀 문제는 아닌 것 같아 C를 잡았다. 짝수일 때는 정렬해준 후 맨 앞과 맨 뒤를 차례대로 매칭해주면 되는데, 홀수일 때는 잘 생각이 나지 않는다. 친절하게도, 제곱 풀이가 가..
오늘의 PS (18) - 220629 어제는 노느라 문제를 풀지 못했다. 오늘은 플레 랜덤 문제를 몇 개 풀었다. 20670 - 미스테리 싸인 볼록다각형 이분탐색 문제를 연습하고 싶어 풀었다. 다각형을 위 아래로 나누는 방법과 각도로 나누는 방법 두 가지가 있는 것 같다. 이거 말고 접선 긋는 문제도 있는데, 한번 연습해 볼 계획이다. 18373 - N!!!...! mod P K가 크면 답이 0이 될 것이라고 추측할 수 있다. 그러면 경우의 수가 몇개 남지 않는데, 이를 열심히 짜주면 시간 초과를 받는다. (12!~=5e8)!을 구하는 게 1초 안에 돌아가지 않는 것 같다. 도저히 모르겠어서 열심히 풀이를 찾았는데, FFT를 쓰는 어려운 풀이와 윌슨 정리라는 걸 쓰는 풀이가 있었다. 티어를 봐선 FFT는 절대 아닌 것 같아서 윌슨 정리를 공..
오늘의 PS (17) - 220627 오늘의 랜덤 검색 태그는 아래와 같았다. 변태라고 생각할 수도 있지만, 그게 아니라 내가 약하다고 생각한 분야를 모았더니 저렇게 됐다. 공평하게 각 태그에서 하나씩 골라서 풀었다. 18862 - 이제 다시 시작이다 기하인 척 하는 자료구조 문제이다. 식 정리를 열심히 하면 넓이를 4가지 경우에 따라 이차함수 꼴으로 계산할 수 있다. 다행히도 좌표의 범위가 주어져 있으니, seg[a]를 \(ex,ey\)와의 거리가 \(a\)인 스피커의 개수로 정의하자. 이러면 4가지 경우의 범위를 잘 나눠준 후 1, \(a\), \(a^2\)의 누적합을 저장하는 펜윅 트리로 답을 구해줄 수 있다. 11406 - 책 구매하기 2 플로우 기본 문제이다. 2814 - 최소인수 기본적인 풀이는 1557번 등과 비슷하다. 이분 탐..
BOJ 1300 Solve xx00 솔브가 될 때마다 적는 일기 글이다. 히스토리를 보니, 대략 1달에 100문제 정도를 꾸준히 푼 것 같다. 1300번째 문제를 뭘로 할까 둘러보던 중, 2018+2021 PPC를 다 풀면 딱 1300문제이길래 다 밀었다. 1300번째 문제는 PPC 2021의 보스 문제이자 Hyperbolic님이 출제한 Black Friday가 되었다. 나이브로 뚫린다는 소리를 들었지만 그렇게는 짜기 싫었고, 정해는 솔직히 너무 어려워서+풀이를 들었기 때문에 대충 알고 있었어서 풀이를 까고 풀었다. 그런데도 꽤 생각해야 할 부분이 있었던 것 같다. 2018 & 2019년도 PPC는 마땅한 에디토리얼이 없는 것 같아 2019년 문제들까지 다 밀고 나면 블로그에 풀이를 작성할 예정이다. 언제가 될지는 모르겠다ㅎㅎ 올..
오늘의 PS (16) - 220625 ABC랑 코포 글로벌 라운드를 쳤다. ABC 257 A. A to Z String 2 (0:01, +) *22 제한이 작아서 그냥 반복문으로 구현해줄 수 있다. B. 1D Pawn (0:03, +) *91 역시 그냥 반복문으로 구현해주면 된다. C. Robot Takahashi (0:07, +) *678 어른과 아이를 분류해서 정렬한 후, 각 값과 +-1을 대상으로 해 이분탐색으로 \(f(X)\)를 구해주면 된다. D. Jumping Takahashi 2 (0:15, +) *1203 시간을 이분탐색으로 구한다고 가정하면, 그래프를 만드는 데에 \(O(N^2)\), 각 노드를 시작점으로 BFS를 하는 데에 \(O(N^2)\)이 걸려 \(O(N^2logX)\)에 문제를 해결할 수 있다. E. Addition..
220624 팀 연습 셋은 SUAPC 2021w을 사용하였으며, 동아리의 다른 UCPC 출전 팀들과 함께 3시간동안 진행하였다. ~0:05 qjatn0120 선배가 앞쪽, 내가 뒤쪽, slah007 선배가 가운데를 보기로 하고 시작하였다. J~M을 본 나는 J를 일단 거르고 K가 쉽다는 것을 깨달아 짜서 맞았다. ~0:11 slah007 선배가 본인의 문제를 헷갈리는 해프닝이 있었지만, 쉬운 문제였던 B와 I를 qjatn0120 선배와 slah007선배가 각자 짜서 맞았다. ~0:19 이후 내가 L 풀이를 구상해 짜서 맞았다. qjatn0120 선배는 구현량이 많은 A를 잡았으며, slah007 선배는 H를 잡았다. ~0:24 H AC가 나왔다. slah007 선배는 F를 풀러 갔으며, 나는 J랑 M이 쉽지 않다는 것을 깨닫..