leo020630의 블로그

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의 업솔빙을 빼면 랜덤 디펜스는 진행하지 않을 것 같다.

2일차 랜덤 디펜스이다. 2038 - 골롱 수열 지문이 이해가 되지 않아 약간 헤멨다. 수열의 특징을 파악한 후 최댓값이 크지 않을 것이라고 추측하면 맞을 수 있다. 20930 - 우주 정거장 KOI 개구리 점프의 2차원 버전이다. 그 문제에서 하는 것을 2번 해주면 된다. 13174 - 괄호 23799 - 리브 매칭 열심히 생각하다 집중도 잘 안 되고 문제도 어려워서 포기했다. 20188 - 등산 마니아 문제에서 요구하는 것을 잘 나누어 수식으로 표현하면 DFS 한 번으로 정답을 구할 수 있다. 분명 G2~D4 범위에서 돌렸는데, 어제 오늘 10문제 중 P4~P1이 단 하나도 나오지 않아 연습이 잘 되지 않았다. 내일부터는 범위를 P4~D5로 바꿀 예정이다.

종강을 했다. 시험기간에는 문제가 그렇게 풀고 싶었는데, 종강하자마자 의욕이 확 식길래 랜덤 디펜스를 시작하기로 했다. 범위는 G2~D4이며, 하루에 5문제씩 뽑아서 진행할 예정이다. https://www.acmicpc.net/group/14908에서 진행 중이니 제가 뭘 푸는지 구경하고 싶거나 같이 문제를 풀고 싶으신 분들은 언제든 환영입니다ㅎㅎ 오늘은 첫날이라 시간을 기록하지 않았는데, 다음부터는 시간도 잴 예정이다. 15678 - 연세워터파크 웰노운이라 짜서 맞았다. 최근 \(k\)개 항의 최대 또는 최소를 관리해야 하는 DP는 세그 또는 PQ 또는 덱을 사용해서 해결할 수 있음이 널리 알려져 있다. 2136 - 개미 이것도 웰노운이라 신나게 짜긴 했는데, 생각해보니 번호를 구하는 방법을 몰라서 시..

slah007 선배의 추천으로 풀게 된 문제이다. 푼지는 좀 됐는데, 시험기간 탓에 이제야 포스팅한다. 문제 요약 구간 \([L, R]\) 로 나타내어지는 선분 \(N\)개가 주어진다. 만약 두 선분이 겹칠 경우, 두 선분 사이의 거리를 1로 정의한다. \(A\)번 선분과 \(B\)번 선분의 거리를 구하는 쿼리를 \(Q\)번 처리하라. 풀이 일반성을 잃지 않고 두 선분이 겹치지 않으며 A가 B보다 앞에 있다고 가정하자. 당연하게도, B에 도달하기 위해서는 매 이동마다 가장 끝 좌표가 큰 선분으로 이동하는 것이 최적이다. 이렇게 같은 행동을 반복하는 문제는 DP, 그 중에서도 Sparse Table을 사용하면 해결할 수 있다. 다만, Sparse Table을 만들기 위해서 몇 가지 생각해야 할 부분이 존재..