블로그 옮겼습니다

https://csacademy.com/contest/archive/task/second-minimum/ 반씩 나눠가며 각각의 l, r 에 대해 작은 값을 가지고 있다면 한번 분할정복 돌리면 가장작은 값은 바로 나오며그다음에 토너먼트의 승패표가 있을 때 2등의 후보는 lgN개로 정해져있는 성질이 있기 때문에 다시 순회하면서lgN개에 대해서만 반복문 한번 돌리면서 가장 작은놈을 구해주면 된다.2등의 후보는 결승에서 1등한테 진놈, 준결승에서 1등한테 진놈, 준준결승에서 1등한테 진놈, ..... ,1라운드에서 1등한테진놈이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespa..

https://algospot.com/judge/problem/read/COUNTPALIN \( 1\leq{N}\leq{10^6} \)길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해최대..

N 명의 사람이 각각 선물을 하나씩 준비해왔을 때 모두가 자신이 준비한 선물 이외의 선물을 갖도록 나눌 때그 경우의수를 구하는 문제 1 2 3 4 5 다섯명의 사람이 있다고 가정하자.맨 처음에 1번사람은 자신의 선물이 아닌 나머지 사람들의 선물, 즉 n-1 개의 선물을 가질 수 가 있다.그럼 그중에 하나의 경우인 1번사람이 2번사람의 선물을 가질 때를 생각해보자.그럼 2번사람이 받는 선물은 두가지 경우로 나뉜다. 첫번째, 1번사람의 선물을 갖는 경우. 그럼 1번 사람과 2번사람이 선물을 둘이 교환한 것과 같게 되므로D[i] : i명의 사람이 자신의 선물을 안갖도록 선물을 교환하는 경우의수일때, 교환한 두명을 제외한 나머지 n-2명에게 같은 행위를 반복하므로 D[n-2] 가 된다. 두번째, 1번 사람이 아..