Codeforces 검색 결과

해당 글 6건

Codeforces Round #625 - D. Reachable Strings

https://codeforces.com/contest/1320/problem/D Problem - D - Codeforces codeforces.com 두 문자열이 서로 연결되어있다(reachable)는 것을 다음과 같이 정의한다. 어떤 문자열에서 011 혹은 110 이 등장하면 그것을 각각 110, 011로 바꾸는 동작을 반복하면 다른 문자열과 같아질 수 있다.(원문 디스크립션 예시 참고 바람) 초기 문자열(S)이 주어지고 l, r, len 쿼리 형식으로 입력이 주어진다. S[l,l+1,...l+len-1]과 S[r,r+1,...r+len-1] 이 서로 reachable하면 Yes, 아니면 No를 출력하여라. 곰곰히 고민해보면 1이 두개 연속으로 있는 부분을 지워도 상관이 없다. 1이 달랑 한 개만 ..
Problem Solving 2020. 3. 4. 17:45

Centroid에 관하여

Centroid는 트리의 중심을 의미한다. 모든 이웃의 서브트리의 크기가 전체 트리 크기의 절반 이하가 되도록 하는 정점을 의미한다. 그렇기 때문에 용도가 재귀적이다. 트리에서 $O(N)$이나 $O(NlogN)$ 수준에서 문제의 조건을 만족하는 단 하나의 경로를 찾아야하는 문제에 대해서는 무조건 센트로이드를 떠올려야 한다. 센트로이드의 정의를 이용한 예제 https://codeforces.com/contest/1205/problem/D Problem - D - Codeforces codeforces.com 좋은 수학문제다. 센트로이드를 중심으로 이웃 노드를 2개의 파티션으로 분할하여 서브트리의 크기 합이 각각 $N/3$와 $2N/3$ 사이에 오도록 만들 수 있다. 각각의 수를 $a$와 $b$라고 하면, ..
Problem Solving 2020. 2. 17. 23:05

Codeforces Round #609 - C. K Integers

https://codeforces.com/contest/1268/problem/C Problem - C - Codeforces codeforces.com 역시 문제 기술 짧고 간단하다. 퍼뮤테이션 배열 $p_1, p_2, \dots, p_n$이 들어온다.($1 \leq n \leq 2\cdot 10^5$) 배열의 인접한 두 원소의 값을 바꾸는 동작을 실행할 수 있다. 어떤 $k$에 대해 $p_i = 1$, $p_{i+1} = 2$, ..., $p_{i+k-1} = k$를 만족하도록 시행해야할 동작의 최소 횟수를 $f(k)$라고 하자. $f(1), f(2), \dots, f(n)$을 공백을 간격으로 출력하여라. (풀이) 본격 라이브러리빨 문제 퍼뮤테이션의 위치 배열을 $pos$라고 하자. (즉, $pos ..
Problem Solving 2020. 2. 7. 14:44

Codeforces, 백준 프로그래밍을 위한 Vim 세팅

글을 시작하기 앞서 나는 프로그래밍 초보임을 명시하겠다. 코드포스 대회 경험도 얼마 없으며 이제 막 오렌지를 단 신생아이다. 실제로 내가 이 세팅을 백준이나 코드포스 문제를 푸는데 제법 효율적으로 사용하고 있다는 느낌도 들어서.. 포스팅 한다. Vim이 코딩할 때 도움이 되는가? Vim을 제대로 사용하면 분명 코딩에 도움이 된다. 동영상에 나온 것은 간단한 문제에 대한 코드다. $N$개의 정수가 들어오고, $Q$개의 쿼리가 주어진다. 각 쿼리마다 자연수 $k_i$가 입력으로 주어지며, $k_i$번째로 큰 정수를 출력하고 그 값을 원래 집합에서 지운다. 그냥 쌩 C++로 코딩한다면 어떨까. STL에서 여러 가지 이진탐색트리는 지원해주나(map, multiset 등) k번째 원소에 대한 연산을 코딩하려면 머..
Vim 2020. 2. 3. 20:21

Codeforces Round #616 - C. Prefix Enlightenment

https://codeforces.com/contest/1290/problem/C Problem - C - Codeforces codeforces.com 문제 깔끔해서 좋다. 램프 $N$개가 있고($1 \leq N \leq 3 \cdot 10^5$), 그들의 초기 On-Off 상태(1/0) 배열 $S$가 입력으로 주어진다. 집합 $A_1, A_2, \dots , A_k \subseteq \{1, 2, 3, \dots, N\}$이 있다.($1 \leq K \leq 3 \cdot 10^5$) 단, 임의의 $1 \leq i < j < k \leq N$을 고르면 $A_i \cap A_j \cap A_k = \emptyset$을 만족한다. $A_i$ 집합을 선택하면 그 집합의 원소에 해당하는 모든 램프가 togg..
Problem Solving 2020. 2. 3. 16:33

Educational Codeforces Round 81 - E. Permutation Separation

https://codeforces.com/contest/1295/problem/E%EF%BB%BF Problem - E - Codeforces codeforces.com 문제 리딩이 깔끔해서 좋았다. 퍼뮤테이션 배열과 비용 배열이 입력으로 들어온다. 적당한 칸막이를 설치하여 왼쪽에 1~k의 퍼뮤테이션 값을 가지는 원소를, 오른쪽에 k+1~N의 값을 가지는 원소를 배치시키는 것을 최종목표로 하며, 원래 위치에서 좌 혹은 우 칸막이로 이동하는데 걸리는 코스트가 입력의 비용 배열이다. 초기 칸막이 위치가 k번째 원소와 k+1번째 원소 사이에 있었다고 가정하고, 결과적으로 왼쪽에 퍼뮤테이션의 1~t 원소가, 오른쪽에 t+1~N 원소가 위치하게 된다고 하자. 이 때 필요한 최소 비용을 $D[k][t]$ 라고 하면..
Problem Solving 2020. 1. 31. 00:03