블로그 옮겼습니다

문제 링크 \(1 L; pos.resize(N); for(int i = 0 ; i > pos[i]; auto s = upper_bound(all(pos), 0); auto m = upper_bound(all(pos), L / 2); vector ss = vector(s, m); vector ee = vector(m, pos.end()); reverse(all(ee)); for(int i = 0 ; i

http://codeforces.com/contest/732/problem/E N

문제 링크 \(1\leq{a,b,c}\leq{10^9}\) 일 때, A * B = C 를 만족하면서 |A-a| + |B-b| + |C-c| 가 최소가 되게 하는 자연수 A,B,C 에 대하여|A-a| + |B-b| + |C-c| 를 구하는 문제이다. 처음에 삼분탐색 등으로 구하려 했는데 풀리지 않았다. 애초에 삼분탐색만으로는 풀 수 없는 문제같다.우선 가장 중요한 것 중 한가지는 A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소값이 되기 위한 B와 C는자동으로 결정 된다는 것이다. 그 이유는우선 우리는 A가 이미 정해졌기 때문에 |A-a| + |B-b| + |C-c|를 최소로 만들기 위해서는 최대한B를 b와 같게 만들고 C를 c와 같게 만들어야 한다. 그런데 C는 A와 B의 곱으로 이루어 지기..

문제 링크 이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..

문제링크 모든 자연수를 \(1+2+4+.....+2^{k-1}+r\) 로 분해할 수가 있는데M개의 수를 이 방식대로 분해하여 분해된 요소들을 모두 모아 정렬한 결과인 sequence를 A라고 해보자. \(1\leq{N}\leq{10^5}\)\(1\leq{a_i}\leq{10^{12}}\) sequence의 크기 N과 N개의 elements 로 이루어진 A의 원소들 ai 가 입력으로 들어온다. 이 A를 다시 분해하기 전의 원래의 수로 복원하려고하는데 복원하는 방법은 여러가지가 있을 것이다.복원의 결과로 나온 수가 K개일 때 K가 될 수 있는 수는 여러가지가있을 것이다. 이 때 이 가능한 K들을오름차순으로 모두 출력하는게 문제의 질문이다. 우선 k+1 개의 수를 \(1+2+4+.....+2^{k-1}\) 의..

https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/winter-is-coming-12/description/ 1 ≤ Elements of array ≤ 109 1 ≤ T ≤ 10 1 ≤ N ≤ 100000 여러 테스트케이스에 대해 배열의 크기 N 이 주어지고 N개의 원소가 입력으로 들어온다.각각의 배열의 원소는 1~10억이다.연속된 부분 배열들 중 부분 배열의 원소의 합이 N으로 나누어 떨어지는 부분배열의왼쪽과 오른쪽 인덱스를 구하는 문제이다(인덱스는 1부터 시작)만약 답이 여러개라면 가장 작은 길이의 배열을, 그래도..