-
2020년 선린인터넷고등학교 교내 프로그래밍 대회들의 풀이
작년 하반기에 선린인터넷고등학교에서 개최되는 여러 정보 경시 대회에 김준원, 권욱제님 등과 함께 출제했던 적이 있습니다. 이 대회들에는 여러 교육적인 문제가 많이 있었으나, 잘 정리된 풀이는 아직 없는 것 같아서 이 참에 정리해봤습니다. 1. 2020 선린 정보 알고리즘경시대회 문제는 https://www.acmicpc.net/category/detail/2294 에서 풀어볼 수 있습니다. A. 헛간 청약 지문을 잘 읽으면 해결할 수 있는 문제다. 정답은 $\min(N, \lfloor W/L \rfloor \times \lfloor H/L \rfloor)$ 이다. 정답이 최대 $N$ 임에 유의하여 해결해야 합니다. B. 소-난다! 비트마스킹을 이용하여 $2^N$개의...
-
프로그래밍 문제 출제하기
서론 삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다. Acka1357님의 프로그래밍 대회를 개최하기 위한 10가지 djm03178님의 Codeforces #578, Codeforces #620 출제 후기 evenharder님의 UCPC 2020, KCPC 2018 출제 후기 hojoon0205님의 shake! 2019 출제 후기 이 글은 문제를 어떻게 만들 것인가에 초점을 둡니다. 아이디어를 어떻게 구상하고, 지문은 어떻게 작성하고, 데이터는 어떻게 만들고, 문제 검수는 어떻게 해야 하는지를 다룹니다. 백준 온라인 저지에...
-
AtCoder Regular Contest 075 C Meaningful Mean 풀이
문제 요약 문제 링크 $N$개의 수가 있다. $i$번째 수를 $a_i$라 하자. 수열 $a$의 $N$개의 수에서 연속한 수들을 고르는 방법의 가지수는 $\frac{N \times (N+1)}{2}$ 개이다. $\frac{N \times (N+1)}{2}$ 개 중에서 평균이 $K$ 이상인 것이 몇개인지 구하라. $ 1 \le N \le 2 \times 10^5, 1 \le K \le 10^9, 1 \le a_i \le 10^9 $ 풀이 1. $O(N^3)$ Naive 한 방법. $\frac{N \times (N+1)}{2}$ 개의 모든 경우에 대해서, 직접 합을 구하고 평균이 $K$ 이상인지를 확인한다. 2....
-
AtCoder Grand Contest D Median Pyramid Hard 풀이
문제 요약 문제 링크 $N$층의 피라미드가 있다. $i$번째 층에는 $2i - 1$개의 칸이 있다. 피라미드의 $N$층에 $1, 2, \cdots, 2N-1$을 적절히 섞은 순열이 쓰여 있다. $1$층 부터 $N-1$층 까지의 칸에 숫자를 채우는 규칙은, 그 칸에 있는 수가 그 칸 아래쪽에 있는 $3$개의 수의 중앙값이라는 것이다. 위 방법에 따라 피라미드를 채웠을 때, $1$층에 있는 칸에 쓰인 숫자를 구해라. $ 2 \le N \le 10^5 $ 풀이 1. $O(N^2)$ 규칙에 맞춰서 모든 칸의 값을 구해본다. 공간복잡도가 $O(N^2)$라고...
-
프로그래밍 대회를 개최하기 위한 10가지
프로그래밍 대회를 개최하기 위한 10가지 이 글은 Ajou Programming Contest(2016-19 APC), 경인지역 6개대학 연합 프로그래밍 경시대회(2016-19 shake!), 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회(2016 UCPC)를 운영했던 제 경험을 토대로 작성되었습니다. 프로그래밍 대회를 개최하려는 분들께 조금이나마 도움이 되었으면 하는 마음으로 대회를 맡으며 경험했던 시행착오를 모아 필요한 10가지를 정리해보았습니다. 어디까지나 제 개인의 경험에 기반한 내용으로 대회를 열기 위해서는 이래야 한다!가 아닌 아래 과정을 고려해보자는 의미로 읽어주시면 좋겠습니다. 일의 진행 순서로 나열하긴 했지만 모든 과정은 유기적입니다. 대회의...
-
2019 SCPC Round 2 5번 풀이
문제 요약 $M \times M$ 격자판에 $N$ 개의 점이 찍혀 있다. 각 점에 대해서, 그 점은 왼쪽 아래로 하는 가장 큰 정사각형을 그리려 한다. 단, 정사각형은 $N$ 개의 점중 어떤 점이라도 내부에 포함시키면 안된다. 모든 점에 대해서 정사각형을 그릴 때, 모든 정사각형 변의 합을 구하시오. $2 \le M \le 10^9$, $1 \le N \le 500000$ 풀이 1. 먼저 2D Range Tree 를 써서 특정 직사각형 구간에 점의 개수를 $O(\log^2 N)$ 시간에 알 수 있다. 여기에...
-
문제 출제를 위한 플랫폼 - Polygon 사용하기
Polygon이란? Polygon이란 Codeforces에서 제공하는 Competitive Programming Contest를 위한 문제 출제를 위한 플랫폼입니다. 출제를 위해 필요한 과정 - 데이터 제작, 검증, 솔루션 검증 등에 굉장히 유용한 기능들이 많으며 그 과정을 다른 사람과 공유하며 협업할 수도 있습니다. 폴리곤에서의 작업은 각 문제 단위로 동작합니다. 문제를 등록하는 방법부터 완성된 문제를 패키지로 다운받는 방법까지, 필요한 기능들을 간략히 확인하고 언제 어떤 메뉴를 사용해야 하는지 문제 출제 단계에 따라 익혀봅시다. 아, 그 전에 회원가입은 다들 하셔야겠죠? 문제 등록하기 폴리곤에 로그인하면 아래와 같은...