결국 오고야 마는 것들

끔찍한 구현 문제. 최대 깊이가 10이기 때문에 총 경우의 수가 410으로 완전탐색으로 풀 수 있다. 물론 캐쉬를 적용하면 훨씬 빨리 답을 구해낸다. #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}; struct state { pii R, B; int d; state(pii r, pii b, int dd) {R = r, B = b, d ..

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

심금을 울리는 제목... 경로에서 남-남 혹은 여-여 경로를 제외하고 크루스칼을 돌리고 연결된 노드의 수가 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}; vector adj; int parent[1..

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

sds 알고리즘 특강을 들으면서 풀었다. 여기서 만든 parent 배열을 채우는 기법을 sparse table이라고 하는 것 같던데, 어떻게 이런 생각을 해냈는지 놀라울 뿐이다... log(n)으로 n번째 부모를 빠르게 찾는게 핵심인 것 같다. 세그먼트 트리도 그렇고 컴퓨터에서 2의 힘이란 정말... #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, -..

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

lca 응용 문제. sparse table로 2의 지수승의 부모 노드를 저장했듯 최솟값과 최댓값 배열을 만들어서 저장하면 된다. 이 문제를 풀면서 lca와 sparse table을 좀 더 이해한 것 같아서 기분이 좋다!@ #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 = 17; vector adj[100001];..

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

문제가 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