본문 바로가기

전체 글36

CF 1741F https://codeforces.com/contest/1741/problem/F Problem - F - Codeforces codeforces.com 어떤 막대기 a, b가 있을 때 거리가 max(0, a.l - b.r) 로 구해지는 경우를 생각해보자. 막대기 a에 대해 b.l 2022. 10. 26.
CF 1715C https://codeforces.com/contest/1715/problem/C Problem - C - Codeforces codeforces.com 머리가 안돌아가서 그냥 관찰로 대충 찍어맞췄는데 그마저도 푸는데 거의 1시간 걸림. 전체 g 구하는 방법: 1, 1, 2, 2, 2, 3, 3 이 있으면 [1, 1] + [2, 2, 2] + [3, 3] 이렇게 같은 수들 묶음 사이에 +가 있다 생각하고 각 +마다 +를 포함하는 구간의 개수를 세면 된다. 거기에 nC2를 더하면 된다. 왜 이게 되냐면 배열의 모든 원소가 같을 경우에 g의 합이 nC2다.(모든 구간에서 g가 1이므로) 그리고 어떤 구간이 +를 하나 포함할 때마다 그 구간에 해당하는 g는 1씩 증가하기 때문이다. 이제 쿼리가 들어올 때 마다.. 2022. 10. 26.
CF 1720D1 https://codeforces.com/contest/1720/problem/D1 Problem - D1 - Codeforces codeforces.com a[i]가 200이하라길래 대충 2차원 dp거나 뭐 200개 관리하는 쪽으로만 생각하다가 못풀었다. xor연산에 대한 관찰이 더 필요했다. arr[i] xor j 는 j를 최대 200까지만 바꿀 수 있다. 반대로도 마찬가지. 따라서 dp[i] = max(dp[i - 400] ~ dp[i-1]) + 1 인데 사실 i - 255까지만 봐도 된다. 왜냐하면 i - 256 이하의 숫자들은 뒤에서 7번째 이상의 비트들만 놓고 봤을 때 이미 i보다 작다. 근데 200은 뒤에서부터 7개 비트만 건드리므로 뭘 해도 i보다 커질 수가 없기 때문이다. 2022. 10. 23.
CF 1736C2 https://codeforces.com/contest/1736/problem/C2 Problem - C2 - Codeforces codeforces.com 2400짜리 문제...너무 어렵다. C1에서 dp[i] = min(arr[i], dp[i - 1] + 1) 인 것은 쉽게 알 수 있다. 먼저 모든 i에 대해 track[i](dp[i] = arr[i]라고 가정했을 때 [i, N] 구간 dp 합) 를 전처리 해 둔다. dp에 대한 psum도 전처리를 해 준다. 이제 쿼리를 구해보자. dp'를 arr[p] = x 가 됐을 때 p부터의 dp라고 했을 때 dp'[q] = arr[q]인 가장 작은 q를 찾는다.(p < q = arr[j] - j를 구할 때 set에서 찾고 set에 i를 집어넣는다. set에 저.. 2022. 10. 22.

티스토리툴바