목록PS (14)
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$축순으로 정렬한다면, 기존..
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 사용 알고리즘 : 오프라인 쿼리 / 세그멘트 트리 오프라인 쿼리는 뭔가 거부감이 들고 남자라면 응당 온라인 쿼리로 풀어야지(?) 라는 생각이 있었..
문제 링크 atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c C - Cell Inversion AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 관찰 1) (a, b) (c, d)와 (a, d) (b, c)의 효과는 같다. 관찰 2) S가 주어진다면, 그 S에서 화살표의 왼 부분이 될 문자들과, 오른 부분들이 될 문자들은 이미 정해져있다. index가 짝수번째이면서 B이거나, 홀수번째이면서 W이면 언제나 화살표의 왼쪽이 배정되고 (괄호문자열의 "(") 반대 경우는 언제나 화살표..
문제 링크 : www.acmicpc.net/problem/18535 사용 알고리즘 : DSU, 구현 관찰) G 위치 두 곳에 가고일이 있다고 해보자. 두 가고일은 서로 거울에 의해 보일 수 있는 위치에 놓여있다. 이 떄, 한 가고일을 특정 방향으로 고정시키면, 다른 가고일의 방향도 무조건 고정되는 것을 알 수 있다. (그렇지 않으면 한 가고일이 다른 가고일의 옆면을 보게 된다.) 이는 가고일이 두마리가 아니라 여러마리여도 확장할 수 있는 개념이다. 서로 거울로, 혹은 그냥 공기로 연결된 가고일들끼리는, 한 가고일의 방향만 결정해주면 나머지 가고일의 방향은 자동으로 결정된다는 것이다. 따라서 연결된 가고일끼리 DSU로 부모를 같게 해준 뒤, 원래 orientation에서 바뀌는 정도의 cost를 계산해 주..