상위 99.99%의 PS

이틀 뒤 UCPC다. 내일은 브론즈 하나만 풀고 잘 듯 BOJ 25223 - Reset (P5) 더보기 이분 탐색을 하면 된다. research를 어떤 task에 해야 하는지에 대한 아이디어를 떠올리는게 힘들었다. 필요한 리셋 횟수가 k일 이상이라면, 이 일을 어려운 일이라고 하자. 일단, 쉬운 일과 어려운 일들을 어떻게 해도 k일 내에(리셋은 k-1회) 끝낼 수 없다면 불가능한 경우이다. 그리고 k-1번의 리셋을 하고, 마지막 k번째 날에 해야하는 어려운 일의 시간들의 합이 c보다 크다면 불가능하다. 아니라면 가능함 BOJ 16225 - 제271회 웰노운컵 (D5) 더보기 B에 대해 정렬하면, 맨 왼쪽은 내가 항상 가져가게 된다. 인덱스가 작은 곳부터 2칸씩 늘리면서, 지금까지 본 것들 중 가장 A값이..

자다 깨서 비몽사몽했다.. A (00:02) 무지성 O(N^2) B (00:21) k > 1일때는, 어떻게 연산을 하더라도 too tall한 element의 개수가 변하지 않는다. k = 1일때는, \(\lfloor{\frac{(N-1)}{2}}\rfloor\)이 답이다. 원하는대로 추가가 가능하기 때문 C (01:12) 인성 개터진 case work. D (00:46) A의 길이가 홀수인 구간 \([l, r]\)에서, \(l\leq x \leq r\)인 수가 홀수 개 존재한다면, 이 구간 안에 우리가 원하는 답이 존재한다. 이분 탐색을 통해 15(\(

3일 정도 대충해서(브실 풀었음) 그 날짜가 삭제되었다. ucpc 전까지 빡공 해야겠다! BOJ 14899 - 수열과 쿼리 19 (D1) 더보기 Segment Tree Beats 문제다. min/d와 max/d가 같을 때, min/d + 1 == max/d일 때 레이지를 보내면 된다. BOJ 16367 - TV Show Game (P3) 더보기 R = true, B = false로 두면 2-sat이 마려워진다. 3개 중 2개가 성립해야 하므로, \((A or B) and (B or C) and (C or A)\)가 된다. 이 뒤는 쉽다. BOJ 16366 - Starwars (P4) 더보기 pair bfs 문제이다. 지문 길이가 ㅋㅋ;; BOJ 10464 - XOR (G4) 더보기 1부터 N까지의 모든 ..

퍼플 확정. 그러나 D번을 못 푼 것은 좀 슬프다. A (00:03) z | A_i의 최대를 구하면 된다. B (00:08) 답은 0, 1, 2 중 하나이다. C (00:29) m^p * q 꼴을 p, q의 pair로 묶어서 q가 같은 연속된 구간을 합쳐준다. D (--.--) 업솔빙했다. 1의 위치에서부터, 왼쪽 오른쪽으로 각각 가장 멀리 가주면 된다. E (01:03) D를 보다가 넘어가서 10분만에 풀었다. Hockey-stick identity를 사용하는 문제. E번이 이렇게 쉬울 줄은 몰랐다. DE 둘다 *2000인데 난이도 차이가 꽤 크게 느껴지기도 했고, 내가 D번같은 유형에 정말정말 약하다... 다음은 오렌지.. div. 2 only에서 날먹하면서 올라가면 될 듯?

https://codeforces.com/contest/1700 Dashboard - Codeforces Round #802 (Div. 2) - Codeforces codeforces.com 올라가자.. A (00:02) 오른쪽 끝까지 이동 -> 그대로 아래로 쭉 이동 B (00:15) 앞자리가 9인 경우: 11111111 (자리수 + 1) 앞자리가 9가 아닌 경우: 99999999 C (00:25) 왼쪽부터 진행해도 최적이다. \(A_i\)와 \(A_{i+1}\)의 대소관계에 유의하여 풀면 된다. D (01:10) 열린 파이프의 개수를 k라고 하자. (sum(A) / k)를 올림한 값이 곧 걸리는 시간이다. 이분 탐색이 마려워진다.그러나, 4 1 1 1 1이고, 열린 파이프의 개수가 4인 경우는, 2초..

결과가 마음에 안 든다. A (00:03) 010101....꼴로 만들고, 남은 수는 오른쪽에 다 몰면 된다. B (00:20) '10' 또는 '01'꼴이 있다면, 그 왼쪽의 숫자들은 모두 없앨 수 있다. 그러니까 저 형태일 때 인덱스를 ans에 더해주면 된다. C (00:30) 합이 0이 아닐 때, sum[1:k] 0일 때는 불가능하다. 그리고, 합이 sum[1:k] < 0인 모든 k(i

어제부터 시험이 시작됐지만 ps는 해야지.. BOJ 17429 - 국제 메시 기구 (D4) 더보기 Euler Tour + HLD + Lazy Segtree. 구현 양이 너무 많아서 티어가 높아졌다. 오일러 투어를 할 때, 무거운 정점 우선으로 내려가서 numbering을 해 주고, HLD를 했기 때문에 경로에 대한 update와 sum은 빠른 시간에 구할 수 있다. BOJ 10350 - 은행 (R5) 더보기 (음수가 되는 구간합) / (전체 구간합) 의 올림의 합이 답이다. 시간 제한이 5초라서 \(O(N^2)\)가 가능하다. 실수로 알고리즘 분류를 봐서 쉽게 풀렸다.. BOJ 16680 - 안수빈수 (P5) 더보기 \(x *(1e9 - 1)\) BOJ 18185, 18186 - 라면 사기 (D4) 더보..

https://codeforces.com/contest/1697 Dashboard - Educational Codeforces Round 130 (Rated for Div. 2) - Codeforces codeforces.com 아직도 민트로 떨어진게 웃기다. 퍼플 등반 다시 가자.. A (00:02) \(sum(a) - m\) B (00:05) 배열을 내림차순으로 정렬하고 누적합 배열 p를 만들자. \(p[y] - p[x]\)가 답이다. C (00:26) +1 s에서 등장하는 알파벳, t에서 등장하는 알파벳을 각각 세고, 같아지는 순간이 올 때마다 확인하면 된다. 그냥 구현 문제다. D (01:39) +1 풀이 쓰기 너무 귀찮다. 이분탐색을 돌리면 된다.

들어가기 전에, 코드는 파이썬으로 작성했으니 참고했으면 좋겠다. 어자피 작동 원리는 같으니 문제는 안 된다. https://www.acmicpc.net/problem/16911 16911번: 그래프와 쿼리 첫째 줄에 정점의 개수 N(2 ≤ N ≤ 100,000)과 쿼리의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제를 풀어보자. 처음에는 어떤 두 정점도 연결되지 않은 상태이고, 다음 쿼리들을 수행하는 문제이다. 1번 쿼리: 두 정점을 연결하는 간선을 추가한다. 2번 쿼리: 두 정점을 연결하는 간선을 제거한다. 3번 쿼리: 정점 u에서 v로 가는 경로의 존재 여부를 출력한다. 2번 쿼리가 없다면, 단순하게..

과제때문에 쉬엄쉬엄 풀었다. 곧 시험이기도 한데, 공부는 안 할 예정 BOJ 21607 - Polynomial and Easy Queries 더보기 \(f\)와 \(g\)를 왜 굳이 저걸 준 것인지를 생각하며 노트에서 놀다보면, \(f(g(x)) = g(f(x))\)임을 알 수 있다. 자신에 대해 f, g를 합성했을 때의 값을 각각 sparse table에 저장하고, update쿼리에서는 뿌려진 f와 g를 레이지 세그로 각각 저장하면 된다. BOJ 17353 - 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 더보기 \(B_i = A_i - A_{i-1}\)이라고 정의하면, B에서 구간 \([l, r]\)에 1을 더해주고, \(B_{r+1}\)에는 구간의 크기를 빼주면 된다. 그리고 \(A_k\)..