그리디6 cf #653 div3 F - Cyclic Shifts Sorting (그리디, constructive, sorting, inversion) https://codeforces.com/contest/1374/problem/F 소팅 문제에서 inversion개수로 규칙찾기 원소의 수가 n개인 배열 a에서 다음 연산을 최대 $n^2$번 수행하여 정렬하여라. 정렬 못하면 -1 출력 1. i번째 원소를 맨 앞으로 가져올 수 있다. 2. a의 원소가 모두 distinct하면 위 operation으로 inversion 개수의 parity를 바꿀 수 없다. 따라서 이 때 inversion 개수의 parity가 홀수면 정렬 불가능하다. 3. a의 원소에 중복 원소가 있다면 일단 distinct한 배열로 바꿔준 후에, inversion 개수의 parity가 홀수라면 중복 원소 한 쌍을 swap하여 parity를 짝수로 맞춰주면 된다. 예를들어 $a = [2,1.. 2020. 7. 13. BOJ 14939 - 전구 끄기 (비트마스크, 그리디, 완탐) https://www.acmicpc.net/problem/14939 https://www.acmicpc.net/problem/14927 n*n그리드 위에 꺼진전구와 켜진 전구가 주어진다. 한 전구의 스위치를 누르면 주변4방향과 자기 자신의 상태가 변한다. 모든 전구를 끄기위해 최소 몇번 스위치를 눌러야 하는가? (n 2020. 5. 19. cf 562 div2 C - Increasing by modulo (이분탐색, 그리디) https://codeforces.com/contest/1169/problem/C 0~m사이 값을 갖는 n개의 요소를 갖는 배열이 주어진다. 임의의 배열 요소을 여러개 골라 (ai+1) % m해주는 것을 하나의 operation이라 할때, 배열 a를 단조증가로 만들기 위해선 최소 몇번의 operation을 해야 하는가? 최소 0번 최대 m번의 operation이 필요하다. 어떤횟수 이상의 operation을 수행하면 정렬이되므로 이분탐색. bool pos(k) : k번 operation으로 a 정렬 가능? for(int i=0; i k) return false; b[i] = p; } else { if (m - b[i] + p > n >> m; a.resize(n); for (int i = 0; i < n.. 2020. 3. 15. 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. 이전 1 2 다음
