본문 바로가기

분류 전체보기

(17)
BOJ 7469 K번째 수 (in Q log N!) https://www.acmicpc.net/problem/7469 7469번: K번째 수 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. 현정 www.acmicpc.net Step 1 ($O(M \log^3 N)$) 이 단계는 머지 소트 트리를 알고 있다면 누구나 풀 수 있습니다. 머지 소트 트리는 일반적인 세그먼트 트리와 비슷한데, $[l, r]$ 구간을 담당하는 노드에는 $[l, r]$ 구간에 있는 수들을 정렬해서 배열 형태로 저장해 둔 세그먼트 트리를 말합니다. 머지 소트 트리의 구축은 모든 노드에 대해 정렬을 독립적으로 하면 $O(N \log^2 N)$에 가능합니..
IOI 2021 후기 이번 IOI에 한국 국가대표로 선발이 되어서, 본 대회를 치르게 되었습니다. 코로나19가 계속되는 바람에 올해도 싱가포르 현지에서 대회를 치르지 못하고 우리나라에서 온라인으로 치르게 된 점이 아쉽습니다. 작년에 이어 2년째 IOI에 참가하게 되었는데, 작년과는 느낌이 확연히 다른 대회였습니다. 작년과 다르게 올해는 주변 누구도 성적에 대한 기대를 가지지 않아서 편한 마음으로 시험을 볼 수 있었습니다. 아마 이러한 점도 성적에 영향을 주지 않았나 싶습니다. Day 0 (Practice Session) 연습 세션 문제는 작년과 거의 똑같았습니다. 차이점이 있다면, 무슨 이상한 전처리를 해야 맞는 문제 하나가 간단한 bfs 문제로 바뀌었습니다. 작년에 끝까지 풀지 못했던 문제(Jelly Flavours)를 이..
Problem Solving Diary #2 IOI 2015 Day 1. Teams 서브태스크 1, 2 (34점) $O(NQ)$로 풀 수 있는 경우 어떻게 쉽게 풀 수 있을까요? 그리디한 접근을 생각해 봅시다. 정원 수가 작은 프로젝트부터 보면, 현재 넣을 수 있는 사람들 중 $B_i$가 가장 작은 사람을 넣는 게 이득입니다. (나중에 가능성이 있는 사람을 남겨 둬야 하므로) 따라서 사람들을 $A_i$ 순서로 정렬하고 프로젝트를 정원 수에 따라 정렬한 뒤에, 힙을 사용하여 $B_i$가 작은 사람부터 뽑아내면 됩니다. 시간 복잡도는 $O(NQ \log N)$입니다. 더보기 #include #include "teams.h" using namespace std; typedef long long ll; int n; pair arr[500002]; void..
Problem Solving Diary #1 IOI 2020 Day 1. Comparing Plants 대회 때 멘탈이 제대로 갈려나간 문제입니다. 다음 대회를 망치지 않기 위해서는 이런 문제를 풀어야 한다고 생각해서 잡고 풀었습니다. 서브태스크 1 (5점) $k=2$로, 바로 옆의 식물과의 대소관계를 확실히 알 수 있습니다. 어떤 식물 $x$가 식물 $y$보다 확실히 크려면 (문제 조건에 의해 $x h_{x+1} > \cdots > h_{y-1} > h_y$ $h_x > h_{x-1} > \cdots > h_1 > h_n > \cdots > h_{y+1} > h_y$ 첫 번째 조건은 $s_x = s_{x+1} = \cdots = s_{y-1} = 0$에 대응되고, 두 번째 조건은 $s_1 = \cdots = s_{x-1} = s_y = \cdot..
ARC 121 후기 및 풀이 이번 앳코더 ARC에서 6문제를 다 풀어 전체 5등, Rated 중 1등을 하였습니다. 간단한 후기와 문제 풀이를 해볼까 합니다. A. 2nd Greatest Distance 구현과 케이스처리가 매우 복잡한, 400점짜리 문제 치고는 어려운 문제입니다. 다만 아래와 같은 관찰을 통해 구현을 편리하게 줄일 수 있습니다. 각 정점을 x좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점과, y좌표순으로 정렬했을 때 상위 2개 / 하위 2개 점만이 필요하다. 만약 2번째로 긴 체비셰프 거리가 위 정점들로 이루어지지 않는다면, 두 양끝점 중 하나를 위에서 뽑아낸 (최대 8개의) 점들로 대체했을 때 더 긴 해를 얻을 수 있음이 보장되기 때문입니다. 따라서 위와 같이 8개의 점의 후보를 얻어내고, 나이브하게 2번째로..
APIO 2021 후기 APIO 2021은 작년 APIO보다 많이 어려운 셋이었고, 점수도 받기 힘들었습니다. cms 화면 캡처는 깜박하고 못 했지만, 47+100+36=183점을 획득했습니다. 전체 성적은 29등(은메달) / 한국 1등입니다. 인증샷은 APIO 결과 화면으로 대체합니다. 문제의 난이도가 매우 높았고 구현도 힘들었으며, 대회 중에 채점 큐가 터져서 정말 고난의 연속이었습니다. 물론 그 덕에 시간을 1시간 더 받긴 했고, 결과적으로는 이득이었던 것 같습니다. 아래는 문제별로 제가 생각한 최대 풀이입니다. A. 육각형 영역 최종 점수: 47점 총평: 100점 풀이는 바로 나왔지만, 구현이 매우 매우 매우 매우 매우 더러워서 시간 내에 도저히 풀 수 없는 문제였습니다. 구현이 간단한 풀이가 있다면 매우 궁금합니다. ..
2021 국대 멘토링 일지 - 3주차 이번 멘토링 셋은 JOI 2020으로, 4시간 동안 5문제를 풀어야 했습니다. 전체적인 난이도는 예상했던 것보다는 할 만했던 것 같습니다. 시간대별로 상황을 서술하겠습니다. 3주가 2주보다 먼저 올라오는 이유는... 아직 2주 문제들을 구현해보지 못했기 때문입니다. #1. Just Long Neckties (0:00 ~ 0:06) 만약 $A$와 $B$가 모두 정해진다면, 둘 다 오름차순으로 정렬한 뒤 같은 순서에 있는 것끼리 matching하는 것이 최적임을 쉽게 보일 수 있습니다. 따라서 $A$에서 가장 큰 것을 빼고 나머지끼리 matching시켜 답을 구한 뒤에, $A$의 값을 하나씩 바꿔 주면서 multiset 등을 이용해 계속 가장 큰 값을 찾아내면 됩니다. Time Complexity: $O(N..
2021 국대 멘토링 일지 - 1주차 이번 주부터 국대 멘토링 교육이 시작되었습니다. 내신 준비로 시간이 충분하지 않아 일부 문제들은 풀이만 생각하고 구현을 아직 해 보지 않았는데, 시험이 끝나는 대로 구현해 볼 예정입니다. 제가 배정받은 문제 세트는 다음과 같습니다. #1. Trous de Loop (BOJ 18368) 조건을 만족하는 가장 긴 구간을 찾는 문제이므로 투 포인터를 이용합니다. 각 구간에서 자기 내부의 길이 $d$ 구간 중 구간 합이 최대인 것을 찾아야 하는데, 이 문제는 사실 누적합을 이용하면 투 포인터를 돌리면서 구간 내의 최댓값을 빠르게 찾는 문제가 되고, 이는 덱으로 해결 가능합니다. 따라서 문제가 쉽게 풀립니다. Time Complexity: $O(N)$ #2. Highway Modernization (BOJ 183..