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

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

문제 풀이를 랜덤 디펜스에서 랜덤 + 그때그때 공부하고싶은 주제 기본 문제들로 바꿨다. 따라서 하루로는 글 쓸 거리가 좀 없을 수 있어서 이틀동안 푼 문제들에 대해 요약을 해 보려 한다. 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의 업솔빙을 빼면 랜덤 디펜스는 진행하지 않을 것 같다.