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)\)