qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

BOI 2023을 돌았다. Day 1 0:00 ~ 0:27 문제를 다 읽었다. 1번은 원 그려진거 보고 바로 넘겼고 2번은 인터렉티브라서 일단 넘겼다. 3번은 간단한 dp일 것 같다는 느낌을 받아서 3번부터 풀었다. 한 지점에서 p의 배수가 될 때까지 기다리거나 기다리지 않고 넘어가거나 둘 중 하나만 해도 되기 때문에 간단한 제곱 dp를 짤 수 있다. 이걸 짜면 27점을 받는다. 0:27 ~ 0:43 dp[i] = min_{j

06/27 학교 수업시수 채워야 해서 불참했다. 06/28 BOJ 8243 (POI 12/13 Arch) / O 왕이 1번 노드에서 시작해서 트리 위를 움직이는데, 왕이 도착한 노드는 색칠이 된 상태여야 한다. 현재 왕의 위치는 알 수 있지만, 왕이 어디로 갈지는 모른다. 하루에 칠할 수 있는 노드의 최대 개수를 $X$개라고 할 때, 조건을 만족하도록 할 수 있는 $X$의 최솟값을 구해야한다. $X$에 대한 이분탐색 + 트리 dp로 해결가능하다. BOJ 11746 (Landscape Improved) / O 돌 $N$개를 바위들 위에 적절히 쌓아서 꼭대기의 높이를 최대화해야 한다. 답에 대한 이분탐색을 한다고 가정하고, 각 x좌표에 대해 그 지점에 꼭대기가 있을 경우 돌이 몇 개 필요한지를 세그트리 + ..

1. 국대교육은 아침연습 3문제, 오후실습 3문제로 구성되어있다. 글에 적힌 순서대로 아침연습 123번, 오후실습 123번이다. 2. O는 대회 시간 내로 AC를 받은 문제, △는 업솔빙을 한 문제, X는 업솔빙 안 한 문제이다. 06/21 이 날은 학교 수행 때문에 교육을 빠졌다. 06/22 BOJ 22491 (Repairing) / X 파이프와 밸브가 여러 개 있고, 밸브를 적절히 잠궈서 끝점에 물이 못 흘러들어가게 해야 한다. 이때, 물이 안 흐르는 구간의 길이의 합을 최소화해야 하고 이 값을 출력해야한다. 대충 그래프를 만들었다고 생각하면 끝점에서 bfs 같은걸 돌려서 가장 가까운 밸브들을 전부 잠근 다음 시작점에서 물을 흘려보내서 계산을 하면 될거같다. AC를 받은 사람이 없어서 맞는지는 잘 모..

문제 셋: 1번 IOI09 POI (https://www.acmicpc.net/problem/5462) 2번 BOI06 Coin Collector (https://www.acmicpc.net/problem/3368) 3번 CEOI13 Adriatic (https://www.acmicpc.net/problem/9284) 4번 KTST20 하나 둘 셋 (https://www.acmicpc.net/problem/25013) KOI 스타일로 구성된 4시간 셋입니다. 0:00 ~ 0:06 난이도 순이라는 걸 알고 있었기 때문에 1번부터 차례로 풀었습니다. 매우 쉬운 문제이므로 바로 AC를 받고 넘어갔습니다. 0:06 ~ 1:30 2번을 봤습니다. 문제를 잘못 이해해서 1시간 가까이 뇌절을 했고, 일단 나이브라도 ..

문제 셋: 2011 IOI day 2 실제 대회처럼 5시간 타이머를 해놓고 봤습니다. 0:00 ~ 0:24 일단 1번 문제부터 읽어봤습니다. 부모 정점을 고려해서 적당한 트리 dp를 돌리면 서브태스크 1을 맞출 수 있다는 강한 확신이 있었지만 구현과 디버깅을 빠르게 할 자신이 없어서 일단 보류했습니다. 서브태스크 1의 배점이 매우 높기 때문에 일반그래프를 트리로 줄이면 문제가 해결되지 않을까 하고 생각을 해봤지만 잘 되진 않았습니다. dp관점으로 생각해보면 답이 작은 정점부터 차례로 계산해나갈 수 있고, 이는 다익스트라와 동일한 발상입니다. 구현도 매우 간단하기 때문에 바로 코딩을 했고, 100점을 받았습니다. 다른 문제를 읽지 않고 한 문제의 100점 코드를 짠다는 것은 매우 위험한 전략이지만, 풀이가..

레드 후기를 올릴 때 IGM을 찍으려면 1년은 걸릴 줄 알았는데 생각보다 빨리 찍게 되었네요. 딱히 적을 말도 없고 아마 코포 레이팅 관련 글은 이게 마지막일 것 같으니 (누텔라를 찍으면 얘기가 달라지지만) 제가 코드포스 IGM을 찍을 때까지 어떻게 공부했는지 정리하려고 합니다. 1. Virtual Contest로 많은 대회를 풀어보기 코드포스 레이팅을 올리는 가장 효과적인 방법은 최대한 많은 코드포스 대회에 참가하는 것입니다. 코드포스에서 제공하는 기능인 virtual contest로 과거 대회를 풀어보면 실제 대회랑 유사한 환경에서 문제를 풀 수 있고, 코드포스에 자주 나오는 유형을 파악하거나 전략을 세우는데 매우 큰 도움이 됩니다. 저는 오렌지이던 시절에 Div.1 contest들을 virtual ..

대회 시작 전 대회가 시작하기 전, 노트북을 점검하는 시간에 코드블럭을 키고 몇가지 코드를 짜서 돌려봤습니다. NYPC는 휴리스틱 문제가 자주 나오는 편이기 때문에, 난수를 생성하는 mt19937을 짜서 돌려봤는데 무슨 이유에선지 컴파일 에러가 났습니다. 그래서 그냥 rand()를 쓰기로 하고 일단 넘어갔습니다. 다른 코드도 몇 개 짜봤는데 range-based for가 작동하지 않고 컴파일 에러가 났습니다. 알고보니 코드블럭 기본 세팅이 c++98로 되어있었고, 스태프의 도움을 받아 c++11로 컴파일을 할 수 있게 되었습니다. 버전을 올리니 mt19937도 정상적으로 돌아갔고, 별 문제가 없었습니다. 0:00~0:30 NYPC 본선은 일반적으로 난이도 순으로 문제가 나오기 때문에, 쉬운 1번과 2번은..

NYPC 2021 예선이 종료되었습니다. 작년에 비해 문제 퀄이 많이 떨어진 것 같아서 개인적으로 좀 아쉬웠습니다. 문제마다 그냥 처음 떠오른 풀이를 바로 짜다보니 세그먼트 트리를 이용한 풀이가 좀 많습니다. 다른 쉬운 풀이가 있을 수 있으니 다른 블로그 풀이도 참고하면서 보면 좋을 것 같습니다. 1일차 1번) 계단 문제 요약 1층부터 $M$층까지 있는 건물의 $F$층에서 시작해서, 계단을 한 층 오르는 것을 $N$번하려고 할 때 엘리베이터를 타는 횟수의 최솟값을 구하는 문제입니다. 풀이 더보기 $M$층까지 올라간 후, 엘리베이터를 타고 1층으로 가는 것을 반복하는 것이 최적의 전략입니다. $M$, $N$이 크기 때문에 식을 세워서 풀면 $O(1)$에 답을 계산할 수 있습니다. 코드 더보기 #includ..