leo020630의 블로그

오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: 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방향이 자신보다 크며, 후자의 경우는 잘 세어보면 항상 규칙을 만..

ABC랑 코포 Div.2를 쳤다. ABC 256 A. 2^N (0:00, +) *7 이건 좀.. B. Batters (0:03, +1) *83 하라는 대로 구현해주면 된다. 이상하게 읽었다가 한번 틀렸다. C. Filling 3x3 array (0:08, +) *541 좌상단 4개의 숫자만 정해주면 나머지는 모두 자동으로 정해진다. 따라서 $O(30^4)$에 문제를 해결할 수 있다. D. Union of Interval (0:11, +) *546 백준에 널린 스위핑 기본 문제 E. Takahashi's Anguish (0:18, +) *1224 Functional Graph 형태이니 그림을 그려주자. 일자 형태는 잘 배치할 수 있는데, 사이클 형태는 하나를 끊어서 일자로 만들어주어야 한다. 이 때, ..