Eau de Cologne

문제와 풀이 간략하게만 작성합니다.1. 연속 1$0$과 $1$로 구성된 수열이 주어집니다. 수열에 있는 $0$을 $1$로 바꾸는 데에는 한 번에 비용 $S$가 들고, $1$을 $0$으로 바꾸는 데에는 한번에 비용 $E$가 듭니다. 수열의 값을 바꿔서 $1$이 연속으로 나오는 부분이 $1$개 이하가 되도록 하고 싶습니다. 이 때의 최소 비용을 계산하세요.풀이수열을 앞에서부터 보고 다음과 같이 정의합니다.앞 $i$개의 원소에 대해 수열을 모두 $0$으로 만드는 비용: $X_i$수열을 $0...01...1$의 꼴로 만드는 비용: $Y_i$수열을 $0...01...10...0$의 꼴로 만드는 비용: $Z_i$이 때 $X_{i+1} = X_i + V_i \times E; Y_{i+1} = \min(X_{i+1},..

문제와 풀이 간략하게만 작성합니다.1. A보다 B가 좋아A와 B로만 이루어진 문자열이 주어질 때, 연속이고 길이가 2 이상인 어떤 부분에서도 A의 개수가 B의 개수보다 많지 않기위해 문자열에 끼워넣어야 하는 B개수의 최솟값은?풀이두 A사이의 간격을 살펴봅시다. 두 A사이에 B가 0개 혹은 1개 있으면 AA, ABA 문자열에 대해 A의 개수가 B의 개수보다 많게 됩니다. 두 A사이에 B가 2개 이상 있으면, $n$개의 A가 있는 부분문자열을 고르려고 할 때 B를 $2n-2$개 이상 골라야해서, $n \ge 2$에 대해 항상 B의 개수가 A의 개수 이상이 됩니다.2. 배달$N$개의 수를 4개씩 $\frac{N}{4}$개의 그룹으로 묶어서, 각 그룹 점수의 합을 최대화 하려고 한다. 그룹 ${a, b, c, ..

다음 코드를 생각해봅시다. fn ref_idx(v: &mut [i32], i: usize, j: usize) -> (&mut i32, &mut i32) { assert!(i != j && i (&'b mut i32, &'b mut i32) { assert!(i != j && i

HTML 삽입 미리보기할 수 없는 소스

HTML 삽입 미리보기할 수 없는 소스 Sample Usage: Problem: https://www.acmicpc.net/problem/17429 Code: https://www.acmicpc.net/source/share/29df4fc631d14b97ba84e21bea6a2d87

에라토스테네스의 체에서 간단한 최적화만으로도 매우 빠르게 동작합니다. $O(N \log \log N)$ 시간복잡도를 가졌지만, 로컬에서 1억에 0.25초, 10억에 3.6초 정도에 동작합니다. HTML 삽입 미리보기할 수 없는 소스 기본적인 에라토스테네스의 체와 같은 방식으로 처리합니다. 단, 다음과 같은 최적화를 거쳐줍니다. 1번 줄: vector은 필수적입니다. 라이브러리가 bit단위로 값을 저장하기 때문에, 메모리 사용량을 획기적으로 줄일 수 있습니다. (수 800만개당 1MB입니다. 1억은 12.5MB, 10억은 125MB를 사용합니다) 2-4번 줄: 소수가 될 수 있는 수는, 3 이상의 홀수와 2 뿐입니다. 5번 줄 (i=3, i+=2): 2의 배수는 이미 불가능하다고 체크했기 때문에, 3이상의..