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

다뤄본 태그 더보기 Euler Tour Technique (ABCDE) A. [2820] 자동차 공장 (Platinum III) 더보기 Subtree Add Update와 Point Query입니다. Euler Tour Technique를 사용하면 우리가 잘 풀 수 있는 형태인 Range Add Update와 Point Query로 바꿀 수 있습니다. 아래 쓰인 코드는 Difference 배열을 사용해서 Range Update / Point Query를 Point Update / Range Query로 바꾼 방식입니다. 이에 관해 간단히 설명해보자면 \( D_{i} = A_{i} - A_{i-1} \)을 정의한다면, \( A_{i} = \sum_{j=1}^{i} D_{i} \)가 됩니다. 그럼, \( D..

다룬 태그들 더보기 Sparse Table (ABC) Lowest Common Ancestor (DEFG) A. [17435] 합성함수와 쿼리 (Gold I) 더보기 \( f^N(x) \)는 \( f^1(x), f^2(x), f^4(x), \ldots, f^{2^k}(x) \)의 적절한 합성으로 만들 수 있습니다. 그러니, Exponentiation by Squaring 하듯이 전처리를 돌리고 쿼리를 처리해주면 됩니다. const int B = 20; int spr[22][200020]; void Main(){ int n; cin >> n; for (int i = 1; i > spr[0][i]; } for (int b = 1; b q; while (q--){ int k, x; cin >> k >> x; ..

A. [20039] Coronavirus Trend (Platinum II) 더보기 의도한 태그: Segment Tree + DP 우선, 두 수의 차이를 계산해야 하니 길이가 \( N - 1 \) 차이 배열 \( D_{i} = A_{i+1} - A_{i} \)을 만들어볼 수 있습니다. 이를 통해 문제를 재정의하면, Difference 배열에서 값을 적절히 합쳐서 고립된 +, -가 없도록 만드는 문제가 됩니다. (문제의 조건에 의해, 0은 고려하지 않아도 됩니다.) 이제, DP로 이 문제를 풀어봅시다. \( DP_{i, s, c} := A_{[1, i]} \)에 대해, 마지막 수의 부호가 \( s \)이며, 이 부호가 현재 \( c \)회 연속으로 나오게 하기 위해 필요한 합치기의 최소 횟수 문제 특성상,..

다룬 태그들 더보기 세그먼트 트리의 수열 직접 정의해보기 (ABCD) 2-Dimensional Segment Tree (EF) Kth Segment Tree (GH) Merge Sort Tree (IJ) Continuous Sum Segment Tree (KL) A. [10090] Counting Inversions (Platinum V) 더보기 Inversion을 좀 더 명확히 정의하면, \( i A_{j} \)인 \( (i, j) \) 쌍을 의미합니다. 그럼 우리가 \( j \)를 기준으로 돌리면서 앞에 나온 값들 중 \( A_{j} \)보다 더 큰 값의 개수를 찾아주면 됩니다. 그래서 \( B_{x} := \) \( A_{j} = x \)인 \( j < i \)..

다룬 태그 더보기 Segment Tree (ABCDEFG) Segment Tree with Lazy Propagation (HIJKLM) A. [2042] 구간 합 구하기 (Gold I) 더보기 세그먼트 트리의 기본형 문제입니다. 어떤 원소의 업데이트와, 구간의 합을 처리해주면 됩니다. const int N = 1048576; ll seg[2097160]; void upd(int pos, ll val){ pos += N-1; seg[pos] = val; pos >>= 1; while (pos){ seg[pos] = seg[pos= 1; ed >>= 1; } return res; } void Main(){ int n, m, k; cin >> n >> m >> k; int q = m+k; for (int i..

다뤄본 태그 더보기 Exponentiation By Squaring, Modular Multiplicative Inverse (Fermat's Little Theorem) Primality Test, Prime Factorization, Sieve of Eratosthenes Sweeping Minimum Spanning Tree (Kruskal, Prim) DIsjoint-Set Union (Union-Find) Depth First Search, Breadth First Search, Dijkstra, Bellman-Ford, Floyd-Warshall, 0-1 BFS Directed Acyclic Graph, Topological Sort Tree Tree DP, Bitwise DP A. [1165..

다뤘던 태그들 더보기 Brute Force, Dynamic Programming, Greedy Sort Stack, Queue, Heap (Priority Queue) Exchange Argument Prefix Sum Binary Search, Parametric Search Greatest Common Divisor, Least Common Multiple, (Euclidean Algorithm) Multidimensional DP, Interval DP, Knapsack, Longest Increasing Subsequence, Longest Common Substring Recursion, Backtracking, Divide and Conquer Bitmasking Coordinate Compr..

1. [2183] 테니스 시합 (Bronze II) 더보기 입력은 하나의 완전한 시합입니다. 그러니 입력의 끝 = 시합의 끝이 되고, 시합의 마지막 경기를 이긴 사람이 최종 승자가 될 때 시합이 끝나기 때문에 결국 마지막 경기를 이긴 사람 = 입력의 마지막 글자가 답이 됩니다. void Main(){ int n; string s; cin >> n >> s; int sl = s.size(); cout