Codeforces 1251F (Educational 75) Red-White Fence
알고리즘 문제풀이/Codeforces
2020. 4. 24. 02:29
난이도 : Codeforces 2600 사용하는 알고리즘 : FFT, Combinatorics 1. 문제 설명 Red Fence $k < 5$ 개와, White Fence $n < 1e5$ 개의 길이가 주어진다. 이때, 다음과 같은 조건을 만족하는 Fence를 만들려고 한다. - 가운데의 Red-Fence를 기준으로, 그 앞과 뒤에 0개 이상의 White Fence를 설치한다. - 이때, Red Fence까지의 높이는 Strictly increasing해야 한다. 즉, 1 < 3 < 5 < 7, 7이 빨간색과 같은 형태. - Red Fence부터 끝까지의 높이는 Strictly Decreasing해야 한다. 즉, Red Fence를 중심으로 하는 Strict bitonic 을 요구한다. 쿼리가 잔뜩 주어..