[Codeforces Round #806 (Div. 4)] E. Mirror Grid
※ 짝수의 경우 왼쪽 상단(2사분면)만 확인해주면 모든 셀을 방문할 수 있음. 홀수의 경우 중앙이 추가되기 때문에 x좌표나 y좌표 중 하나를 추가로 확인해주어 g셀을 제외한 모든 셀을 탐색하게 해야됨 (i 짝수의 경우 5/2 홀수가 되기 때문에 문제없다. 홀수의 경우 6/2 로 열을 한 번 더 탐색해준다.) ※ 중앙 셀을 제외한 모든 셀은 다음과 같이 이동한다. a좌표 - [0,0] -> [0,3] -> [3,3] -> [3,0] b좌표 - [0,1] -> [1,3] -> [3,2] -> [2,0] 홀수의 경우 c좌표 - [2,0] -> [0,2] -> [2, 4] -> [4,2] (x와 y는 처음의 좌표 [x,y] -> [y,x의 반대] -> [x의 반대, y의 반대] -> [y..
[Codeforces Round #784 (Div. 4)] H. Maximal AND
※. 작업을 통해 ai의 비트 중에 비트 1개를 1로 바꿀 수 있다.(or 연산) ※. 가장 최상위 비트부터 바꾸는 것이 이득이다. (j = 2, 4 ,8을 바꾸는 거 보다 j = 16을 바꾸는 것이 더 큰 값) ※. 1에서 n개 까지의 배열값에서 (0~30)번째 비트가 1인것의 개수를 세어준다. (비트가 겹친다면 k작업을 적게 수행하여 결과를 바꿀 수 있다.) ※. (n - (0~30)비트 개수를 저장한 배열)이 k보다 작다면 결과값을 바꿀 수 있다. (n = 3, k = 2, [8,4,2]이면 arr[0] = 0, arr[1] = 1, arr[2] = 1, arr[3] = 1이다. 3 - 1(arr[3])은 2이므로 k작업을 2번해서 4와 2를 모두 or 8 (100 -> 1100, 10 -> 101..
[Codeforces Round #790 (Div. 4)] E. Eating Queries
※ 섭취해야 하는 설탕의 양이(x) 모든 사탕의 합보다 크다면 -1을 출력 ※ 설탕의 양이 사탕의 합과 같다면 사탕의 갯수(n) n을 출력 ※ 사탕의 정보가 있는 배열을 정렬한 후 가장 설탕이 많은 사탕부터 사탕 갯수당 설탕의 양을 나타내는 배열을 만든다 (1,1,3,3,4,4,5,9) -> (9, 9+5, 9+5+4, 9+5+4+4, ... 9+5+4+4+3+3+1+1) ※ n, q가 150,000 이므로 nq가 아닌 q*log n 인 이분탐색으로 찾아야함 1.사탕 갯수마다 설탕의 합을 나타내는 dp배열을 생성 2. x가 sum(설탕의 합)보다 크면 -1 같으면 n 3. 나머지 경우는 이분탐색으로 dp배열을 탐색 import java.io.BufferedReader; import java.io.IOEx..
