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

본문 바로가기

알고리즘 문제풀이/Codeforces

(18)
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 을 요구한다. 쿼리가 잔뜩 주어..
Codeforces Round #627 (Div. 3) 후기 + 풀이 Div3지만 코포에서 라운드 시간 중에 올솔브 성공한건 처음인것 같다. :dhk: A. Yet Another Tetris Problem $2 \times 1$ 블록을 아무리 세워도 각 열의 홀짝성을 바꿀 수 없다. 반대로, 홀짝성이 같다면 높이 쌓는것에는 문제가 없으므로 엄청 높이 쌓으면 전부 지울 수 있다. 따라서, 홀수와 짝수 중 한종류만 있으면 YES, 아니면 NO. B. Yet Another Palindrome Problem 길이가 3 이상인 Palindromic subsequence 가 있는지 확인하는 문제. Substring이 아닌 Subsequence이므로, - 어떤 수 $x$ 가 두번 이상 나오고, - 그 수가 나오는 최소 위치와 최대 위치가 두칸 이상 떨어져 있다면 (즉, $xx$가 아닌..
Codeforces Round #620 (Div. 2) 후기 + 풀이 오렌지 찍었다 :dhk: 한국인 세터 라운드라서 시간도 좋은 것 같아서, 오렌지까지 1점 남았지만 그냥 Div2 뛰기로 했다. A. Two rabbits 두 토끼 사이의 거리 $d$가 $a+b$ 로 나누어 떨어지는지 확인하고, 되면 몫을 출력, 아니면 -1. 더보기 #include #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") #define ll long long #define eps 1e-7 #define all(x) ((x).begin()),((x).end()) #define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); usin..
Codeforces Round #618 (Div. 1) 후기 + 풀이 Predictor에 +116이라고 뜨는 것과는 달리, 실제로는 +115를 받아서 2099점이 되었다. 오렌지 갔나 했는데, :blobsad: ㅠㅠ 라운드는 굉장히 재밌게 했던것 같다. A. Anu has a function 수열 $a_1, a_2, a_3 \dots a_n$ 과 함수 $f(x, y) = (x | y) - y$ 이 주어질 때, 이들을 적당히 재배열해서 $$f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)$$ 의 값을 최대화하는 문제. 잘 생각해 보면, $f(x, y)$ 는 $x$의 On bit 들을 모은 집합에서 $y$의 On bit 들을 모은 집합의 차집합을 반환한다는 사실을 알 수 있다. 즉, 최대한 '가치' 가 높은 비트(큰 비트) 들을 살리..
Codeforces Round 601 + 616 (Practice) dlwocks31 이랑 코드포스 Division 1 라운드 두개를 붙여서 같이 연습을 돌았다. Division 2는 A/B를 푸는게 실제로는 별로 의미가 없고, Div2 F는 못 풀 가능성이 높으니 실제로는 풀 만한 문제가 3개밖에 없어서 2시간 반을 잡고 Div1 두 라운드의 ABC 세문제씩만 뽑았다. Round 616 Problem A. Mind Control 사람들이 줄을 서 있고, 어떤 배열의 맨 앞과 맨 뒤 중 하나를 골라서 뽑아 올 수 있다. 이때 $m$ 번째에 서서 최대한 큰 수를 가져가고 싶은데, 앞에 있는 $m-1$ 명 중 $k$ 명의 선택을 강제할 수 있다. 나머지 $m-k-1$ 명은 어떤 선택을 할 지 알 수 없지만 내가 최대한 손해를 보는 상황이 되었을 때 얻는 값을 찾는 문제. 생..
Codeforces Educational Round 80 후기 + 풀이 Div2 기준 137등으로, 59점이 올라 2035점이 되었다. Max Rating 보다 약간 낮다. 전반적으로 셋은 재밌었는데, C번에서 약간의 뇌절 + E번에서 분명 풀었던 문제와 매우 비슷한데 실패해서 아쉽다. A. Deadline 정수 $d$ 가 주어졌을 때 다음을 최소화하는 문제이다, $$x + \left\lceil\frac{d}{x+1}\right\rceil$$ 잠깐 Ceiling 을 무시하고 산술기하 평균을 이용하면, $x+1 = \sqrt{d}$ 가 최적임을 알 수 있다. ceiling 함수가 붙으므로 약간의 오차가 발생할 수 있으므로, $\sqrt{d}$ 를 기준으로 좌우 100개 정도씩 값을 확인해 보면 된다. 대략 수학적으로 최적을 구하고 그 주위를 보는 문제는 UCPC때도 풀어 본 ..
Codeforces Edu78 F [Cards] 풀이 문제 지문은 생략하고, 다음을 계산하는 문제이다. Binomial Distribution $B(n, p)$ 가 주어진다. 이때, $E(X^k)$ 를 빠르게 구하고 싶다. Dynamic Programming 을 이용한 풀이가 있는것 같은데, 사실 잘 모르겠다. 그 풀이를 설명한 댓글에서도 Stirling number of the second kind 같은 것들을 언급하는 것으로 보아 그닥 프로그래밍적인 풀이인지는 모르겠고, 내가 모르는 조합 / 확률론적인 지식을 요구하는 것 같아서 굳이 그걸 찾아서 공부해야 할지는... 아무튼 내 풀이는 moment generating function 과 미적분 지식을 요구하기 때문에 그닥 Codeforce에 적합한 것 같지는 않다. 다른 풀이의 존재를 몰랐다면 이거 그냥..
Codeforces Round 603 (Div.2) 후기 + 풀이 Pretest 에서는 한 번도 안 틀리고 갔는데, B번에서 Failed System Test를 받았다. 프리텟을 9개 미만으로 넣었냐 퍼플 복귀 성공 :) A. Sweet Dreams 최근에 본 A번 중 가장 어려운거 같다. 한 5분정도 생각이 안나서 라운드를 던질지 고민했었는데.. $a, b, c$ 개씩의 세 종류의 사탕이 주어졌을 때 (Without loss of generality, $a \geq b \geq c$ 라 하자) 가 주어졌을 때, 서로 다른걸로 두개씩 고르는 행동을 몇 번 할 수 있는지 묻는 문제. 일단 $c$는 다 챙길 수 있으므로, 적어도 답은 $c$ 이상이다. 3번 사탕을 다 챙기되, 뭐랑 매칭해서 챙길지의 문제. $a - b =g$ 를 고려해서, 나중에 $a$와 $b$의 개수가 ..