kth990303의 코딩 블로그

추천받은 문제 중 하나. 입력 범위가 상당히 크기 때문에 꽤나 어려워 보이지만, 오히려 그러한 점이 힌트가 되는 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/15816 15816번: 퀘스트 중인 모험가 첫째 줄에 지금까지 달성한 퀘스트의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄에 지금까지 달성한 퀘스트들의 번호 Q1 ... QN 까지의 N개의 수가 주어진다. (−1,000,000,000 ≤ Q[i] ≤ 1,000,000,000, Q www.acmicpc.net 의식의 흐름 및 해설 수의 범위가 굉장히 크기 때문에 O(N^2) 이상의 시간복잡도 풀이는 불가능하며, 입력받는 퀘스트 범위가 -10억 ~ 10억인 점, 요청으로 추가되는 퀘스트 개..

엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제. 이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다. 위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데, 이번 기회에 복습 겸 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmi..

괄호 문자열 시리즈 문제 중 하나이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 사실 괄호 문자열 문제가 시리즈로 있다는 것을 이 문제로 처음 알았다. 예전에 풀어본 9935번 문자열폭발 문제랑 비슷한 줄 알았는데, 생각해보니 그 문제는 괄호가 아니라 문자열 관련 문제였다. 괄호라고 해서 스택, 카탈란수가 생각나서 비슷하게 생각했나보다. 의식의 흐름 및 해설 처음에는 스택이나 카탈란 수를 떠올렸다. 그러..

UCPC 2021 본선 D번 문제이다. 본선은 정말 괴수들만 진출하는 곳이 맞긴 한가보다. UCPC 본선 중에서 가장 쉬운 문제들 중 하나라고 한다. https://www.acmicpc.net/problem/22876 22876번: 츠바메가에시 "츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재 www.acmicpc.net 처음에 이 문제에서 tree 배열의 범위를 잘못 생각하여 계속 맞왜틀을 하였다... 의식의 흐름 및 해설 / 테스트케이스 첨부 처음에는 단순히 매 순간의 최댓값 3번을 구하면 된다고 생각하여 세그먼트트리를 이용하여 구현하였다. 주의할 점은 좌표의 범위..

스코페를 치른 이후 LCA와 segtree를 연습하고 싶은 마음에 푼 문제이다. 문제는 다음과 같다. www.acmicpc.net/problem/17131 17131번: 여우가 정보섬에 올라온 이유 첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다. www.acmicpc.net 저번에 북서풍 문제, 화성지도 문제를 풀어서 세그먼트트리 with 스위핑 문제를 경험해서 그런지 이 문제 또한 아이디어 자체는 세그먼트트리가 잘 떠올랐다. 북서풍 문제랑 상당히 유사한 아이디어로 풀면 되지 않을까. 심지어 좌표압축을 할 필요조차 없다. 그런데... 난 이문제에서 엄청나게 많은 맞왜틀을 겪었다. (아직도 그 이유는 찾지 못했다. slack, 질문게시판에 물어봤음에도 불..