algorithm 검색 결과

해당 글 4건

Codeforces Edu80. Div2. D

https://codeforces.com/contest/1288/problem/D Problem - D - Codeforces codeforces.com n=6 m=5 a1: 5 0 3 1 2 a2: 1 8 9 1 3 a3: 1 2 3 4 5 a4: 9 1 0 3 7 a5: 2 3 0 6 3 a6: 6 4 1 7 0 a수열 2개만 뽑아서 각 자리마다 max값을 취함. 이 수열을 c라고 하자. c = { max(a11,a21), max(a12, a22), max(a13,a23), max(a14, a24), max(a15, a25) } 인 셈. 이제 수열 c값들의 minimum값을 구함. 이 min값의 최대값을 구하는 문제 min값을 이분탐색으로 추정한다. 그럼 이 min값 이상인 것들은 1이라 표시하고 미..
PS - OJ/Codeforces 2020. 1. 18. 16:56

XOR 문제. bit단위로 max(a_i xor X)를 최소로 하는 값 구하기

Codeforces Round #613 Div2. D - Dr. Evil Underscores Problem - D - Codeforces codeforces.com Q. XOR 문제. bit단위로 max(a_i xor X)를 최소로 하는 값 구하기 콘테중 못푸는 문제가 있는데, 그 중 어떤 문제는 답을 봐도 내가 나중에 절대 풀 수 있을 것 같지 않은 문제가 있다. 이 문제가 그런 문제중 하나.. [0, 2^30-1] 범위의 정수를 N개(최대 10만) 받고, max(a_i xor X)을 구하는데, 이 값이 최소가 되도록 X라는 정수값을 골라보자. 문제는 X를 구하는게 아니라 max(a_i xor X)의 가능한 최소값을 구하는 것이다. 푸는 방법. 최상위 비트부터 X값을 만들어본다고 생각하자. a배열의 ..
PS - OJ/Codeforces 2020. 1. 12. 20:08

LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열(Substring)을 구하는 경우.

Codeforces Round #613 Div2. B - Just Eat It! 1000Pts. Problem - B - Codeforces codeforces.com LIS(Longest Increasing Subsequence) 구하는데 정확히는 Subsequence가 모두 붙어있는 수열을 구하는 경우. 수열은 v[1], v[2], ..., v[n], n=10만, v[x]는 [-10억,10억] 범위 1. 상태공간 정의 dp[x] = x번째 배열을 반드시 포함하는 최대값 2. 점화식 dp[x] = max(0, dp[x-1]) + v[x]; DP문제 자체는 쉬운데 한가지 조건이 있었으니 n개를 모두 포함하는 수열은 답에서 제외해야 했다. 그래서 나는 f(n-1)을 구하고 v[1]=0으로 만든 뒤 f(n)..
PS - OJ/Codeforces 2020. 1. 11. 20:06

임의의 X에 대해 LCM(a,b) = X를 만족하는 a,b중 max(a,b)를 최소로 하는 a,b 구하기

Codeforces Round #613 Div2. C - Fadi and LCM 1250Pts. Problem - C - Codeforces codeforces.com Q. 임의의 X에 대해 LCM(a,b) = X를 만족하는 a,b중 max(a,b)를 최소로 하는 a,b 구하기 LCM(a,b) = a * b / GCD(a,b) 이므로 X가 정해진 이상 max(a,b)를 최소로 하기 위해선 a*b/GCD(a,b)를 최소로 해야 하며, GCD(a,b)가 1일때 max(a,b)는 최소가 될 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; t..
PS - OJ/Codeforces 2020. 1. 11. 19:58