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 2020. 1. 19. 16:21

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

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

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 2020. 1. 18. 16:37

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

[Codeforces] Two Pointers Div2. C~D 난이도 (Update 19.12.29)

Problems Solved Name Difficulty Solved 580B O Kefa and Company 1500 x9884 binary search, sortings, two pointers 676C O Vasya and String 1500 x7629 binary search, dp, strings, two pointers 701C O They Are Everywhere 1500 x6398 binary search, strings, two pointers 1190A O Tokitsukaze and Discard Items 1500 x6336 implementation, two pointers 788A O Functions again 1500 x5823 dp, two pointers 1208B ..
PS - OJ/Codeforces 2019. 12. 27. 02:58

[Asgard] 익스트림너클 - 테트라 성공!

2019. 06. 20일 11시 30분경 사냥하기엔 이미 시간이 늦었고 할게 없어서 수다 조금 떨었는데 갑자기 업글이 하고싶어졌다 요즘 린네 1봉 각반 팔아서 10억글로드 가까이 있기도 했고ㅎㅎ 아무튼 그래서 이카루스 가서 코어를 2개 사서 질렀는데 크으으ㅡ으으으으으으 아스 하다보니 이런날도 있다 이전에 쓰던 트라이는 제대로 찍은 스샷이 없는데, 왜 찍었는지 모를 스샷에 트라이가 찍혀있었다 ㅎㅎ 확실히 트라이랑 테트라랑 생긴게 많이 다르다 트라이 사자마자 코어 2번 해보고, 20일날 밤에 해본 코어 2번이 전부였으나 4억으로 트라이 -> 테트라 간 셈이다 으하핳ㅎ헤헤헿 기분이 넘 좋다 :) 축하해주신 분들 모두 감사합니다~!
Hobby/Asgard 2019. 6. 23. 02:16

UVa Online Judge 10137. (The Trip)

일단 이 문제도 알고리즘 트레이닝 북 42페이지에 있는걸 보고 가볍게 풀려했으나, 알덕력이 모자라서 소수점에서 한참 헤매게 됐다. 나는 보통 소수점과 관련된 문제라면 int로 바꿔서 많이 풀었는데, 오늘은 int로 바꾸는 과정에서 문제가 있었다. 일단 컴퓨터는 부동소수점으로 소수를 표현하기 때문에 뭔가 문제가 많다. 소수와 관련된 연산은 결합법칙, 분배법칙도 성립하지 않고, 0.1은 사실상 정확히 표현이 불가능하며, int(278.78 * 100)을 printf로 찍어보면 27877이 나오는 신비한 경험도 할 수 있다.(이 부분은 int(278.78 * 100 + 0.5)로 해결할 수 있긴하다...
PS - OJ/UVa 2018. 11. 24. 21:15

UVa Online Judge 100. (The 3n+1 problem)

요즘 다시 알고리즘을 시작한지 2주정도 지난 것 같다. 오늘은 알고리즘 트레이닝 북(Programming Challenges)을 처음 펼쳐봤는데,(이 책을 산지는 100만년이 지난 것 같지만..) 첫 부분부터 가볍게 생각하고 문제를 봤는데,세그먼트 트리를 사용해서 풀 수 있는 문제가 나온 것 같아서 좀 당황했었다.보통 책 초반부는 간단한 것들을 시킬텐데....? ▶ 일단 결론부터 말하자면 책에 오타가 있었다.실제 문제는 N제한이 10,000이었는데,책에서는 N제한이 1,000,000이어서 ㄷㄷ 문제는 두 정수 a,b가 주어지고, (단, 0 < a,b
PS - OJ/UVa 2018. 11. 24. 20:55