코드포스
-
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)$..
-
1553-B, *1300코드포스 2021. 7. 28. 21:50
Problem - 1553B - Codeforces codeforces.com 문제 문자열 $s(1 \leq \left | s \right | \leq 500)$와 $t(1 \leq \left | t \right | \leq 2 \cdot \left | s \right |-1)$가 주어진다 스케너가 임의의 $s$ 문자 위에서 오른쪽으로 갔다가 왼쪽으로 차례로 읽을 때 $t$로 읽을 수 있는가? $O(t^{2}s)$ 먼저 스캔했을 때 $t$가 나올 수 있는 문자열을 구하자 --- ! 스케너가 오른쪽으로 갔다가 왼쪽으로 가기 시작하는 문자를 $key$라고 하자 $t$의 각 자리별로 $key$라고 생각하고 ! 을 구한다 $O(t^2log\ t)$ 스케너는 항상 오른쪽을 먼저 가기 때문에 ! 의 제일 오른쪽에는..
-
459-B, *1300코드포스 2021. 7. 28. 15:34
Problem - 459B - Codeforces codeforces.com 문제 $n(2 \leq n \leq 2 \cdot 10^{5})$개의 $b(1 \leq b \leq 10^{9})$가 주어진다 $b_{i},\ b_{j},\ i \neq j$ 차이의 최대값을 구하고 그 값이 나올 수 있는 경우의 수를 구하라 풀이 $b_{i}$의 최대값을 $\mathrm{max}$, 최솟값을 $\mathrm{min}$ 이라고 하자 i) $\mathrm{max=min}$ 차이의 최대값이 나오는 경우의 수는 $b$의 값에 따라 개수를 세서 구한다. $$\mathrm{(max\ value\ b\ number)} \times \mathrm{(min\ value\ b\ number)}$$ ii) $\mathrm{max \..
-
451-B, *1300코드포스 2021. 7. 28. 13:18
Problem - 451B - Codeforces codeforces.com 문제 크기가 $n(1 \leq n \leq 10^{5})$인 배열이 주어진다 오직 한번만 배열의 일정 구간을 뒤집어서 배열을 오름차순으로 정렬할 수 있는가? $O(n)$ 문제의 상황을 감소하는 구간의 개수에 따라 나눠보자 (감소하는 구간 $[l,\ r]$이란 구간 내에서 감소하면서 $\mathrm{arr[l-1] < arr[l]\ and\ arr[r] < arr[r+1]}$을 만족) i) 감소구간이 0개 배열이 오른차순으로 정렬되어 있다는 의미 ii) 감소구간이 1개 감소구간을 뒤집으면 오름차순이 될 수도 있음 iii) 감소구간이 2개 이상 배열이 오름차순이 될 수 없다 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
-
189-A, *1300코드포스 2021. 7. 27. 21:20
Problem - 189A - Codeforces codeforces.com 문제 세 정수 $a,\ b,\ c(1 \leq a,\ b,\ c \leq 4000)$가 주어진다 길이가 $n(1 \leq n \leq 4000)$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수는? $O(n)$ $DP_{i}$를 길이가 $i$인 끈을 길이 $a,\ b,\ c$로만 자를 때 나오는 조각의 최대 개수라고 하자. 그러면 $$\mathrm{DP_{i}=max(DP_{i-a},\ DP_{i-b},\ DP_{i-c})+1},\ \mathrm{Not\ all\ of\ DP_{i-a},\ Dp_{i-b},\ Dp_{i-c}=0}$$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..
-
230-B, *1300코드포스 2021. 7. 27. 16:11
Problem - 230B - Codeforces codeforces.com 문제 답을 $n(1 \leq n \leq 10^{5})$번 출력한다 $x(1 \leq x \leq 10^{12})$가 주어졌을 때, $x$의 양의 약수가 3개인가? $O(\sqrt{x}+nlog\ x)$ 양의 약수가 3개인 수는 $$p^{2},\ \mathrm{p\ is\ prime}$$꼴의 수이다 먼저, 에라토스테네스의 체(sieve of eratosthenes)를 이용하여 소수를 구하고 $O(\sqrt{x}log\ log\ \sqrt{x}) \approx O(\sqrt{x})$ 이 소수를 set 에 저장한다 $O(log\ \pi(\sqrt{x})!) \approx O(\sqrt{x})$ 이제 수들이 주어질 때마다 i) 완전제..
-
4-C, *1300코드포스 2021. 7. 25. 15:09
Problem - 4C - Codeforces codeforces.com 문제 $n(1\leq n \leq 10^{5})$번 32자 이하의 알파벳 소문자로 이루어진 이름이 주어진다 처음보는 이름은 "OK", $k$번 본 이름은 "준_이름$k$" 를 출력한다 $O(nlog\ n)$ 정도의 알고리즘은 통과 가능하다 $O(nlog\ n)$ map을 이용하여 이름을 저장한다 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 "\n" using namespace std; map m; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.ti..