전체 글36 CF 1732D1 https://codeforces.com/contest/1732/problem/D1 Problem - D1 - Codeforces codeforces.com 가장 느린 풀이는 문제에서 요구하는 대로 그냥 set만들고 거기에 숫자 넣고 ? 쿼리 들어오면 k-mex를 구하는 것이다. 여기서 들어오는 k에 대해 ans를 map 같은 자료구조를 이용해 전처리 해두고 나중에 다시 그 k에 대한 쿼리가 들어오면 그 때 set에서 ans + i * k가 없을때까지 i를 0부터 돌려주고 다시 ans를 저장하면 시간초과가 나지 않는다. 근데 사실 왜 시간초과가 나지 않는지는 정확히 모른다... 그냥 뇌피셜로는 최악의 경우가 k가 모두 다를 때고 set의 크기를 sz라고 하면 어떤 k에 대해 i의 반복 횟수는 sz / k.. 2022. 11. 4. CF 1732C1 https://codeforces.com/contest/1732/problem/C1 Problem - C1 - Codeforces codeforces.com 어떤 수 x에 xor y를 하면 x는 최대 y만큼만 변한다. 따라서 구간의 길이가 길수록 f의 값이 커지므로 f의 최댓값은 f(1, n)이다. f(l, r) == f(1, n)인 구간 중 가장 짧은 구간을 구해야 하므로 psum, pxor을 전처리 해준 뒤 이분탐색을 돌리면 된다. 2022. 11. 4. BOJ 10649 https://www.acmicpc.net/problem/10649 10649번: 프리스비 농부 존과 그의 소들은 프리스비를 하며 놀고 있다. 베시가 프리스비를 던지자, 마크한테 갔고 결국 마크네 팀에게 프리스비가 넘어갔다! 마크의 키는 H이고(1 2022. 11. 1. BOJ 18320 https://www.acmicpc.net/problem/18320 18320번: Loan Repayment Farmer John owes Bessie $N$ gallons of milk ($1\le N\le 10^{12}$). He has to give her the milk within $K$ days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bess www.acmicpc.net X가 1이면 항상 가능하다. X가 N이면 1 * K < N 이므로 항상 불가능하다. 따라서 먼저 이분탐색을 생각해 .. 2022. 10. 31. 이전 1 2 3 4 5 6 ··· 9 다음