leo020630의 블로그

오늘의 랜덤 검색 태그는 아래와 같았다. 변태라고 생각할 수도 있지만, 그게 아니라 내가 약하다고 생각한 분야를 모았더니 저렇게 됐다. 공평하게 각 태그에서 하나씩 골라서 풀었다. 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 형태이니 그림을 그려주자. 일자 형태는 잘 배치할 수 있는데, 사이클 형태는 하나를 끊어서 일자로 만들어주어야 한다. 이 때, ..

화~수는 조별 과제 + 귀가 때문에 랜덤 디펜스를 하지 못했고, 어제는 문제를 뽑았더니 코포가 얼마 남지 않았길래 하나만 풀고 코포하러 갔다. 코포는 대차게 망했다. 전혀 틀린 점이 없는 코드들이 틀리길래 억울해 하던 중, 대회 시작 1시간 후 이런 걸 발견했다. 원래 long long으로 고정해 두는데, 백준 풀면서 바꾼걸 까먹었던 것이다. 이후 1시간동안 C를 푸려고 노력해보았으나 잘 되지 않았고, 그대로 퍼플로 향했다. 16~17일에 랜플디로 고른 문제들은 아래와 같다. 5480 - 전함 온라인으로 해결하는 것은 어려워 보이니, 오프라인으로 해결하는 방법을 떠올려보자. 2차원일 때와 1차원일 때의 풀이 방법이 크게 다르지 않으므로 1차원이라고 가정하자. 이 때, 한 가지 관찰이 필요하다. : 나를 ..

3일차 랜덤 디펜스이다. 범위는 P4~D5이다. 14286 - 간선 끊어가기 2 1824 - 도미노 1310 - 달리기 코스 각 문제의 지문을 읽고 그에 맞는 알고리즘을 코딩해주면 된다. 2244 - 민코프스키 합 정의에 의해 생기는 \(NM\)개의 점으로 컨벡스 헐을 구해주면 된다. 14179 - 크리스마스 이브 할 게 많아서 풀지 못했다. 업솔빙 예정 셋이 지나치게 알고리즘 연습문제들만 나와서 그닥 재미있지는 않았다. 내일은 조별과제를 해야 해서 아마 14179의 업솔빙을 빼면 랜덤 디펜스는 진행하지 않을 것 같다.