결국 오고야 마는 것들

문제가 lis랑 비슷하게 생겼는데, 곰곰이 생각해보니 Counting Inversions 문제와 유사한 문제였다. 다른 점은 한 정점에서 여러개의 간선이 생길 수 있다는 것? 1번 정점부터 n번 정점까지, 간선이 빠른 순서로 query를 날리고 넣어주면 된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1..

혼내주기 2021. 7. 21. 12:16

온도가 0부터 216이기 때문에 리프 노드가 온도인 세그 트리를 만들고 k개를 유지하면서 (k+1)/2번째 수를 찾는 쿼리를 날리면 된다. 매번 삭제와 추가를 반복해도 어차피 모든 연산이 O(log(n))이기 때문에 충분히 가능하다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 K; for(int i =..

혼내주기 2021. 7. 21. 12:15

아직 익숙하지 않아서 그런지, 아님 그냥 잔실수가 많아서 그런지 디버깅 하는데 많은 시간을 보냈다... 별도의 캔디 배열에 2i번 올라갈 때 마주치는 모든 캔디를 비트마스크로 저장해놓고 lca를 찾을 때 경로의 모든 캔디를 OR 연산한 뒤 쿼리로 필요한 캔디가 있는지 확인하면 된다. 번외로 질문 게시판에 반례가 없는 문제를 몇개 풀다보니 반례를 생각해보는 시간이 많아져서 강제로 실력이 느는 기분이다 ㅋㅋ. 역시 습관적 반례 검색은 실력에 도움이 안된다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begi..

혼내주기 2021. 7. 21. 12:14

방향 그래프에서 플로이드를 돌리면 a가 b보다 먼저 일어났는지 확인할 수 있다. adj[a][b]의 값이 1이면 a가 먼저 일어난 것이고 adj[b][a]의 값이 1이면 b가 먼저 일어난 것이다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; bool adj[401][401]; int n, K, s; void input() { cin..

혼내주기 2021. 7. 21. 12:13

다잌으로 모든 최단 경로를 찾고(길이가 같은 여러개의 최단 경로가 있을수도 있음) 그 경로들을 지운다음 나머지 경로들로 최단 경로를 찾으면 된다. 삽질했던 포인트: 1. 길이가 같은 여러개의 최단 경로를 생각 못함 2. pq에 거리가 같은 경우는 경로만 넣어야 하는데 중복되는 간선을 넣음 (주석으로 표시) 3. 경로를 제거할때 사이클이 있는 경우가 있어서 visited 배열로 중복 방문을 막았어야 함 공식 사이트에 있는 TC로 체크해서 답이 맞는데도 시간초과가 나와서 굉장히 헤맸다... 결국 8트만에 성공... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using ..

혼내주기 2021. 7. 21. 12:12

lis. 개인적으로 이분 탐색보다 세그먼트 트리가 더 이해하기 쉬운 것 같다. 2개의 element를 정렬해서 갯수세는 세그먼트 트리 문제들이 재미있는듯. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 a; arr[i] = {a, i}; } } int query(int l, int r, int i = 1,..

혼내주기 2021. 7. 21. 12:08

꼬인것만 보고 lis인 줄 알았는데 알고보니 inversion counting이었다. 롱롱이도 안써서 또 삽질. 문제를 꼼꼼히 읽는 습관... 문제를 꼼꼼히 읽는 습관... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; using pii = pair; #define all(v) v.begin(), v.end() int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1}; int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1}; const int N = 1 a; idx[a] = i+1; } for(int i = 0; i < n; ++i) { ..

혼내주기 2021. 7. 21. 11:00

구간의 맨 왼쪽 전구 색을 c라고 하면, [l,r]구간을 c로 통일시키는 최소 횟수를 구하려고 했다. 그래서 구간을 색 c와 c가 아닌 구간으로 나눠서 재귀적으로 c가 아닌 구간들의 값을 구해서 더하려고 했는데 삽질을 아주 오래 하고 안풀렸다... 결국 sds 특강 강사님의 설명을 듣고 풀었다. 굳이 색에 집착하지 않아도 되었던 것, 그리고 구간을 나누는 것도 n이 200이기 때문에 다 해봐도 되는 것이었다... 아이디어가 완벽하진 않았지만 큰 흐름은 잡았다는데 위안을 삼고 있다 ㅠ dp는 역시 어렵다. 심지어 KOI 초등학교 문제다. 나는 언제쯤 초등학교를 졸업할 수 있을까? #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using names..

혼내주기 2021. 7. 21. 10:55