공부 저장소

자료구조 검색 결과

해당 글 3건

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 5년 전

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 5년 전

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 5년 전