IOI 2012 - 크래이피쉬 글쓰는 기계

http://geniusainta.com/problems/view/IOI12_scrivener

IOI 2012 문제가 너무 신기하고 재밌어 보인다.

이거 포함 3문제 풀고 겨학가자 (가능할라나)

O(N^2) / 34점

헷갈리긴 하지만 하라는 대로 하면 된다

풀이

O(NlgN) / 60점

저걸 보면 prev 배열을 상당히 많이 부른다. 이걸 빠르게 해주는 방법이 있다.

처음에 노란 책(프로그래밍 콘테스트 챌린징)에서 봤을때는 응? 했었지만 이번에 직접 짜면서 감탄한 방법.

자료 구조라고 해야 하나... dp라고 해야 하나.. 아마 dp라고 하는게 맞을 거 같다.

N^2 풀이에 보면 prev[x]가 있는데 얜 코드를 이해했다면 알겠듯이 "x 앞에 붙어 있는 문자" 이다. 이걸 일반화해보자.

"prev[x][k] = x의 2^k번째 앞에 붙어 있는 문자."

일단 시간 복잡도 / 공간 복잡도 분석.

공간 복잡도는 2^k <= N이므로 N * K <= NlgN.

prev[x][0]이 주어졌을때, prev[x][i] = prev[prev[x][i-1]][i-1] 이라는 것을 알 수 있는데 둘은 이미 구해져 있으므로 시간 복잡도는 테이블당 O(1) 고로 NlgN.

할 수 있는건 두가지다.

1) x의 p번째 조상 찾기.

11번째라 하면, 1번째(2^0) -> 2번째(2^1) -> 8번째(2^3) 조상을 순서대로 찾으면 된다. 합하면 11번째.

많아야 lgN step이고 비트 연산으로 구현하면 된다.

2) 이진 탐색.

나는 이런 용도로 썼었는데, GetLetter를 호출할 때 "size가 일정 수 이상인 x의 가장 높은 prev"를 찾는 식으로 문제를 접근했다.

이렇게 됐을 경우 19부터 차례로 내려오면서 이진탐색을 하면 된다. 만약의 x의 2^i번째 조상이 조건을 만족한다면 x = prev[x][i]를 대입한 후 i-1에 대해서 계속 해 보고, 아니면 안 해보는 식, 이 방법을 통해서 O(lgN) 만에 쿼리를 처리할 수 있다.

종합적으로 세 함수 모두 lgN 스텝이므로 당연히 AC가 뜰 줄 알았는데 안떠서 슬펐다.

(acmicpc.net에서는 tle가 2초라 떴는데 GA는 가차없이.. ㅠㅠ)

풀이

3. 100점 / O(NlgN)

UndoCommands가 O(lgN)인 것은 우리가 undo만 하는 놈도 문자로 봐주기 때문이다.

얘를 문자로 보지 말고 테이블에 끼워넣지 말자. 

테이블에 끼워넣지 않는 건 그냥 하면 되는데 테이블에 접근하지 못하는건 또 다른 문제다. 이 때는 undo 대신 "undo를 타고 가면 도달하는 문자" 를 반환해주면 된다.

해당 원소에 접근했을 때 undo 직후 맨 뒤에 있는 문자를 나타내는 함수를 go[x]라 하면, go[x]만 사용하면 문자만 있는 테이블에 무리없이 접근할 수 있다. UndoCommands는 이때 go[x]만 설정해주면 O(1)에 처리 가능하다.

go[x]의 치역이 오로지 문자인 조건을 만족하는 경우를 "완벽하다" 라고 해보자. 일단 함수는 초기에는 무조건 완벽하다.

완벽한 상태에서 x가 undo인 경우가 들어왔다. 이 경우에 go[x] = go[x-U-1]이고 이는 문자를 가리킬 것이다. 여전히 완벽하다. 그러므로 이 함수는 항상 완벽하다.

그래서 go[x]는 완벽하고 따라서 UndoCommands는 O(1)에 처리 가능하다.

UndoCommands는 따라서 go[x] = go[x-U-1]; 이것만 하면 된다.

풀이

추가적으로 2^k table (sparse table이라고 한다. sparse하지 않은 테이블이라 마음에 안드는 이름이지만) 을 사용해서 풀 수 있는 문제들이 여러가지가 있는데, 대표적으로 LCA 문제를 요 테이블과 이진 탐색을 섞어서 풀 수 있다. 어렵지 않게 풀 수 있으며 RMQ보다 활용법이 훨씬 더 무궁무진한 거 같다.

http://koistudy.net/?mid=prob_page&NO=599

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

를 풀면서 연습해보자.