상위 99.99%의 PS

백준을 요즘 대충하는 관계로 문제가 느리게 쌓였다. 게임을 줄여야 하는데... BOJ 16854 - 편안한 문자열 (G2) 더보기 "()))((()" 같은 대칭 여부, 올바른 괄호 문자열 여부를 확인하면 된다. 무지성 N^2. BOJ 16853 - 필름 (P3) 더보기 각 단색광은 독립적이기 때문에, 빨파초 3개를 각각 처리해주어 2-sat을 하면 된다. BOJ 25323 - 수 정렬하기, 근데 이제 제곱수를 곁들인 (G1) 더보기 정렬 후를 B라고 하면, A_i * B_i가 제곱수여야 정렬 가능한 형태가 된다. BOJ 16855 - 일해라, 류트! (P4) 더보기 r의 범위가 작으므로, 가능한 모든 순서쌍 \((r_i, r_{i+1})\)에 대해 전처리가 가능하다. 이를 통해 i번째의 약물을 언제 넣어..

https://www.acmicpc.net/problem/25213 25213번: 조각 케이크 (Hard) 조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다. 답이 매우 커질 수 있으므로, \(10^9+7\)로 나눈 나머지를 출력한다. www.acmicpc.net [알고리즘 분류] Meet in the Middle Combinatorics Prefix Sum Meet in the Middle을 공부하고 풀어본 문제다. 몇 가지 관찰이 필요하다. 1. lcm(2~25)는 그렇게 크지 않으므로, 분모를 통일할 수 있다. (계산이 편해진다.) 2. 모든 크기의 조각들이 무한히 존재할 때, 이들을 잘 모아 케이크 한 판으로 만들기 위해서는 많아봤자..

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

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까지의 모든 ..

어제부터 시험이 시작됐지만 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) 더보..

과제때문에 쉬엄쉬엄 풀었다. 곧 시험이기도 한데, 공부는 안 할 예정 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\)..

6월 1일에 더 문제를 풀 생각이 없었는데 dong_gas의 문제 추천 세례를 받고 과솔빙을 했다..ㅎ 덕분에 문제들이 순식간에 쌓였다 BOJ 24654 - Build The Grid (G2) 더보기 달팽이처럼 빙글뱅글 돌리면 된다 BOJ 2041 - 숫자채우기 (D5) 더보기 이게 왜 다5인지 모르겠다. 가로를 +1, -2, +3, -4, ... 로 채우고, 세로는 역순으로 채우면 된다. BOJ 19217 - Jitterbug (D3) 더보기 두 그룹으로 나누어보자. 한 쪽 정점 100개 그룹은 모든 정점끼리 연결하고, 나머지는 일자로 만들면 된다. 이 둘을 잇기만 하면 된다. BOJ 21099 - Four XOR (P5) 더보기 두 값을 XOR한 값은 많아봤자 2^17개이다. 비둘기집 원리에 따라서 ..

다행히도 요즘은 스트레스를 덜 받나보다. 어제 코포 레이팅을 -50정도 받았는데도 화가 안났다. 오늘부터 플3~다5 랜덤디펜스를 시작했다. 마지막 두 문제는 오늘 푼 것임 BOJ 17473 - 수열과 쿼리 25 (R5) 더보기 세그비츠 문제다. 이 글로 풀이를 대체함 BOJ 2268 - 수들의 합 7 (G1) 더보기 세그트리 슈퍼기초문제다. \(i > j\)인 쿼리가 들어올 수 있음에 유의하면 된다. BOJ 17476 - 수열과 쿼리 28 (D1) 더보기 세그비츠 활용문제다. 제곱근 값은 빠르게 감소하는 특징이 있으므로 같은 값을 가지는 리프노드들이 많아지게 된다. 그러나 \([100, 99, 100, 99, ...]\)와 같은 경우에서, 제곱근 연산과 전체 구간 \(+90\)이 번갈아 들어오는 경우가 ..

주식회사 승범이네를 제외한 7문제. 그냥 6문제정도 쌓일 때마다 글을 올려야겠다. 귀찮아질 것 같아서... BOJ 16679 - Back to the Bones (P5) 더보기 전처리 dp 문제이다. \(dp[i][k] = \)(i번째에서 주사위들의 눈의 합이 k가 나오는 경우의 수)라고 정의해보자. 주사위 \(x\)개를 다시 굴린다고 하면 눈이 가장 작게 나온 것들을 굴리는 것이 무조건 이득이다. 즉, y=(얻어야 하는 수)로 정의하면, \(dp[x][y]\)를 활용해 주사위를 몇 개 굴리는 것이 최적인지를 찾아내면 된다. 따라서 각 쿼리마다 \(O(N^2)\)에 해결할 수 있고, 전체 시간복잡도는 \(O(N^3)\)이다. BOJ 12844 - XOR (P3) 더보기 레이지 세그 활용문제이다. 홀수/짝..

https://www.acmicpc.net/problem/16404 16404번: 주식회사 승범이네 첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판 www.acmicpc.net [알고리즘 분류] Segment Tree (with lazy propagation) Euler Tour Technique 오일러 경로 테크닉이라는걸 배우고, 기초문제를 풀어보았다. 오일러 경로 테크닉은 루트가 있는 트리에서 어떤 정점의 서브트리에 속하는 정점들을 연속된 수로 renumbering할 수 있는 기술이다. 일단 나는 이렇게 이해했고, 이 문제는..