hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [18116] 로봇 조립 (Gold IV) 더보기 의도한 태그: Union-Find (Easy) 'I a b'의 쿼리는 그냥 union으로 처리하면 됩니다. 'Q c'도 find가 쓰이는 것 같은데, 부품의 개수까지 알아내야 합니다. 부품의 개수 = 집합의 크기 이고, 집합의 크기는 모두 1인 상태로 시작해서 union을 할 때마다 합쳐지는 두 집합의 크기의 합을 새로 저장해주면 됩니다. const int N = 1000000; int par[1000020], siz[1000020]; int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); } void uni(int a, int b){ int pa = fnd(a), pb ..

1. [22971] 증가하는 부분 수열의 개수 (Silver II) 더보기 의도한 태그: Longest Increasing Subsequence \( D_{i} = A_{i} \)로 끝나는 LIS의 개수를 정의하면, 점화식은 아래와 같이 적어볼 수 있습니다. \( j > n; for (int i = 1; i > arr[i]; } for (int i = 1; i = arr[i]){ continue; } dp[i] += dp[j]; dp[i] %= mod; } } ..

1. [13549] 숨바꼭질 3 (Gold V) 더보기 의도한 태그: Dijkstra (Easy) 정점은 그냥 좌표고, 간선은 문제에서 충분히 자세히 알려주고 있습니다. 탐색 범위를 넉넉하게 잡는 걸 추천합니다. 저는 자세한 생각하기 귀찮아서 목적지에 2를 곱한 \( 200\,000 \)으로 잡았습니다. const ll INF = 0x3f3f3f3f3f3f3f3f; ll dis[200020]; ll djk(int st, int ed){ memset(dis, 0x3f, sizeof(dis)); dis[st] = 0; priority_stack pq; pq.push({0, st}); while (!pq.empty()){ int now = pq.top().sc; ll dst = pq.top().fr; pq.p..

1. [19699] 소-난다! (Silver II) 더보기 의도한 태그: Backtracking (Easy) 소들을 선택하는 경우의 수는 \( {}_{N}C_{M} \)가지가 됩니다. 제한이 \( 1 \le M \le N \le 9 \)니, 조합의 식에서 분모를 아예 무시해도 \( 9! = 362 880 \)이라는, 충분히 작은 값이 나옵니다. 그러니, 이 경우들을 다 돌려보면 됩니다. const int N = 9000; bool pr[9020]; int n, m; int arr[10]; vector ans; void btk(int idx, int cnt, int sum){ if (idx > n){ if (cnt == m){ if (pr[sum]){ ans.push_back(sum); } } return..

A. [23238] Best Student (Diamond V) 더보기 의도한 태그: Mo's Algorithm + Square Root Decomposition 문제를 간단히 해석하자면, \( [L, R] \) 구간에서 가장 많이 등장한 학생을 찾는 문제가 됩니다. 그러니 Mo's를 사용하면 간단히 해결할 수 있겠죠. 그런데, 가장 많이 등장한 학생을 찾을 때 "등장 횟수"를 Segment Tree 같은 걸로 저장시키면 시간복잡도에 log가 붙으면서 TLE가 나게 됩니다. 그러니, "등장 횟수"의 개수를 Square Root Decomposition으로 관리해주면 됩니다. Square Root Decomposition의 시간 복잡도는 Mo's와 독립적으로 계산되므로, 합하면 \( O(Q \sqrt(N)..

다룬 태그들 더보기 구간 나눠서 처리하기 (A) Square Root Decomposition (BC) Mo's Algorithm (DEF) A. [20537] Gap (Platinum III) 더보기 Subtask 1은 간단히 해결할 수 있습니다. \( a = 0, b = 10^{18} \)으로 놓은 뒤, \( f(a, b) \)를 호출하면 가장 작은 수와 가장 큰 수를 알 수 있게 됩니다. 그럼 그 가장 작은 수와 가장 큰 수를 제외하고 남은 \( N-2 \)개의 수에 대해 재귀적으로 탐색해주면 됩니다. 이는 \( a = mn+1, b = mx-1 \)로 범위를 조정시키면 됩니다. 그럼 배열의 모든 원소를 알 수 있게 되므로, 문제를 간단히 해결할 수 있습니다. Subtask 2는 아래와 같이 해결할..

다룬 태그 더보기 Trie (ABCDEF) A. [14725] 개미굴 (Gold III) 더보기 트라이를 구축하는 문제입니다. 차이점이라면, 문자열에서 하나의 글자를 들고 오는 대신 문자열의 배열에서 하나의 문자열을 꺼내서 쓰는 정도의 차이가 있습니다. (사실 이 문제는 트라이 없이도 풀 수 있습니다. 그래서 Gold III이라는 낮은 난이도를 받은 거고요.) struct Node{ map nxt; }; vector trie; void psh(int ni, vector& v, int vi){ int vl = v.size(); if (vi == vl){ return; } if (trie[ni].nxt.count(v[vi]) == 0){ trie[ni].nxt[ v[vi] ] = trie.size(); tr..

1. [2217] 로프 (Silver IV) 더보기 의도한 태그: Greedy (Easy) 만약 로프를 \( c \)개 쓸 거라면, 자명하게 가장 강한 \( c \)개의 로프를 써야 합니다. 그리고, 그 때 들 수 있는 중량은 \( c \times \min(A_{1}, A_{2}, \ldots, A_{c}) \)가 됩니다. 만약 로프의 강도가 (큰 게 먼저 오도록) 정렬되어있다면, 답은 \( c \times A_{c} \)가 됩니다. 그러니, \( c \)를 \( 1 \)부터 \( N \)까지 다 돌려주면서 답을 찾으면 됩니다. 2. [2630] 색종이 만들기 (Silver II) 더보기 의도한 태그: Divide and Conquer (Easy) 현재 크기의 색종이를 보면서, 한 가지 색깔로만 칠해졌다..