목록전체 글 (51)
PS 부수기
$maxdate[s]=$ $s$일날 김치를 넣었을 때 최대의 김치싸대기를 날릴 수 있는, 김치를 빼는 날짜 $e$ $res(s,e)=$ $s$일날 김치를 넣고, $e$일날 김치를 뺐을 때 날리는 김치싸대기의 힘 그러면 정의에 따라 $res(s,e) = (e-s) \times t[e] + b[s]$이고, $s$를 고정시킨다면 가능한 모든 $res(s,e)$값 중 $res(s,maxdate[s])$가 제일 클 것이다. 우리는 각 $s$ 시작일 마다 $res(s,maxdate[s])$값을 찾아주고 그들 중 최댓값을 구하면 된다. 그 전에, 우리는 다음 식을 증명할 수 있다. $maxdate[s] \leq maxdate[s+1]$ 즉, 김치를 나중에 넣는다면, 최적의 빼는 날 $maxdate$가 김치를 일찍 넣..
우리는 $a_x$~$a_y$의 구간 gcd를 다음과 같이 나타낼 수 있다. $gcd(a_x, a_{x+1}, a_{x+2}, ... , a_y)$ $=gcd(a_x, a_{x+1}-a_x, a_{x+2}-a_{x+1}, ..., a_y-a_{y-1})$ 여기서 우리는 $a_k-a_{k-1}$꼴의 항들과 $a_k$꼴의 항 2가지를 세그먼트 트리를 이용해 관리할 수 있다. 만약 $a_2$~$a_4$ 구간에 range update $+k$가 일어났다고 가정해보자. $a_k-a_{k-1}$꼴의 항들의 변화이다. $((a_2 + k) -a_1, (a_3 + k) -(a_2+k), (a_4+k)-(a_3+k), a_5-(a_4+k)..., a_n-a_{n-1})$ $=(k+a_2-a_1, a_3-a_2, a_4-a..
유형이 비슷하고, 자주 나오는 것 같아서 같은 곳에 풀이를 적습니다. 이 유형의 문제들에서는, 보통 2개 (혹은 그 이상)의 축이 나오고, 대소관계를 비교하는 쿼리를 해결해야합니다. 한 축을 정렬하여 한쪽의 대소관계를 강제한 뒤, 다른 축을 순차적으로 업데이트 해 쿼리를 해결할 수 있습니다. 1. 북서풍 https://www.acmicpc.net/problem/5419 5419번: 북서풍 각 테스트 케이스에 대해서, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 출력한다. www.acmicpc.net 이 유형의 가장 간단한 버젼입니다. 문제를 간단히 요약하면, 2차원 평면에 섬들이 놓여있습니다. 여기서 우리는 각 섬에서 북서쪽에 있는 섬들의 갯수 합을 구하면 됩니다. 섬을 $x$축순으로 정렬한다면, 기존..
Naive solution 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 int main() { IOS; ll ans=0; clock_t st, en; st=clock(); for(int i1=1;i1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int main() { IOS; long double x = 2; int cnt=0; for(long double k=0 ; ; k++) { long double l=(k+log10(123))/(log10(2)); long double r=(k+log10(124))/(log10(2)); int il = (int)l+1; int ir = (int)r; for(int t=il;t
A. 서로 신고하는 문제 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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include using namespace std; #define IOS ios::sync_with_stdio(false);cin.tie(0) #define all(x) x.begin(), x.end() #define ff first #define ss second #define LLINF 0x3f3f3f3f3f3f3f3f #define INF 0x3f3f3f3f #define uniq(x) sort(a..
문제 링크 : https://www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무를 마친 키파는 버거운 직장에서 벗어나 새로운 직업에 도전하고자 햄버거집을 차렸다. 키파는 케이크를 여러 차례 만들면서 빵은 좀 구워 봤지만 햄버거를 만드는 것 www.acmicpc.net 문제 해석 괄호 문자열이 주어진다. 1. 쿼리 1번을 시행시, l ~ r번째 괄호 문자열을 뒤집는다. 2. 쿼리 2번을 시행시, l ~ r번째 괄호 문자열이 올바른 괄호 문자열이 되도록 추가하는 괄호의 최소 갯수를 구한다. 문제 풀이 "("은 1로, ")"은 -1로 해석해보자. 올바른 괄호 문자열이 되려면, 1과 -1로 이루어진 수열 안에서 Minimum prefix sum이 음수가 아니..
문제링크 www.acmicpc.net/problem/20681 20681번: Black Family Tree The first line of the input contains two integers n and q (2 ⩽ n ⩽ 105, 1 ⩽ q ⩽ 105). The second line contains n space-separated integers c1 to cn (0 ⩽ ci ⩽ 104). The third line contains n−1 integers p2 to pn (1 ⩽ pi < i). Each of the next www.acmicpc.net 사용 알고리즘 : 오프라인 쿼리 / 세그멘트 트리 오프라인 쿼리는 뭔가 거부감이 들고 남자라면 응당 온라인 쿼리로 풀어야지(?) 라는 생각이 있었..