Thursday, August 27, 2015

Latin America Regional Contests 2010 G번(BOJ 5699번)

문제 링크(acmicpc.net 5699번)

Aho-Corasick 알고리즘으로 풀 수 있다.

주어지는 입력 문자열들로 트라이를 구성하고, 기존의 노드(x)에서 새로 뻗어나가는 노드(y)의 실패링크(yf) 걸어줄 때

d[y] = max(d[x], d[yf]) + "노드 y에서 끝나는 string의 개수"

O( 문자열의 길이의 합 ) 에 해결할 수 있다.

내 소스 코드

Wednesday, August 26, 2015

Coder's High 2013 J번 Bookthief

평범한 0-1냅색이라고 가정하면 다음과 같은 DP식을 세울수있다.

D[N,V] := N종류의 아이템에 대해 고려해서, V칸을 채웠을때의 최대 값어치
D[N,V] = max{D[N−1,V],D[N−1,V−(volume of item)]+(value of item)}

vi=(volume of item), ci=(value of item)이라고 하고, 아이템의 갯수를 ki라 하자. 위의 식에서 0-1을 0-k로 확장시킨다는 느낌으로 식을 바꿔 써보면,

D[N,V] = max{D[N−1,V],D[N−1,V−vi]+ci,D[N−1,V−vi×2]+ci×2, ... ,D[N−1,V−vi×ki]+ci×ki}

묶어서 쓰면 다음처럼 쓸수있다.

D[N,V] = max{D[N−1,x]+(V−x)/vi×ci} (단,x≡V mod vi이고,V−vi×ki≤x≤V이다.)

x에 대한 식만 남기고 V에 대한 부분은 밖으로 뺄 수있다.

D[N,V] = max{D[N−1,x]−x/vi×ci}+V/vi×ci

f(x) = D[N−1,x]−x/vi×ci 라고 하자.

그렇다면 D[N,V]를 다음과 같이 구할수 있다.

1. f(V)값을 PQ에 넣는다.
2. PQ의 top인 x값이 V와 vi×ki를 넘게 차이나면 top을 제거한다
3. PQ의 top인 f(x)값에 대해 D[N,V]=f(x)+V/vi×ci이다.

최대 PQ의 크기는 O(V)이므로, 시간 복잡도는 O(NVlgV)이다. 이렇게 작성해도 AC를 받기엔 충분한 속도지만, 조금 더 속도 향상을 할 수 있다. PQ안에 있는 2개의 t1 < t2에 대해 생각해보자. 만약 f(t1) < f(t2)라면 t1은 PQ의 top이 영원히 될수 없다. 그러므로 이러한 t1은 전부 배제되었다고 가정하면,

1. PQ안 원소들의 x값들을 순서대로 x1<x2<x3..라 하면
2. f(x1)≥f(x2)≥f(x3)≥...을 만족한다.

또한 위의 조건을 만족하도록 PQ를 관리하여야 한다. 이러한 구조는 선형 deque로도 관리할수있으며, 매 원소는 최대 한 번 삽입과 삭제가 발생하게 되므로 이때의 시간 복잡도는 amortized O(NV)이다.

Saturday, August 1, 2015

KOI 2005 고등부 3번 - 소방차

문제 링크
우선 가장 쉬운 건 O(NM)의 dynamic programming.
D(i, j) = min(D(i-1, j), D(i,j-1), D(i-1,j)+|P(i)-F(j)|).
D(i-1, j)랑 D(i, j-1)을 참조할 때는 min(i-1, j-1)+1과 같은 지 확인하면서 compute하면 된다.

그런데 사실 해법은 dynamic programming과는 다르게 greedy method이다.

펌프 2개 P1<P2가 있고, 소방차 2개 F1<F2가 있다고 하자.
만약 이 펌프들과 소방차들을 이어주는데, 가능한 구간을 고려해보자.
P1<P2<F1<F2일 때 (F1-P1) + (F2-P2) = (F2-P1) + (F1-P2).
P1<F1<P2<F2일 때 (F1-P1) + (F2-P2) < (F2-P1) + (P2-F1).
따라서 구간이 일부분만 겹칠 필요없이, 완전히 포함되거나 독립적이다.

그래서 생각해낸 것이, 구간이 완전히 안에 포함되는 쌍은 바깥쪽 쌍보다 위상이 더 높다고 한다면, 같은 위상 상에서는 완전히 독립적인 구간들 밖에 없어서, 선형 시간에 서로 다른 인접한 원소들을 잘 짝지어서 그 쌍의 합들이 최소화할 수 있게 된다.

위상을 numbering하는 방법은, 펌프들의 위치와 소방차들의 위치를 다 모아놓고 위치순으로 정렬한 다음에, 연속해서 펌프나 소방차가 나온다면, 각각의 경우에 대해 위상의 증감을 반대로 누적해주면 된다.

각 위상마다 애들을 위치순으로 보면 P로 시작해서 F와 P가 번갈아 등장하다가 P로 끝날수도 있고, F로 끝날 수도 있다. (F로 시작하는 건 P로 시작하는 것과 똑같이 처리하면 되므로 일단은 생략)
만약 P로 시작해서 F로 끝나면 그냥 처음부터 보면서 (i+1)번째와 i번째를 짝 지어주는 게 최선이다. 왜냐하면 가능한 짝은 다 지어야하므로.
만약 P로 시작해서 P로 끝난다면 중간에 빈 원소가 하나 생기게 되므로 기존의 인접한 짝들을 지은 것에다가, 끝에서부터 엇갈리게 보면서 새로운 쌍을 이어주고, 기존의 쌍을 없애줄 수 있다. 그 작업을 매번 할 때마다 부분해를 갱신해주면 된다. 그림으로 표현하면 아래와 같다.

따라서 전체적으로 정렬을 사용한다면 O( (N+M) log (N+M) )에 풀 수 있고, 위상에 따라 카운팅 소트하듯이 하면 O(N+M)에 해결할 수 있다.