7/24 연습

*이 문제 set은 백준 온라인 저지에서 랜덤을 돌려서 푼 문제들입니다. 풀이를 좀 포멀하게 적고 싶어서 쉬운 문제라도 모두 풀이를 상세하게 기록할 예정이니, 그게 마음에 들지 않으신 갓갓분들은 살포시 뒤로가기를 눌러 주세요.

---

1. 수열 축소

문제 : http://icpc.me/2237

풀이 :

얘는 고1때 정올을 딱 시작할 때쯤 풀지 못하고 넘겨버린 문제. 사실 CON이란 연산이 전혀 대단하지 않다는 것만 알면 된다.

CON연산을 수행한 결과는 수열의 인접한 원소 사이에 + 또는 -의 부호를 적절히 삽입하여 계산한 식이다. (단, $a_2$앞에는 반드시 -가 붙는다) 그래서 $n \times (2\sum{a_{i}}+1)$ dp table을 잡고,

$dp(i,j) : a_{1}~a_{i}$까지 적절히 계산한 값이 $j$가 되게 하는 $a_{i}$의 부호로 생각하면 $O(n\sum{a_{i}})$시간 안에 dp table을 채울 수 있고, 답이 $dp(n,T)$에서 역추적을 하면서 각 수열에 붙어야 하는 부호를 알아낸다.

$dp(i,k)=+$인 경우, 왼쪽에 있는 가장 가까운 $dp$값이 -인 인덱스 $lm$에 대해 $CON(a,lm)$를 호출하면 된다.

$dp(i,k)=-$인 경우는 언젠가 $CON(a,1)$을 호출하면 된다. 

+인 경우부터 오른쪽에서 왼쪽으로 쫙 훑고, -의 개수만큼 1을 출력해주면 답이 된다.

Time Complexity : $O(n\cdot \sum{a_i})$

---

2. NMK

문제 : http://icpc.me/1201

풀이 :

쉽게 보고 풀다가 MWT 여러 번 낸 문제. 그리디에 왜 이렇게 약한지 모르겠다...

일단 그런 수열이 존재하지 않을 조건을 명확히 하는 게 중요하다.

(1) $M+K\ge N+2$인 경우, $LIS$와 $LDS$의 교집합에 최소 2개의 원소가 존재하게 되는데, 이를 $a_{i},a_{j} \quad(i<j)$라고 하면 수열 $a$에는 겹치는 원소가 없으므로

$a_i<a_j$인 동시에 $a_i>a_j$여야 하므로 모순.

$$M+K\le N+1$$

(2) $MK+1\le N$인 경우,

Erdos-Szekeres theorem ( https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem )에 의해 M+1 이상의 길이를 갖는 LIS, 또는 K+1이상의 길이를 갖는 LDS가 존재하게 된다.

$$MK \ge N$$

두 조건을 모두 만족할 경우 쉽게 수열을 construct할 수 있다.

$(t-1)K+1, (t-1)K+2, \cdots , N \quad (tK\ge N > (t-1)K)$

$K, K-1, K-2, \cdots ,1$

$2K, 2K-1, \cdots ,K+1$

$\cdots$

$(t-1)K, \cdots ,(t-2)K+1$

로 잡으면 된다. 아마도?

Time Complexity : $O(N)$