7/24 연습

2017. 7. 25. 16:39알고리즘 문풀/BOJ 연습

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




1. 수열 축소


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


풀이 :


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


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

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

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

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

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


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


2. NMK


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


풀이 :


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


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


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

ai<aja_i<a_j인 동시에 ai>aja_i>a_j여야 하므로 모순.

M+KN+1M+K\le N+1


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

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

MKNMK \ge N


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

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

K,K1,K2,,1K, K-1, K-2, \cdots ,1

2K,2K1, ,K+12K, 2K-1, \cdots ,K+1

\cdots

(t1)K, ,(t2)K+1(t-1)K, \cdots ,(t-2)K+1

로 잡으면 된다. 아마도?


Time Complexity : O(N)O(N)

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

7/30 ~ 7/31 연습  (0) 2017.08.01
7/29 연습  (0) 2017.07.30
7/27~7/28 연습  (0) 2017.07.29
7/26 연습  (0) 2017.07.27
7/25 연습  (0) 2017.07.26