$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

전체 글

(113)
BOJ 10532, USACO 2014 March Gold II Sabotage 난이도 : Solved AC 기준 Platinum 3 사용 알고리즘 : Binary Search (Parametric), Kadane Algorithm, etc... 1. 문제 설명 최대 10만 개의 정수 수열이 주어진다. 이 수열에서 중간의 연속된 Segment 하나를 들어내어 없앰으로써 (단, 처음과 끝에 있는 수는 없앨 수 없다), 남은 부분의 Average를 최소화하고자 한다. 2. 풀이 남은 부분의 Average를 minimize하는 것은 매우 특이한 작업인 데 비해, 남은 부분의 Sum을 minimize하는 것은 매우 쉬운 작업이다. 안쪽 구간 중 Maximum sum subarray를 찾으면 충분하고 이는 $O(n)$ 에 가능하기 때문이다. 이를 이용하여 Average를 빨리 구하는 발상은 ..
6월 ~ 7월 1주차 PS 정리 결국 1학기가 종강하고 나서야 PS를 다시 조금씩 시작했다. :( 앞으로 이렇게 묶어서 포스팅할때는 코드를 Github을 이용해서 올리려고 한다. BOJ 16440, 경북대학교 Goricon 2018, "제이크와 케이크" 난이도 : Solved AC Platinum 5 s와 k가 나열된 문자열을 최소 개수의 연속된 조각으로 자르고, 이를 재배열하여, 양쪽이 같은 개수의 s와 k를 가질 수 있게 하는 문제이다. 답이 2 이하라는, 즉 2번의 커팅으로 문제를 반드시 해결할 수 있다는 놀라운 Claim을 증명하려고 한다. 이는 다시 말해, 하나의 $n/2$짜리 연속한 segment가 $s$와 $k$를 동수로 포함하도록 자를 수 있음을 의미한다. $n/2$ 개 짜리 연속된 구간을 먼저 잡고, 이를 오른쪽으로 살..
메르텐스 함수 (Mertens Function) 와 그 빠른 계산 (Xudyh Sieve) 메르텐스 함수 (Mertens Function) 은 뫼비우스 함수 (Mobius Function) 으로부터 정의되는, 매우 재밌는 성질을 갖는 함수이다. 1. Mobius Function / Mertens Function의 정의 먼저, 간단히 정의를 살펴보자. 정의. Mobius Function 다음과 같은 뫼비우스 함수를 정의한다. $$\mu(n) =\begin{cases} 0, & ^\exists d \in \mathbb{N}, d > 1 \text{ such that } d^2 | n\\ (-1)^k, & n = p_1 p_2 p_3 \dots p_k \end{cases}$$ https://gratus907.com/43?category=869407 한참 예전에 이런 포스팅을 했었는데, 여기에서 뫼비..
4월 3, 4주차 PS 정리 그나마 Red Army Study와 dlwocks31이랑 연습하면서 푸는 문제들이 있어서 조금 알고리즘 공부하는 시간이 늘었다. Google Code Jam Round 1B에 참가했고, 319등의 성적을 거뒀다. https://gratus907.com/103 9문제 + Codejam이 있으니 11문제라고 생각하기로 했다. ㅋㅋ 레드아미의 경우, 2주차 셋은 개인적으로 괜찮았지만 3주차 셋은 공부하는 의미가 없었다. 여기 기술된 문제 중 2주차에 해당했던 문제는 Palindrome, Sad Powers, Queue, Red-White Fence의 4문제이고, 3주차의 경우 한 문제도 적지 않았는데, 어쩌다보니 문제가 다 사전지식만 있으면 금방 뚝딱하는 문제거나 끔찍한 구현에 시달리는 문제가 뽑혀서... B..
페르마의 두 제곱수 정리 이번 포스팅에서는 다음과 같은 정리를 증명해 보려고 한다. Theorem 1. 페르마의 두 제곱수 정리 어떤 소수 $p$ ($p > 2$)가 두 제곱수의 합, 즉 자연수 $x, y$에 대해 $$p = x^2 + y^2$$으로 나타내어질 필요충분조건은 $p \equiv 1 \mod 4$ 인 것이다. $\Rightarrow$ 거의 자명. 모든 제곱수는 모듈러 4에서 1 또는 0이고 (홀수를 제곱하면 1, 짝수를 제곱하면 0임이 어렵지 않다), 이를 더하여 $4k+3$ 형태의 홀수는 절대 얻을 수 없다. 따라서, 소수가 $4k + 1$ 인 것은 두 제곱수의 합이기 위한 필요조건임을 안다. $\Leftarrow$ 긴 여행을 떠나야 한다 (...) Wikipedia나 http://www.secmem.org/blo..
Codeforces 1251F (Educational 75) Red-White Fence 난이도 : Codeforces 2600 사용하는 알고리즘 : FFT, Combinatorics 1. 문제 설명 Red Fence $k < 5$ 개와, White Fence $n < 1e5$ 개의 길이가 주어진다. 이때, 다음과 같은 조건을 만족하는 Fence를 만들려고 한다. - 가운데의 Red-Fence를 기준으로, 그 앞과 뒤에 0개 이상의 White Fence를 설치한다. - 이때, Red Fence까지의 높이는 Strictly increasing해야 한다. 즉, 1 < 3 < 5 < 7, 7이 빨간색과 같은 형태. - Red Fence부터 끝까지의 높이는 Strictly Decreasing해야 한다. 즉, Red Fence를 중심으로 하는 Strict bitonic 을 요구한다. 쿼리가 잔뜩 주어..
BOJ 13361 최고인 대장장이 토르비욘 난이도 : Solved.ac 기준 다이아 5 출처 : ICPC NWERC Regional, Nordic Collegiate Programming Contest [NCPC] 2016 H 1. 문제 설명 직사각형 $n$ 개가 주어진다. 각각의 두 변의 길이는 $a_i, b_i$ 이고, 이걸 적당히 돌려서 $n$개를 위로 쌓으려고 한다. 다음 조건을 만족해야 한다. - 각 직사각형의 '너비' 는 Strictly 감소 수열을 이뤄야 한다. - 가능한 경우 중 '높이' 가 최대한 커야 한다. 2. 풀이 굉장히 중요한 발상이 있는데, 이 발상을 처음 떠올리기는 많이 힘든 것 같다. 비슷한 문제를 어디선가 누가 말해줘서 이런 생각을 본적이 있는데 출처를 모르겠다. :( 직사각형이 가진 두 숫자 $a_i$ 와 $b_i..
Google Codejam 2020 Round 1B 1, 2번 풀이 Codejam은 구글에서 진행하는, 기업 대회 중에서는 가장 규모도 크고 알려진 PS 대회로 수만명이 참가하는 대회이다. Qualification Round에서 기본적인 코딩 실력 정도로 거르고, 그 인원으로 Round 1을 세 번 치르는데 세 번 중 한 번만 1500등 안에 들면 Round 2에 진출할 수 있다. 1A에서 진출한 사람은 1B를 응시하지 못하므로 1A, 1B, 1C로 갈수록 진출하기는 조금 쉬워진다고 할 수 있겠다. Round 1A같은경우는 아침이라 말려서 (라는 핑계로) 2천등 정도 해서 진출에 실패했고, Round 1B는 어제 새벽에 319등이라는 기대 이상의 좋은 성적을 거두고 진출했다. 푸는데 성공한 두 문제의 풀이를 적으려고 한다. Editorial 과 거의 같지만, 1번의 아이..