PS - OJCodeforces 검색 결과

해당 글 25건

Edu 80. Div2 E - 수열의 x번째 수를 꺼내서 계속 앞으로 가져다 놓기.

https://codeforces.com/contest/1288/problem/E Problem - E - Codeforces codeforces.com [1 2 3 4 5] 라는 수열이 있을 때 3이라고 입력하면 [3 1 2 4 5]를 만들고 여기서 4라고 입력하면 [4 3 1 2 5]를 만들려고 한다. 이 때 각 숫자마다 숫자가 존재했던 위치의 max값을 구하는 문제다. segtree나 fenwick을 이용하는 전형적인 문제. x의 suffix sum이 현재 x보다 앞에 있는 숫자들의 개수를 알려준다고 하면 suffix sum은 fenwick이나 segtree등으로 쉽게 구할 수 있다. 다만 x의 suffix sum을 구하고 난 다음 이 x라는 숫자를 맨 앞으로 가져가야 하는데, 이를 위해 x를 제외..
PS - OJ/Codeforces 5년 전

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 5년 전

같은 것 포함인 오름차순(내림차순이 아닌) 경우의 수

https://codeforces.com/contest/1288/problem/C Problem - C - Codeforces codeforces.com Edu 80. div2. C 콘테중에는 못풀었지만 그래도 콘테 끝나고 나서 풀 수 있었음. 나중에 알고보니 아이디어가 참 좋은 문제. a1, a2, ..., am b1, b2, ..., bm 이렇게 m개의 수열 a, b가 있을 때, ai 0LL) return ret; return ret = (f(n-1,r) + f(n-1,r-1)) % mod; } int main() { int n,m; scanf("%d%d",&n,&m); ll ans = 0LL; for(int i=1; i
PS - OJ/Codeforces 5년 전

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 5년 전

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 5년 전

임의의 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 5년 전

Codeforces Round #443 (Div. 1) A. Short Program

Codeforces Round #443 (Div. 1) A. Short Program 나는 왜 이런문제를 못푸는지 모르겠다.하... 이 코포셋이 나온지는 6주나 지났는데,요즘 한 두달간 뻘짓만 하다가 다시 정신차리고 문제를 풀기 시작했다. 일단 이 문제는 xor, and, or 연산을 하는데,문제에서 주어지는 최대 50만개의 연산을 진행한 뒤이 값과 똑같은 값을 출력하는 5개 이하의 XOR, AND, OR 연산 조합을 출력해야한다. 이 문제의 핵심은 다음과 같다.1. 0과 AND 연산을 한다면 반드시 0이 출력되어야 한다.2. 1과 OR 연산을 한다면 반드시 1이 출력되어야 한다.3. 임의의 x번째 비트가 AND와 OR연산의 영향을 받지 않을 때에만 XOR 연산의 영향을 받는다. 이 3가지만 고려하면 문..
PS - OJ/Codeforces 8년 전

Codeforces Round #439 (Div. 2) E. The Untended Antiquity

E. The Untended Antiquityhttp://codeforces.com/contest/869/problem/E div2이지만 무려 E번 문제다.근데 E번 문제치고는 쉽게 풀 수 있었던 것 같다.2D Fenwick + 적절한 random값으로 풀 수 있었다. 일단 문제는 직사각형 평면에 사각형을 그리고 지우는 것을 반복하다가 틈틈이 쿼리가 들어온다.쿼리는 두점을 찍고 두점을 연결할 때 평면에 그린 사각형들의 모서리를 지나지 않고 연결할 수 있으면 Yes, 아니면 No를 출력해야 하는 문제였다. 일단 아래의 입력을 예제로 한번 더 설명하자면, Examplesinput5 6 5 1 2 2 4 5 1 3 3 3 3 3 4 4 1 1 2 2 2 4 5 3 1 1 4 4 outputNo Yes 맨 위의..
PS - OJ/Codeforces 8년 전

Codeforces Round #439 (Div. 2) C. The Intriguing Obsession

C. The Intriguing Obsessionhttp://codeforces.com/contest/869/problem/C (이 문제 너무 어려웠다 ㅠ.ㅠ 콘테중엔 나도 못풀었는데, 해설은 codeforces tutorial을 참고했다.)(참고로 이 문제를 풀려면 페르마 소정리를 알고 있어야 한다. 모른다면 dp로 해결하는 수밖에 없다.) 이 문제는 경우의 수를 구하는 문제다. 섬이 3종류가 있고 섬들 간에 다리를 놓으려고 한다.단 다리를 놓을 때 같은 색깔의 섬들은 최소 3의 길이가 되도록 놓아야 한다. (다리 하나는 길이 1을 의미한다.)각 섬을 직접적으로 연결하는 다리는 하나만 놓을 수 있다.(a,b를 직접적으로 연결하는 다리는 2개 이상 놓을 수 없다.) 입력은 다음과 같다.Examplesin..
PS - OJ/Codeforces 8년 전