코드포스
-
1604-C, *1300코드포스 2021. 11. 1. 00:20
Problem - C - Codeforces codeforces.com 문제 순열 $a_{1} a_{2}...a_{n}$ 가 주어질 때 다음과 같은 시행을 통해 순열이 모두 지워질 수 있는가? $(i+1)\nmid a_{i}$인 항은 지울 수 있다. 이 때 지운 후에는 바뀐 index 에 대해 이 시행을 적용한다 풀이 다음을 관찰하자 중간에 있는 항을 지우면 앞 항들은 erasability(지울 수 있음)가 유지되고 뒤 항들은 변한다 따라서 뒤 항부터 보면서 지우는게 중간이나 앞에서부터 지우는것보다 지울 수 있는 항을 유지하는 더 좋은 선택이다 다음과 같은 greedy 방식으로 푼다 1. 뒤에서부터 지울 수 있는건 지운다 2. 지우다가 막히면 앞에꺼 중 가장 가까이 있는 지울 수 있는 index를 찾아 ..
-
1604-D, *1600코드포스 2021. 10. 31. 21:30
Problem - D - Codeforces codeforces.com 문제 두 양의 짝수 $x,\ y(2 \leq x,\ y \leq 10^{9})$가 주어진다 $n \text{ mod } x = y \text{ mod } n$을 만족하는 $n(1\leq n \leq 2\cdot 10^{18})$을 출력하라 $O(1)$ 제약이 더 많이 생기면 조건이 더 명확해지므로 x, y 의 크기로 경우를 나누어 풀었다 i) x = y 인 경우 n = x 이면 성립한다 ii) x > y 인 경우 잘 모르겠어서 작은 입력에 대한 결과를 출력해봤다 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 #include #define endl ..
-
1283-C, *1500코드포스 2021. 9. 17. 00:35
Problem - C - Codeforces codeforces.com 문제 $n(2\leq n \leq 2\cdot 10^{5})$명의 사람을 차례대로 1, 2, 3, ... , n 이라고 하자 각각의 사람이 누구에게 선물을 주어졌는지 주어진다. 이때 0 은 아직 선물을 주지 않은 사람이다 선물을 아직 주지 않은 사람은 다음 조건을 만족하도록 선물을 주어야한다 1. 자기 자신에게는 주지 않는다 2. 모든 사람은 선물을 적어도 하나 받는다 위 조건을 만족하도록 선물을 주는 경우를 아무거나 출력하라 $O(n)$ 각각의 사람을 node, 선물을 주는 것을 edge 로 표현하여 위 문제를 graph 로 이해하자 그러면, 위 문제는 다음 조건을 만족시켜야 한다 1. 각각의 노드에서 뻗어나가는 edge 는 유일하..
-
1283-D, *1800코드포스 2021. 9. 16. 00:53
Problem - D - Codeforces codeforces.com 문제 $n(1 \leq n \leq 2\cdot 10^{5})$개의 나무가 수직선 위의 서로다른 $x_{i} \in \mathbb{Z}$에 있다 $m(1 \leq m \leq 2\cdot 10^{5})$명의 사람의 위치 $y_{i} \in \mathbb{Z}$는 다음 조건을 만족해야 한다 1. 나무가 있는 정수좌표에는 사람이 있으면 안된다 2. 한 좌표에는 두명 이상이 있으면 안된다 어떤 사람 $y_{i}$의 인접한 나무와의 거리를 $d_{i}$라 할때, $d_{i} = \overset{n}{\underset{j=1}{\text{min}}}|y_{i}-x_{j}|$ $d_{i}$의 합이 최소가 되도록 사람을 배치할 때의 $\mathr..
-
1560-A, *800코드포스 2021. 8. 30. 14:30
Problem - 1560A - Codeforces codeforces.com 문제 1부터 다음 조건을 만족하는 수$x$를 나열할 때, $k(1\leq k \leq 1000)$번째 수는? $x$는 3의 배수가 아니며 일의자리수가 3이 아니다 $O(\frac{5}{3}k)\approx O(k)$ 1부터 하나하나 따질 때 시간복잡도 분석을 해보자 살구색 음영은 3의 배수인 수들이고 빨간색 빗금은 3의 배수가 아닌 수 중 일의자리수가 3인 수이다 위 수들은 주황색 점선을 기준으로 주기가 반복된다. 따라서 $$\frac{18}{30}\cdot \text{(last number)}\leq k$$ 1 2 3 4 5 6 7 8 like = [0] k = 1 while len(like)
-
1498-B, *1300코드포스 2021. 8. 16. 21:54
Problem - 1498B - Codeforces codeforces.com 문제 높이가 1이고 너비가 2의 거듭제곱 형태$(w_{i} = 2^{k})$인 블록 $n(1\leq n \leq 10^{5})$개가 주어진다 높이가 1이고 너비가 $w$인 박스가 있을 때, 모든 블록을 담으려면 최소 몇 개의 박스가 필요한가? (단, $w \geq \mathrm{max(w_{i})}$ 풀이1 Greedy 너비가 큰 블록부터 상자에 넣는다. 블록이 들어간 상자들 중 남는 자리가 있으면 그 곳에 채워넣고, 없으면 새로운 상자에 블록을 넣는다 Claim 1 $w_{i}$가 2의 거듭제곱 꼴이고 $w_{1}$ 부터 $w_{n}$이 증가할때 $$\begin{aligned} &w_{1}+w_{2}+\cdot \cdot \..
-
1553-C, *1200코드포스 2021. 8. 15. 21:32
Problem - 1553C - Codeforces codeforces.com 풀이 두 팀 $odd$와 $even$이 돌아가면서 승부차기를 한다 $1$은 성공, $0$은 실패, $?$은 성공 또는 실패를 의미할 때, 최소 몇번의 킥을하게 되는가? $O(1)$ 승부차기에서 더 이상 킥을 해도 의미가 없는경우는 '지고 있는 팀이 남은 킥을 모두 성공해도 점수를 뒤집을 수 없을 때' 이다 따라서 킥의 횟수를 줄이려면 한쪽 팀이 유리하게 $?$를 바꿔야한다 i) $?$를 $odd$팀이 유리하게 바꿨을 때 최소 킥의 횟수 ii) $?$를 $even$팀이 유리하게 바꿨을 때 최소 킥의 횟수 를 각각 구하며 더 작은 값이 구하려는 값이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..
-
1553-D, *1500코드포스 2021. 8. 15. 19:45
Problem - 1553D - Codeforces codeforces.com 문제 문자열 $s$와 $t$가 주어진다 $s$의 왼쪽부터 문자 하나당 시행1 이나 시행2를 한다 시행1. 키보드로 그 문자를 누른다 시행2. 키보드로 그 문자를 누르지 않고 Backspace 를 누른다 ex) abcd 에서 순차적으로 1121 시행했다면 $\mathrm{a\rightarrow ab \rightarrow a\rightarrow ad}$ abdd 에서 순차적으로 2121 시행했다면 $\ \rightarrow b \rightarrow \ \rightarrow d$ $s$로 부터 $t$를 작성할 수 있는가? $O(\left | s \right |)$ $sp,\ tp$ 두개의 포인터를 사용하여 $t$의 뒤쪽부터 앞쪽으로..