$$\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' 카테고리의 글 목록::::Gratus' Blog

"알고리즘 문제풀이/Codeforces" 관련 글 18

Codeforces 1251F (Educational 75) Red-White Fence
알고리즘 문제풀이/Codeforces 2020. 4. 24. 02:29
난이도 : 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) 후기 + 풀이
알고리즘 문제풀이/Codeforces 2020. 3. 14. 01:11
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) 후기 + 풀이
알고리즘 문제풀이/Codeforces 2020. 2. 18. 11:13
오렌지 찍었다 :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) 후기 + 풀이
알고리즘 문제풀이/Codeforces 2020. 2. 11. 01:03
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)
알고리즘 문제풀이/Codeforces 2020. 2. 5. 02:25
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$ 명은 어떤 선택을 할 지 알 수 없지만 내가 최대한 손해를 보는 상황이 되었을 때 얻는 값을 찾는 문제. 생..
admin

티스토리툴바