이분탐색10 BOJ 15758 - Milking order (이분탐색, 위상정렬) https://www.acmicpc.net/problem/15758 최대 5만개의 법칙 M개가 주어진다. 법칙마다 순서가 주어진다. 예를들어 1 4 3이면 최종 결과에 1 4 3 이 순서대로 나타나야 한다. 앞에서부터 최대한 많은 법칙을 사용해서 유효한 n의 permutation을 만들고자 할 때, n의 permutation을 구하라. 앞에서부터 법칙 1개 ~ m개를 만족할 때에 대해 가능한지 이분탐색한다. bool pos(int k) 함수에서 앞에서부터 k개의 법칙을 이용해서 위상정렬 가능한지 반환하면 된다. 단, 가능한 수열 중 사전 순으로 가장 앞선 수열을 출력해야하므로 위상정렬시 pq를 쓰면 된다. int n, m, ind[MAX]; vector odr[50004]; vector topo; vec.. 2020. 3. 1. Educational codeforces #80 D - Minimax Problem(이분탐색, 비트마스크) https://codeforces.com/contest/1288/problem/D 최대 3e5개의 숫자 배열이 들어온다. 각 배열은 최대 m(m 20 0 1 0 1 1 -> 11 두 배열을 or했을 때 1 1 1 1 1이 되므로 b는 3이상의 최소값을 갖는다. 이번엔 4 이상이면 1, 4미만이면 0으로 바꿔보자 1 0 0 0 0 0 0 0 1 0 OR 연산 후에 1 1 1 1 1이 되지 않으므로 b는 4를 최소값으로 갖지 못한다 여기까지 생각했어도 isPossible(mid) 부분을 구현하는것이 쉽지 않다. 모든 배열에 대해 2중 for문으로 검사하면 n^2으로 시간초과다. 좀더 최적화 해보자 하나의 배열이 갖을 수 있는 비트값은 0 ~ (1 2020. 1. 17. Educational round #75 D - Salary Changing ( 이분탐색 ) https://codeforces.com/contest/1251/problem/D 보자마자 이분탐색이나 dp겠구나 싶어서 이분탐색으로 접근했다. 하지만 시간이 부족해서 10분정도 오버해서 풀었다. 설명) 사람의 수 n과 가지고 있는 돈 s가 주어지고 n명의 사람에 대해 받을 수 있는 돈의 범위 [l,r]이 주어진다. 이 때 사람들에게 나누어주는 돈의 중간값의 최대를 구하는 문제이다. l을 기준으로 사람들을 오름차순 정렬한다면 l, l, .... l, m, max(m,l), max(m, l) ... max(m,l) 인 경우가 최적이다. m값을 기준으로 오른쪽에 위치할 수 있는 사람은 r의 값이 m이상이어야 한다. 중간값 우측의 사람 수가 n/2미만이라면 그 값을 중간값으로 사용할 수 없다. 이 부분이 생각.. 2019. 11. 9. 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. 이전 1 2 3 다음