본문 바로가기

알고리즘/코드포스44

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 #591 div2 C - Save the Nature (이분탐색) 모든 변수를 long long으로 바꿔주니 ac받았다. 배열크기n과 배열을 입력받고, a번째 요소마다 x퍼센트의 기부금을 주는 것에 대한 입력 a,x,b,y를 입력받고, 기부금의 최소금액인 k를 입력받는다. 위와 같이 입력받은 후, k이상의 기부금을 받을 수 있는 최소한의 티켓수를 구하는 문제이다. 문제에서 배열의 순서를 자유롭게 할 수 있다고 한 것에 속아넘어가지 않고, 수학적으로 생각하면 된다. 조건에 맞는 티켓의 최소값을 찾는 이분탐색에 isPossible함수를 O(n)으로 구현해서 전체 O(logn)이다. isPossible함수는 다음과 같이 구현했다. 팔리는 티켓수를 m이라고 할 떄, 1) (x+y)%가 붙는 경우는 t = m/lcm(a,b) 2) x%가 붙는 경우는 r = m/a-t 3) y%.. 2019. 11. 1.
codeforces #592 div2 C - The Football season(수학, 발상) https://codeforces.com/contest/1244/problem/C n > p >> w >> d; ll x, y=-1; for (ll i = 0; i = 0 && (p - i * d) % w == 0) { if ((p - i * d) / w + i 2019. 10. 31.
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.

티스토리툴바