leo020630의 블로그

셋은 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번 등과 비슷하다. 이분 탐..

xx00 솔브가 될 때마다 적는 일기 글이다. 히스토리를 보니, 대략 1달에 100문제 정도를 꾸준히 푼 것 같다. 1300번째 문제를 뭘로 할까 둘러보던 중, 2018+2021 PPC를 다 풀면 딱 1300문제이길래 다 밀었다. 1300번째 문제는 PPC 2021의 보스 문제이자 Hyperbolic님이 출제한 Black Friday가 되었다. 나이브로 뚫린다는 소리를 들었지만 그렇게는 짜기 싫었고, 정해는 솔직히 너무 어려워서+풀이를 들었기 때문에 대충 알고 있었어서 풀이를 까고 풀었다. 그런데도 꽤 생각해야 할 부분이 있었던 것 같다. 2018 & 2019년도 PPC는 마땅한 에디토리얼이 없는 것 같아 2019년 문제들까지 다 밀고 나면 블로그에 풀이를 작성할 예정이다. 언제가 될지는 모르겠다ㅎㅎ 올..

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

셋은 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이 쉽지 않다는 것을 깨닫..

문제 풀이를 랜덤 디펜스에서 랜덤 + 그때그때 공부하고싶은 주제 기본 문제들로 바꿨다. 따라서 하루로는 글 쓸 거리가 좀 없을 수 있어서 이틀동안 푼 문제들에 대해 요약을 해 보려 한다. 13159 - 배열 3444 - Robotic Sort 어제는 스플레이 트리를 구현해보았다. 구현 자체가 크게 어려운 것 같지는 않은데 (명성에 비해), 이런걸 생각해낸 발상이 진짜 대단한 것 같다. 13209 - 검역소 이 문제와 아래 문제는 slah007 선배가 풀길래 따라 풀었다. 우선 파라메트릭을 박고 싶게 생겼으니 박은 후 생각하면, 나눌 간선을 DFS를 돌며 그리디하게 구해줄 수 있다. 이 때 정렬이 필요하기 때문에 전체 시간복잡도는 \(O(Nlog^2N)\) 정도가 된다. 15756 - Disruption ..

랜덤 디펜스를 다시 시작한다. 범위는 동아리 부원들도 같이 하라고 G3~P2정도로 내렸는데, 일단 오늘은 나밖에 안하긴 했다. 16724 - 피리 부는 사나이 Functional Graph에서 사이클의 개수를 구하면 된다. 며칠 전에 앳코더에 비슷한 문제가 나와서 구현도 어렵지 않게 할 수 있었다. 2632 - 피자판매 각 피자에서 \(O(N^2)\)개의 합을 누적합을 통해 뽑아준 후, 이분 탐색으로 만족하는 쌍의 개수를 찾을 수 있다. 시간 복잡도는 \(O(N^2logN)\)이다. 23089 - 사탕나무 내 풀이는 정해보다 살짝 어려운 것 같다. \(DP[x][k]\)를 \(x\)번 노드의 자손들 중 \(k\)만큼 떨어진 노드들의 개수로 정의하자. 이는 DFS를 하는 과정에서 최근 내 \(k\)개의 조..

ARC랑 코포 Div.2를 쳤다. ARC 142 글로는 먼저 적었지만, 앞선 코포로 인해 멘탈이 별로였기에 제출을 막 했더니 페널티가 망했다. A. Reverse and Minimize (0:08, +4) *552 문제 지문을 잘 읽고 여러 예외 상황들을 고려한 뒤 코딩을 시작하면 어렵지 않게 구현할 수 있다. 나는 예외처리같은거 없이 막 냈다가 4번 틀렸다. B. Unbalanced Squares (0:17, +1) *692 아이디어 원툴 Constructive 문제이다. 많은 방법이 있겠지만, 내 방법은 x좌표와 y좌표가 모두 짝수인 곳부터 차례대로 숫자를 채운 뒤, 남은 숫자를 모두 채우는 것이다. 이러면 전자의 경우는 무조건 인접 8방향이 자신보다 크며, 후자의 경우는 잘 세어보면 항상 규칙을 만..