qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

길이 $2n$의 올바른 괄호문자열의 개수는 $C_n = \frac{1}{n+1} \binom{2n}{n}$임을 보이자. 문자열 $s=s_1s_2 \cdots s_{2n}$와 순열 $p = (p_1, p_2, \cdots, p_{2n})$에 대해, 문자열 $s' = s_{p_1}s_{p_2} \cdots s_{p_{2n}}$이 올바른 괄호문자열이면 "$s$가 $p$에 대해 올바르다"고 정의하자. 편의상 $n=4$인 경우에 대해서만 설명한다. 일반적인 경우도 동일한 방식으로 증명 가능하다. $$p_1 = (1, 2, 3, 4, 5, 6, 7, 8)$$$$p_2 = (2, 3, 4, 5, 6, 7, 8, 1)$$$$p_3 = (4, 5, 6, 7, 8, 3, 1, 2)$$$$p_4 = (6, 7, 8, 5, ..

수학 위주로 좀 풀었다.BOJ 17563 (Mona Lisa)$N(\le 50)$비트 랜덤 정수열 $A$, $B$, $C$, $D$가 주어질 때, $A_i \oplus B_j \oplus C_k \oplus D_l = 0$인 $(i, j, k, l)$을 찾는 문제이다. 각 정수열은 pseduo-random generator와 시드로 표현된다.더보기수열 4개를 동시에 다루는 것은 복잡하기 때문에 먼저 2개씩 묶어서 생각한다. 길이 $2^X$ 정도의 수열 2개를 합치면 상위 $X$비트가 0인 원소 $2^X$개 정도를 얻을 수 있다. 이렇게 하면 상위 $X$비트가 모두 0인 $2^{2X}$개의 페어를 만들 수 있고 이 중 하위 $N-X$비트가 겹치는 페어를 찾으면 된다. 따라서, $X=N/3$정도로 하면 풀 ..

오랜만에 AGC + 랭작을 했다. AGC066A. 체스보드 컬러링 후 mod 2d 기준 0/d로 맞추면 된다.B. 못 풀겠어서 풀이를 봤다. 5^i는 2를 곱할 때마다 자릿수 합이 감소하는 경향을 보인다. 적당히 5의 거듭제곱을 많이 이어 붙여서 노이즈를 제거하자.C. 못 풀겠어서 풀이를 봤다. 제거 가능할 필요충분조건은 A가 B의 2배면서 왼쪽이나 오른쪽 끝에 B가 있는 경우다. 이를 이용하면 dp를 할 수 있다.D. 몇 개의 점은 고정하고 그 주변에 있는 A를 퍼뜨린다는 느낌으로 해를 표현할 수 있다. 각 점을 고정했을 때 영향을 받는 구간을 모두 구한 후 dp를 돌리면 된다.E. BOJ 18873이랑 같다. 돌의 배치를 고정해두고 swap 가능한 두 점을 모두 찾아보자. 부모가 자식과 swap 가능..

BOJ 17728 (Walls)각 방벽에 대해 계산하는 쿼리 문제라고 생각하자. 방벽의 이동 경로는 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> ... 과 같은 형태로 나타난다. 시작점이 INF 또는 -INF일 때 경로에서 꺾이는 점을 관리하면 문제를 해결할 수 있다. 방벽의 길이가 증가하면서 꺾이는 지점의 삭제가 일어나고, 이는 연결리스트와 같은 형태로 관리해줄 수 있다. pq를 사용하면 삭제되는 원소를 빠르게 구할 수 있고, 세그를 이용해서 답을 계산할 수 있다. BOJ 17667 (Virus Experiment)풀이가 다양하다. 풀이 1: https://qwerasdfzxcl.tistory.com/24 (타잔 알고리즘과 비슷하다.) 풀이 2: 풀이 1과 비슷한데, scc를 유파로 전부 들고 있으면..

어떤 점 x에서 시작해서 방문할 수 있는 점의 집합을 A_x라고 합시다. A_x의 값이 최솟값이라면, A_x의 임의의 원소 y에 대해 A_y = A_x를 만족합니다. 이러한 집합 A_x들을 "최소 집합"이라고 합시다. 구하고자 하는 집합은 최소 집합의 합집합입니다. dfs를 다음과 같은 규칙에 따라 돌려봅시다. 현재 dfs tree를 만들고 있는 상황이라고 생각하고, dfs(v)가 실행중이라고 합시다. v의 서브트리의 원소를 S_v라고 할 때, 1. S_v와 S_v의 여집합을 연결하는 간선 중, S_v에서 얻은 key를 이용하여 갈 수 있는 간선을 차례로 확인합니다. (주의: S_v는 원소가 계속 추가됩니다.) 2. 그 간선을 타고 가서 나온 정점 w를 방문한 적이 없다면 dfs(w)를 호출합니다. df..

대회장에선 섭태 1만 긁고 접근도 못했는데 백준에 올라왔길래 업솔빙을 했습니다. 서브태스크 2와 3의 풀이를 urd05님에게 듣고 100점 풀이를 찾았습니다. https://www.acmicpc.net/problem/23347 23347번: 수열 연산 모든 수가 $1$ 이상 $K$ 이하의 수로 구성된 수열이 있다. 이 수열에 다른 연속한 부분수열을 삽입하거나 삭제하는 연산을 원하는 만큼 할 수 있다. 단, 이 수열은 길이가 $M$ 이상이어야 하며, 수열 www.acmicpc.net 실제 대회에서의 서브태스크는 다음과 같습니다. 서브태스크 1: $2M \le K$ 서브태스크 2: $M, K, |C|, |D| \le 6$ 서브태스크 3: $M, K, |C|, |D| \le 10$ 서브태스크 4: $M, K,..

문제 링크: https://www.acmicpc.net/problem/18779 18779번: Help Yourself (Platinum) Bessie has been given $N$ ($1\le N\le 10^5$) segments on a 1D number line. The $i$th segment contains all reals $x$ such that $l_i\le x\le r_i$. Define the union of a set of segments to be the set of all $x$ that are contained within at least one segment. www.acmicpc.net 문제 설명: [1, 2N] 구간에 선분이 N개 있을 때, 2^N개의 모든 선분의 부분집..

문제 링크: https://www.acmicpc.net/problem/9208 9208번: 링월드 링월드는 반지모양으로 이루어진 나라이다. 이 나라에는 도시가 m개 있고, 편의상 0, 1, 2, ... m-1로 번호가 매겨져 있다. 이 도시는 반지모양을 이루고 있으며, 0, 1, 2, m-1, 그리고 다시 0 순서이다. www.acmicpc.net 풀이) 일단 그래프 모델링을 해봅시다. 이분그래프 G = (A, B)를 생각할건데, |A| = N, |B| = M이고, i번째 구간이 [j, k]일 때, A에서 i번째 점을 B에서 [j, k] 점들과 연결합시다. 이렇게 하면 문제가 "그래프 G에서 A를 덮는 매칭이 존재하는가?"로 변하게 됩니다. 이 상태로 segment tree를 이용하여 문제를 해결할수도 ..