투포인터4 cf #632 div2 C - Eugene and an array (투포인터) https://codeforces.com/contest/1333/problem/C -1e9~1e9값을 갖는 최대 1e5의 원소 n개의 배열이 주어진다. 배열의 subarray 중 그 subarray의 subarray의 원소합이 0이 아니면 good subarray라고 한다. 주어진 배열의 good subarray 개수를 구하라 [a1, a2, a3, a4]가 good subarray라면 [a1,a2,a3]도 good subarray이다. 하지만 [a3,a4]가 good subarray일수도 있고 아닐수도 있다. ps[1] = ps[4]인 경우 a[2]~a[4]는 bad subarray이다. 문제의 성질을 잘 생각해보면 투포인터로 풀 수 있다. ll n, a[MAX], ps[MAX]; int main() .. 2020. 4. 13. BOJ 11982 - Angry cow (그리디, 전처리dp, 투포인터) https://www.acmicpc.net/problem/11982 어렵다 공식홈페이지와 rdd6584님의 코드를 보며 공부했습니다. 일직선위에 최대 5e4개의 표적이 n개 주어진다. 폭발반경이 R인 폭탄을 일직선 위에 던지려고 한다. 표적은 터지면 이전 폭발반경보다 1 작은 만큼의 폭발반경을 가지며 연쇄폭발한다. 적절한 곳에 폭탄을 던진다면 모든 표적을 부수기 위해 필요한 폭탄의 최소 폭발반경은 몇일까? 소수점 첫 자리까지 나타내라 폭탄은 어떤 두 표적 정 가운데에 떨어지는 것이 최적이다. ->(x+y)/2로 표적의 위치를 특정할 것이므로 표적의 위치는 xxx.5 혹은 xxx.0이다. 모든 표적의 좌표를 두배로 하고 폭발반경이 2씩 줄어든다고 처리하면 정수연산만으로 풀 수 있다. 표적은 오름차순 정렬해.. 2020. 2. 27. codeforces #591 D - Sequence Sorting (LIS유사, 투포인터, dp) https://codeforces.com/contest/1241/problem/D 최대 300000의 쿼리에 대해서 최대 300000길이의 배열을 입력받고 문제에 나온 연산을 최소한으로 수행해서 배열을 정렬한다면, 그 연산의 횟수를 출력하는 문제다. 초기의 배열을 A(앞으로 미는 연산 수행한 그룹) + B(연산수행하지않은 그룹) + C(뒤로 미는 연산을 수행한 그룹)으로 나눈다면, A의 크기와 C의 크기의 합이 정답이 된다. (여기서 크기는 그룹에 속한 숫자의 종류개수) A크기+C크기 = 초기배열의 크기 - B그룹의 크기 이므로, B그룹의 크기만 계산해주면 된다. B그룹은 초기 배열에서 이미 정렬된 최대의 길이이므로, LIS와 유사하다고 볼 수 있다. (초기배열이 1 3 1 4라면 LIS=3, 정렬된 최.. 2019. 11. 2. codeforces #596 div2 B2 - TV subscribtions hard (투포인터) https://codeforces.com/contest/1247/problem/B2 한국말 풀이가 있었으면 금방 넘어갔을 것 같은 문제. editorial에서 투포인트가 문제 풀이법이라고 해서, kks227님 블로그에 가서 관련 문제 풀어본 후 다시 풀어봤는데도 못품. 문제설명 : 배열크기 = 9, 요소종류 = 3, 범위 d = 3 배열 : 3 3 3 2 2 2 1 1 1 로 주어졌을때 연속된 범위 만큼의 부분 배열에 포함된 종류의 최소를 구하는 문제이다. 위의 예제의 답은 1이 된다. ( 333 ''222'' 111 : 큰 따옴표로 표시한 부분배열일 때 정답을 알 수 있다.) 풀이: arr[0] ~ arr[d-1]에 포함된 각 요소의 개수를 미리 map에 저장해둔다. arr[1]~arr[d], arr[.. 2019. 10. 28. 이전 1 다음