$$\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)}$$

본문 바로가기

전체 글

(110)
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번의 아이..
4월 1, 2주차 PS 정리 왤케 요새 안하지.... 딱히 할 시간이 없냐면 그건 또 아니다. (주로 롤토체스에 빠져 살고 있다) 5문제. 난이도 순 (아마도) 그나마 SNUPS Red Army를 시작해서 문제풀 동기가 조금 더 생겼다. Red Army는 작년에 TAMREF님이 개설한 스터디를 올해 내가 이어서 하고 있는데, Codeforces 기준 블루~오렌지 정도 실력을 가진 사람들이 조금 어려운 문제 (2000+) 를 일주일동안 몇개 풀고 디스커션을 하는, 스터디 그룹 같은 느낌이다. 다음주에는 Red Army 2주차를 최대한 풀고 풀이를 작성하는걸 목표로 하고 있다 (2주차부터는 이상한 사람들의 영향으로 2600, 2800 문제가 들어가 있기 때문에 다 풀긴 조금 무리가 있다) Codeforces Round 635 (Div1..
3월 3, 4주차 PS 정리 7문제, 난이도 순. 온라인 개강이라 시간이 널널할줄 알았는데 생각보다 과제가 많아서 PS를 못 돌고 있다. BOJ 11405 책 구매하기 난이도 : Platinum 4 MCMF가 무엇이고 어떻게 구하는지 공부할 때 푸는 기본 구현 문제. 플로우 같은 고급 알고리즘을 너무 모르는 것 같아서 MCMF를 공부하고 구현을 (적당히 팀노트를 베껴 가며) 해봤다. 아직 응용해서 MCMF 문제를 모델링해서 풀기에는 갈길이 먼것 같다. 팀노트에 넣어놓은 MCMF가 잘 도는지 확인하는 문제라고 할 수 있겠다. Atcoder Beginner Contest 160F, Distributing Integers Atcoder 난이도 1962 대략적으로 문제를 설명하자면, 정점 1부터 $N$까지로 구성된 트리에서, $x$ 번을 ..
BOJ 10847, APIO 2015 2 - Jakarta Skyscraper 출처 : 2015 Asia-Pacific Informatics Olympiad Problem 2 백준 번역명 "자카르타의 마천루" 난이도 : Diamond 3 1. 문제 설명 0번부터 $m-1$ 번까지의 번호를 가진 "도게" 가 있고, 이 도게들은 1 시간 만에 $+p$ 또는 $-p$ 만큼씩 점프할 수 있다. 도게끼리 만나면 소식을 전달할 수 있고, 소식을 이미 전달받은 도게만 움직일 수 있다. 1번 도게가 소식을 전달받는 최단 시간을 찾는 문제. 2. 풀이 설명 [36점, 57점 풀이 : Dijkstra] 최단 시간 (가중치가 주어질 때, 최단 경로)를 찾는 문제이고, 음수 간선이 없으며, $n \leq 30,000$개의 빌딩을 오가야 한다는 점에서 다익스트라 알고리즘을 이용해 보자는 생각을 할 수 있..