Go Gradually - Repository

실제 contest중에는 풀지 못한, 난이도 높은 문제였다.Upsolving 을 진행하며, 정리한 내용을 공유하고자 한다.문제https://codeforces.com/contest/1905/problem/Dnn^2 으로는 절대 풀 수 없는 문제이다.핵심 아이디어1. 반드시 맨 앞 원소가, 맨 뒤로 간다.중요한 통찰을 얻을 수 있는 단서 중 하나는, a[0]이 맨 뒤로 간다는 것이다.이 사실을 응용해보자2. MEX값은, 범위가 넓어지면 넓어질수록 무조건 증가하는, 단조증가 형태를 띈다.단조증가 성질 또한, 무궁무진한 활용 가능성을 갖추고 있다.그리디한 접근 혹은, 파라매트릭 서치에도 응용이 가능하니, 기억하고 있도록 하자.3. 값이 순열로 주어진다.중요한 통찰을 얻을 수 있는 마지막 단서는, 값이 순열로 ..

https://codeforces.com/contest/1937/problem/C현재 주어진 연산으로 가능한 것최댓값 찾기: a|a 최솟값 찾기: a|a 현재 주어진 순열은 [0, n-1] 범위를 갖는다.따라서, XOR로 만들 수 있는 최대의 정수는 상한이 정해져 있다.px ^ py = (n - 1의 msb) * 2 - 1그렇다면, 저 상한을 어떻게 만들어낼 것인가?최댓값(n-1)을 찾는다.최댓값과 or 연산을 수행하여 가장 큰 값을 만드는 인덱스들을 찾는다.해당 인덱스들의 집합에 들어가기 위해선 최댓값의 하위 비트가 0인 비트들을 1로 채울 수 있어야 한다. 예시) 11010 -> 1101, 101, 111, 10111XOR 도 결국 OR 되어야 하는데, 그냥 이러면 어떻게 답 안나오나 라는 느낌으로 ..

문제 링크: https://codeforces.com/contest/1995/problem/C오버플로우를 막는 방법에 대한 고민핵심 아이디어a^x^2 a^x >= b^y 인 경우는 없다증명1 초과인 a, b, x, y에 대하여a^x a^x^2 > b^y 이면a^x^2 a^x = p, b^y = q 라고 하면p p * p p * p 따라서 핵심은, 몇번의 제곱을 수행해야 하느냐!오버플로우를 신경쓰지 않도록, 2^63 내에서 대소 비교를 수행하는 방법실제 문제를 풀진 못했으므로, 구현은 남기지 않음

k제일 큰 수에 1이 있으면?그냥 그거 쭉 늘리면 됨제일 큰 수에 1이 없으면?1이 붙은 수 중 가장 큰 수를 늘리거나큰수와의 차이만큼 낭비그 후 효율 떡상(1)중간값을 늘리거나효율 갈수록 안좋아짐이거 이분탐색 되려나?그래프가 ~자 모양이 됨효율 이김/안이김 이분탐색?몰빵보다 좋음/안좋음?이건 몰빵한테 따이는 시점 이분탐색인데중간값을 늘리는 시도를 점차 증가시켜본다?왜 그게 그렇게 되지?왜 최대 원소가 효율을 뽑기 시작하거나k 개 중 x개를 투자하면그 이후 k - x 개는 무조건 큰 수에 넣는게 제일 고효율이다문턱값을 넘으면 그 이후는 거기에 몰빵하는게 무조건 이득중간값을 올리는데 전부 몰빵하거나문턱값 안넘을거면 그냥 중간값 올리는데 몰빵이 나음그럼 중간값을 어떻게 올리지?순서가 동적으로 바뀌는데정해진 ..

트리 구조로 되어있는 숨겨진 그래프n-1 개의 간선을 찾아야 함15n 개의 쿼리를 통해n≤1000트리 구조의 특성상, 임의의 두 노드 사이의 경로는 유일하다한번에 하나씩 컴포넌트를 합쳐나가면?유니온 파인드 이용사이에 모르는 컴포넌트가 나오면?그냥 그거 찾지 뭐...?중요한건 임의의 두 컴포넌트를 "연결" 하고자 하는 것거리가 절반씩 줄어드니, logN서로 다른 두 컴포넌트 찾는 법유니온 파인드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;//Change Class Name to ..

mex를 사용하여 입력받은 값을 최대로 만드는 문제mex는 두번 사용하면 최대로 커지므로, 이를 이용해 달성 가능한 가장 큰 값을 리스트를 순회하며 확인한다.만약 한번만 사용가능했다면 그래프 문제가 됐을 것 같다.맨날 전역에 동적 메모리 할당하고, 오랜만에 PS하느라 까먹었는데메모리 할당도 할당된 크기만큼 시간이 든다!시간복잡도 터지는것에 주의하자.import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.*;//Change Class Name to Proble..

k 번마다 전구가 on-off 됨시간 - 스타트시간/k 의 값이짝수이면 켜진 시점홀수이면 꺼진 시점무조건 모든 전구가 한번이라도 켜진 시점 이후 k시간 안에 전구가 켜져야됨이후는 반복되는 패턴(x - a_i) / k 의 패리티가 모두 짝수인 가장 작은 x최대와 최소 사이 공간이 존재하냐를 묻는 문제로 바뀜((x - a_i) / k) % 2 == 1x += k - (x - a_i) % k(x - a_i) / k % 2 == 0y = min(y, x + k - (x - a_i) % k)import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import..