some problem solving 2016.01

소수 없는 수열 (BOJ 4241)

https://www.acmicpc.net/problem/4241

백트래킹 노잼 ㅠㅠ

One way roads (BOJ 7724. CPSPC 2010)

https://www.acmicpc.net/problem/7724

그래프가 트리인 경우를 생각해 보자. 주어지는 쿼리들은 트리에 있는 정해진 간선들의 방향을 고정시킨다. 이것은 O(N)에 시뮬레이션할 수도 있지만, LCA를 구한 후, 변홧값만 칠해주면 O(lgN)에도 가능하다. (USACO Dec15 Maxflow 참고. http://usaco.org/index.php?page=viewproblem2&cpid=576) 모든 변홧값이 칠해지면, 두 방향 모두를 가르켜야 하는 에지가 존재할 경우 불가능. 한 방향만 가르키면 된다면 그 방향으로, 아니면 아무거나. 하면 된다.

그래프가 트리가 아닐 경우에는, 절선들만 따로 빼서, 절선들로 이루어진 트리를 만들어 주면 된다. 절선 안에 있는 컴포넌트들끼리 연결하는 방법은, 아무 DFS 트리나 잡은 후, tree edge는 깊이가 증가하는 순으로 잇고, back edge는 깊이가 감소하는 순으로 이으면 된다. dfs 트리에 절선이 없어서 이 경우 그 BCC는 SCC가 된다.

복잡도는 어림잡아 NlgN에 준한다. 코딩이 더럽다.

Free Goodies (BOJ 3662. NWERC 2010)

https://www.acmicpc.net/problem/3662

걸핏 보면 순서가 없다고 느끼기 쉽기 때문에 상당히 당황스러울 수 있지만 실제로는 Petra의 선호도 순으로 DP를 돌릴 수 있다.

Petra가 선호하는 순으로 정렬을 하자. Jan은 그 안에서 n/2개 언저리의 부분집합을 뽑아서, 자신의 이득을 최대화할 것이다. 해당 부분집합이 가능하려면, 선호도 순 prefix들에서, [Petra가 뽑은 물건수] >= [Jan이 뽑은 물건수] 여야 한다. (저 부등식은 정확하지 않다. 대충 감만 잡자.) Petra는 항상 Jan이 안 뽑은 것중에 선호도가 높은걸 뽑으려 할 것이기 때문에 저러한 부등식이 성립한다. 저 조건을 맞추는 형태에서 knapsack 스럽게 하면 된다. 복잡도 O(N^2).

저게 국대 멘토교육 문제라서, 사실 저 풀이 자체는 2015년 봄쯤에 생각했던 건데 그때는 계속 WA였던거 같다. 왜 틀렸는지는 모르겠고 다시 짜니까 되더라.

Artificial Lake (BOJ 6154. USACO Jan08)

https://www.acmicpc.net/problem/6154

KOI 2013 수족관과 비슷한 분할정복을 하면 무난하게 풀리는 문제이다. http://amugelab.tistory.com/entry/%EC%BC%80%EC%9D%B4%ED%81%AC-JOI-Spring-Camp-2013 랑 비슷하다고 할 수도 있겠다. 이 문제는 말보다 소스가 나은듯.

cpp : https://github.com/koosaga/olympiad/blob/master/USACO/jan08_lake.cpp

삼각형 (BOJ 3179. COI 2006)

https://www.acmicpc.net/problem/3179

처음에 BIT 쓰는 N^3lgN을 짰지만 TL이 났다. 이걸 짠 건... 아마 졸려서 제정신이 아니었던거 같다 -_-;;

N^3에 대해서 쉽게 생각할 수 있는건 모든 i -> j 벡터에 대해서 ccw 바깥에 있는 애들의 개수를 세고 빼는 알고리즘이다. 하지만 두번 빼지는 부분이 있고, 이러한 부분의 경우의 수가 N^3이라서 잘 안된다는 것을 알 수 있다. 조금 더 더럽지만 잘 작동하는 방법이 있다.

* 1. 모든 i -> j 벡터에 대해서 X좌표가 i, j 사이에 있으며, ccw 서쪽에 있는 애들을 precompute 해놓는다. precomputation은 N^3.

* 2. 모든 점 i에 대해서 X좌표가 같으며 i보다 Y좌표가 같은 점, 큰 점 역시 precompute 해놓는다. 이거 역시 N^2.

* 3. 모든 점 i에 대해서 X좌표가 작은 점, 큰 점을 precompute해놓는다. 이거 역시 N^2.

이렇게 N^3에 조금 더러운 precomputation을 하면 상수 시간에 포함하는 점을 구할 수 있으며, 복잡도는 O(N^3)이다. 생략한 case 좀 있을건데 걍 패스.

여기서 반전이라면, 사실 첫번째 방법을 대충 짜면 AC가 뜬다. 왜냐고? 두번 빠지는 부분이 있다는 것 자체가 그 점이 최적이 아니라는 것을 의미한다. 두번 빠지는 부분으로 가면 무조건 영역은 넓어지고, 그 쪽으로 삼각형을 변형하는 것이 무조건 이득..! 그러면, 그러한 최적이 아닌 해에 대해서는, 두번 빼는 페널티 정도는 상관없다. 전자의 코드는 아주 짧다.

마트료시카 (BOJ 8884. WF 2013)

https://www.acmicpc.net/problem/8884

문제를 딱 보면 기운이 온다 인접한 애들끼리 그룹을 합치는 거면 dp[i][j] = Min(i<=k<j) dp[i][k] + dp[k+1][j] + Cost(i, k, j) ... 실제로 그렇고 저걸 O(N^3)에 구현하면 된다. 잔 디테일이 조금 있는데 그걸 짚고 넘어가자.

* 1. dp[i, j]가 유효하려면 구간 [i, j]의 원소들은 서로 달라야 한다. 이건 N^3에 대충 precalc하면 그런지 알 수 있음.

* 2. Cost(i, k, j)를 구하는 방법 -> 두 subinterval을 합치는 건데, 두 subinterval중에 최솟값이 큰 애를 A, 작은 애를 B라고 두자, Cost(i, k, j) = |A| + |B| - |B에서 A의 최솟값보다 크기가 작은 원소| 이다. 상수 시간에 저걸 반환해야 하며 난 N^2 부분합 + N^2 RMQ 사용함. 여러 방법이 있을 것이라 생각된다.

* 3. dp[1, n]이 유효하다는 보장이 없다. 마트료시카를 단지 모든 수가 포함된 그룹 여러개로 묶어버리면 장땡이라.. 모든 수가 포함된 그룹임은, [i, j] 그룹의 원소들이 서로 다르며 [i, j]의 구간 최댓값이 j - i + 1이면 모든 수가 들어있다. 그러한 연속된 그룹으로 묶는 것은 dp2[i] = dp2[j] + dp[j+1, i] 라는 또 하나의 점화식으로 가능하다. 조건 체크를 발로 해도 O(N^3) 안에 나온다. 답은 dp2[n].