Codeforces 분할정복 Tag 부수기

말그대로 여기서 태그에 DnC가 붙어 있는 놈들을 풀어보려는 시도입니다. 백준에서 좋은 DnC 찾기가 너무 힘들어서...

559B. Equivalent Strings

559B

문제가 말하는 "동치 관계"가 정말로 equivalent relation의 조건을 만족시킨다는 것이 관찰 포인트이다.

그렇다면 한 string \(S\)의 대표원 \(r_{S}\)를 정해줄 수 있고, 편의상 사전 순으로 가장 빠른 string으로 정해주면 된다.

어떤 길이가 짝수인 string \(S = A + B\)에 대해서 \(r_{S} = \text{min}(r_{A} + r_{B}, r_{B} + r_{A})\)로 정해질 것이므로, 시간복잡도는 \(T(n) = 2T(\frac{n}{2}) + \) (문자열 비교하는 시간) \(O(n)\)을 만족하게 된다. 

답은 \(r_{S} = r_{T}\)이면 1, 아니면 0.

따라서 복잡도는 \(O(n \lg n)\).

768B. Code for 1

768B

\(r-l\)이 굉장히 작고, \(n\)이 무지막지하게 크니까 대충 \((r-l) \lg n\) 정도를 생각해볼 수 있다.

그리고 문제에서 주어진 배열의 생성 방식을 그대로 따라가면, single index \(k\)에 대해서 \(k\)번째 수가 마지막에 0일지, 1일지는 \(O(\lg n)\)만에 알 수 있다.

그래서 그냥 \(l\)부터 \(r\)까지 돌면서 0/1 여부를 판별하면, 시간복잡도 \(O((r-l)\lg n)\)만에 답을 구할 수 있다.  

448C. Painting Fence

448C

어떤 구간 \([s,e]\)를 칠할 때에 만약 '가로로 칠하기'를 쓴다면 \(\min(a_{s},a_{s+1},\cdots a_{e})\) 아래까지는 다 칠해주는 것이 최적임을 알 수 있고, 이를 \(a_{mi}\)라고 하면 다시 재귀적으로 \([s,mi-1]\), \([mi+1,e]\)를 칠하는 최적의 방법을 구하면 된다. (단 부분구간을 칠할 때에는 baseline이 0이 아니라 \(a_{mi}\)가 된다)

따라서 \(p(s,e,h)\)를 baseline이 \(h\)일 때 \([s,e]\)를 칠하기 위한 최소 비용이라고 하면

\(p(s,e,h) = \min(e-s+1, \ p(s,mi-1,a_{mi}) + p(mi+1,e,a_{mi}) + a_{mi} - h)\)가 된다.

base case는 \(p(s,e,*) = 0 (s > e)\). 

\(mi\)를 구할 때 naive로 구하면 \(O(n^2)\),

Segment Tree / Indexed Tree / Sparse Table을 쓰면 \(O(n \lg n)\)이다.