Cabbage Leaves Cabbage Leaves

분류 전체보기

• 1931

  백준 2021. 8. 3. 19:37

  1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 회의시간이 $n(1\leq n \leq 10^{5})$개 주어질 때 최대로 진행할 수 있는 회의의 개수? $O(nlog\ n)$ 남은 회의 중 가장 빨리 끝나는 회의를 우선으로 배정한다 위 알고리즘으로 선택한 회의를 $S$, 최적해를 $O$라 하자 이때 각 집합은 회의가 빨리끝나는 순으로 indexing 되어있다 $$\begin{align*} &S:= \left \{ p_{1},\ p_{2},\cdot \cdot \cdot, p_{k} \right \}\\ &O:= \left \{ q_{1},\ q_{2},\cdot \cdot \cdot, q_{l} \right \} \e..

• 1521-B, *1300

  코드포스 2021. 8. 1. 21:28

  Problem - 1521B - Codeforces codeforces.com 문제 크기가 $n(1\leq n \leq 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다 인접한 항이 서로소가 되게 수열의 값을 변경시켜라 (단, $\mathrm{min(a_{i},\ a_{j})=min(x,\ y)}\ \text{and}\ i\neq j,\ a_{i},\ a_{j}\rightarrow x,\ y$) $O(n)$ $(a,\ a+1)=1$임을 이용한다 준 수열의 최소값이 $m$이라고 하면 준 수열을 다음과 같이 바꾼다 $$...,m+2,\ m+1,\ m,\ m+1,\ m+2,\ ...$$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20..

• 1534-C, *1300

  코드포스 2021. 8. 1. 18:04

  Problem - 1534C - Codeforces codeforces.com 문제 $A \in \mathfrak{Mat_{\text{2, n}}}(\mathbb{N})$ 행렬 A에서 같은 열이나 같은 행에 같은 수가 없는 상태를 solve 라고 한다 solve 상태인 A가 주어졌을때 임의의 열의 두 수의 자리를 바꿔서 만들 수 있는 solve 상태 행렬의 수는? $O(nlog\ n)$ 1 2 3 4 5 2 1 4 5 3 위와 같은 solve 상태의 행렬 A가 주어졌다고 하자 첫번째 열을 바꾸면 첫 행에 2가 두개가 되므로 두번째 열도 바꿔야한다 이런식으로 동시에 바뀌어야 하는 열을 같은 집합으로 나타낸다면 $$S=\left \{ \left \{ A^{1},\ A^{2} \right \},\ \left ..

• 1538-C, *1300

  코드포스 2021. 8. 1. 16:48

  Problem - 1538C - Codeforces codeforces.com 문제 크기가 $n(1\leq n \leq 2 \cdot 10^{5})$인 수열 $a_{1}a_{2}...a_{n-1}a_{n}$이 주어진다 $l\leq a_{i}+a_{j} \leq r$인 $i,\ j(i \neq j)$의 개수를 구하라 $O(nlog\ n)$ 먼저 준 수열을 sort 한다 $O(nlog\ n)$ 이제 모든 원소 각각을 뽑았을 때, 조건을 만족하는 원소의 왼쪽 index와 오른쪽 index를 구해서 개수를 구한다 예를 들어 $[l,\ r] = [5,\ 8]$, 수열을 $[1,\ 2,\ 3,\ 4,\ 5]$ 라고 하자. ( ) 은 조건을 만족하는 수들이고 | 은 수를 뽑을 때 칸막이 오른쪽 수들만을 고려한다는 의..

• 1555-B, *1300

  코드포스 2021. 7. 31. 15:16

  Problem - 1555B - Codeforces codeforces.com 풀이 너비가 $W$, 높이가 $H$인 배치도에 2개의 x-y축에 나란한(axis-aligned) 두 개의 책상을 배치한다 첫번째 책상이 먼저 배치되어 있다 두번째 책상의 너비$w$와 높이$h$가 주어질 때, 첫번째 책상을 이동하여 두 번째 책상을 배치할 수 있나? 있으면 첫번째 책상을 최소 얼만큼 움직여야함? $O(t)$ 책상을 배치하는 경우는 다음과 같이 나눠진다 첫번째 책상을 기준으로 두 번째 책상은 i) 상, 하에만 배치 가능 ii) 좌, 우에만 배치 가능 iii) 상, 하, 좌, 우 배치 가능 iv) 안됨 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

• 1555-C, *1300

  코드포스 2021. 7. 31. 14:31

  Problem - 1555C - Codeforces codeforces.com 문제 $2 \times m\ \mathrm{matrix}$ 위에 동전이 깔려있다 Alice, Bob 두 사람이 게임은 한다. 두 사람은 오른쪽이나 아래로 밖에 못 가며 이동한 칸에 있는 동전은 주워간다 Alice가 먼저 $1\times 1$부터 $2\times m$까지 이동한다 그 후 Bob이 $1\times 1$부터 $2\times m$까지 이동한다 $score$는 $\mathrm{Bob}$이 주운 돈의 합 Alice는 $score$를 최소화하도록 이동하고 Bob은 최대화하도록 움직인다 $score$? $O(m)$ Alice가 아래로 이동하는 열을 down 이라고 하자 그러면 Bob의 이동경로는 다음 두 가지 중 하나이다 i..

• 1547-D, *1300

  코드포스 2021. 7. 30. 21:08

  Problem - 1547D - Codeforces codeforces.com 풀이 수열 $a_{1}a_{2}...a_{n}$에 대해 $i$에서 $a_{i}\&a_{i+1}=a_{i},\ i = 1,\ 2,...,\ n-1$일때 수열이 $growing$이라고 한다 두 수열 $a,\ b$에 대해 수열 $\left \{ (a_{1}\oplus b_{1}),\ (a_{2}\oplus b_{2}),\ ...\ ,\ (a_{n}\oplus b_{n}) \right \}$이 $growing$이면 두 수열 $a,\ b$는 $co-growing$이라고 한다 수열 $x$가 주어질 때 $x,\ y$가 $co-growing$에게 하는 lexicographically minimal sequence $y$를 구하라 $O(n)$..

• 코드포스 난이도(*800 ~ 3500) 별 출제 유형

  아무거나적어~ 2021. 7. 29. 16:23

  미리보기 참고 자료수집: https://codeforces.com/problemset?order=BY_RATING_DESC 자료대상: 알고리즘 유형이 기제되어 있는 모든 문제 자료수집시기: 21.07.29 수집방법: python3 을 이용한 crawling 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import requests from bs4 import BeautifulSoup from collections import defaultdict as dd import matplotlib.pyplot as plt db = dd(lambda: dd(int)) cnt ..