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, ..
흔히 등장하는 동적계획법 아이디어들을 정리하기 위해서 만들었습니다. 다뤄볼 주제는 다음과 같습니다. 아마 난이도 순으로 정리할 것 같습니다. 일단 생각나는것 부터 쓰겠습니다: 동적계획법이란 무엇인가 냅색 Floyd-Warshall 게임 이론과 동적계획법 자릿수 동적계획법 Deque 트릭과 동적계획법 서로 다른 부분수열의 개수 CYK 알고리즘 비트DP 트리DP 끼워넣는 DP 원형 구간 DP DP와 행렬 제곱 Bostan Mori / Kitamasa Connection Profile SoS DP (Zeta Transform) 동적계획법 최적화 아이디어들 CHT Monotone Queue Divide and Conquer Lagrange Method 쓸거 너무 많네...
https://www.acmicpc.net/contest/view/912 간략하게 씁니다. 디테일을 안 쓰는 이유는 기억이 안나서... A $7.5N-len$ 이 0 이상인지 이하인지를 가지고 판단했습니다. 더 짧게 짜라면 짤 수 있을듯 B 그냥 하면 됨 C O(N) 풀이가 있다고 합니다. https://www.acmicpc.net/problem/4354 랑 비슷하게 풀면 됨 D 현재 위치와 현재 시간의 차이가 같은 금고를 모두 털 수 있습니다 E 현재 위치와 현재 시간의 차이가 증가하도록 금고를 털 수 있습니다. 이후는 LIS 알고리즘 F 앞쪽 절반만 보면 수가 증가해야해서 중복순열을 쓰면 됩니다 G 이분탐색 + 슬라이딩 윈도우쓰는 재미있는 문제라고 생각함 H (수열의 길이, 수열에 올 수 있는 다음 ..
다음 코드를 생각해봅시다. 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
문제: https://codeforces.com/contest/1858/problem/E2 자료구조의 Persistency를 관리하는 문제다. 자료구조의 Persistency는 주로 다음과 같은 문제이다. 어떤 자료구조 $S$를 구현하여라. $S$의 가장 마지막으로 진행한 연산을 취소해라. 이런 문제는 대개 다음과 같은 방법으로 풀린다. $S$를 구현한다. 단, $S$에서는 "amortization"을 쓸 수 없다. $S$에 어떤 연산을 진행할 때, $S$의 변경 기록을 저장한다. $S$의 마지막 연산을 취소할 때, 변경 기록을 역으로 돌린다. 무슨 말인지 살펴보자. "amortization"을 쓸 수 없다. 우리가 쓰는 자료구조 중에서는, 각 연산은 오래 걸릴 수 있지만, 전체 연산의 시간 복잡도는 특..