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

Gratus' Blog (5 Page)::::Gratus' Blog

"전체 글" 관련 글 119

7월 2 ~ 4주차 PS 정리
알고리즘 문제풀이/PS_Weekly 2020. 7. 26. 18:33
주로 UCPC 2020을 위해 팀원들이랑 공부한거랑, 일주일에 한번씩 도는 dlwocks31과의 1:1 세션에서 푼 문제들이다. BOJ 8903, ICPC Daejeon Regional 2011 D번 "Equipment" (장비) 난이도 : Solved AC Platinum 3 최대화해야 하는 지표가 5개뿐임을 관찰하자. 또한, $\binom{n}{k}$ 개의 조합을 모두 볼 필요가 없는데, $k >= 5$ 이면 지표 $a, b, c, d, e$에 대해 각각을 최대화하는 장비 5개를 모두 고를 수 있고 나머지 전부는 무의미하기 때문이다. 즉, $k = 2, 3, 4$ 에 대해서만 풀자. $k = 2$ 일 때를 예로 들어 생각해 보면, 5개의 stat 중, 몇개는 장비 1에서, 나머지는 장비 2에서 올 것..
2020 UCPC 인터넷 예선 후기 / 풀이
알고리즘 문제풀이/대회 후기, 문제풀이 2020. 7. 26. 12:00
Update : G번의 제한시간에 대한 정정을 두번 받았고, 생각난김에 코드를 추가한다. [코드 링크] * 대회 종료 시간으로 예약 작성하였습니다 :) * 작년의 Little Piplup 그대로 올해도 UCPC에 참여했다. 올해로 3번째 참여하는 UCPC고, 이 팀으로 참여하는 공식대회도 꽤 많았지만 나름 각별한 느낌이 좀 있는데, 팀원들의 병특 시작 등으로 (아마도) 이 3명 그대로 참여하는 마지막 대회일 수도 있어서.... 앞으로도 PS는 같이 할 것 같지만, ICPC에서 휴학생이 참여할 수 없다는 점이 크다. DHdroid의 병특 결과에 따라 내 ICPC 팀도 결정될 예정. 후기 느낌으로 쓰면서 풀이를 Discuss하는 글이기 때문에, 문제 풀이만을 확인하기에는 별로 좋지 않다. 생각하는 흐름 그대..
BOJ 10532, USACO 2014 March Gold II Sabotage
카테고리 없음 2020. 7. 6. 02:17
난이도 : 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 정리
알고리즘 문제풀이/PS_Weekly 2020. 7. 4. 02:44
결국 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)
알고리즘 공부/Mathematics 2020. 5. 1. 04:23
메르텐스 함수 (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 한참 예전에 이런 포스팅을 했었는데, 여기에서 뫼비..
admin

티스토리툴바