* 30분 ~ 60분 : C 아이디어 나오고 코딩 준비 완료. 혜아 초반부터 BEF 잡다 멘붕. 민규 I 디테일을 정리
* 60분 ~ 75분 : C 코딩하고 예제 맞왜틀. D가 쉽다는 제보 도착
* 75분 ~ 90분 : 민규 D 코딩
* 90분 ~ 92분 : C 몇글자 고치고 AC
* 93분 : D AC
* 93분 ~ 120분 : 민규 I 코딩후 맞왜틀. 내가 L을 포함배제로 조지면 될것 같다는 아이디어 냄. 관찰 몇개 한 후 혜아한테 넘겨줌.
* 120분 ~ 150분 : 구사과 H 코딩후 맞왜틀. (2차 멘탈붕괴)
* 150분 : I 고침
* 150분 ~ 170분 : 혜아 L 코딩 들어갔... 는데 풀이 깨짐. 대신 K 풀이가 있어서 그걸 하기로 함
* 170분 ~ 190분 : K 코딩. 난 H 못찾아서 멘붕
* 190분 ~ 197분 : 1시간 쳐다보다가 결국 찾아냈고 고쳐서 AC. 멘탈 박살남. K 코딩 계속 진행
* 205분 : K AC
* 215분 : 이쯤 프리즈
* 205분 ~ 220분 : 내가 E 문제 설명들음. 개쉬움 (3차 멘탈붕괴). 바로 코딩후 AC
* 220분 ~ 235분 : L 다시 생각해보니까 포배 ㄴㄴ 심플DP ㅇㅇ (4차 멘탈붕괴). 바로 코딩후 AC
* 235분 ~ 245분 : G DP테이블 나오니까 규칙이 꽤 이쁘게 나옴. 혜아한테 넘김
* 245분 ~ 275분 : 혜아가 N = 40정도 데이터를 넣고 화가의 심정으로 (...) DP테이블을 예쁘게 따라그림. 그 사이에 민규랑 F 고민
* 275분 ~ 285분 : 민규랑 내가 F 포기하고 백수질.
* 285분 ~ 290분 : G DP테이블 규칙 찾고, 나이브한 코드를 약간 고침
* 290분 ~ 300분 : G WA받고, 맞왜틀과 실수의 갈등 사이에서 헤메다가 게임 오버
* 300분 ~ 390분 : 동방에서 스코어보드 보면서 피자먹음
* 390분 ~ : 핵꿀잠 (...)
제5회 크리콘처럼 일부 문제에 대해서만 간단히 소감을 쓰려고 한다. 스포일러 주의.
C. Computing MDSST
셋에서 가장 재밌었던 문제였던 것 같다. 아마..?
일단 어떤 트리가 주어질 때 Distance Sum은 다음과 같이 계산할 수 있다. 임의의 정점을 루트로 잡은 후 서브트리 사이즈를 계산하면, 모든 {par[v], v} 를 잇는 에지에 대해서 $weight * |subtree(v)| * (n - |subtree(v)|)$ 의 합이 된다. 각각의 path에서 한 에지가 몇번 쓰였는지를 세보면 저런 결론이 나온다.
$DP[S][root]$ = ($S$의 정점들을 모두 spanning하고, root를 루트로 가지며, 저 합을 최소화하는 트리) 라고 하자. $DP[V(G)][*]$ 중 최소가 답이 될 것이다. 이 DP는 이렇게 계산하면 된다.
* base case : $|S| = 1$, 답은 당연히 0
* 그렇지 않다면, root와 연결된 에지가 하나 있을 것이다. 이 에지가 다른 정점 v와 연결되어 있고, v의 서브트리가 $T \in S\setminus\{v\}$ 라 하자. 해당 에지에서 얼마의 추가 cost가 소모되는지는 저 식을 통해서 알 수 있다. 고로 이 부분집합 T와 정점 $v$를 고정시켜주면 문제를 O(4^N * N^2)에 풀 수 있다.
이제 시간 복잡도를 줄여보자.
* 먼저 S의 부분집합 T를 나열하는 것은 사실 $O(3^N)$이다 (쓸데없는 것을 나열하지 않았다면). $S$의 모든 부분집합 $T$에 대해서 $2^|T|$의 합인데, 이걸 $|T|$의 크기를 고정시키고 전부 더하면 $\sum_{i=0}^{N}{2^i * nCi}$ = $3^N$ 이 된다 (이항 정리 - http://koosaga.com/190 4번).
* root에서 뗄 서브트리와 루트를 고정시키는데, 각각의 루트 / 서브트리에 대해서 그 서브트리를 최적으로 연결하는 새로운 루트를 전처리할 수 있다. 이 전처리는 $O(2^N * N^2)$에 가능하다. 고로 $O(N)$ factor가 사라진다.
E. Earthquake
몇가지 관찰 :
* 한 route를 보기 시작하면 그 route에서 답을 찾거나 망하기 전까지는 그 route만 계속 보는 게 최적
* route를 하나 볼 때에는 가장 무너질 가능성이 큰 것부터 두드려 보는게 최적
이제 모든 $N!$개의 route를 보는 순서에 대해서 brute force를 해 보자. $EXP[i]$ = $i$번째 route에서 쓸 시간의 기댓값이라 하면, $EXP[i] = (1 - p1) * (EXP[i+1] + 1) + (1 - p2) * p1 * (EXP[i+1] + 2) + (1 - p3) * p2 * p1 * (EXP[i+1] + 3) + \cdots$ 과 같은 식이 나온다. 결국은 $EXP[i] = F[i] * EXP[i+1] + G[i]$ 와 같은 식으로 정리가 된다. $F[i]$와 $G[i]$를 전부 계산하면...
이제 $EXP[1]$을 최소화하는 $F[i]$와 $G[i]$의 ordering을 찾아야 하는데 이건 그렇게 어렵지 않다. 링크 참조.
H. Hole in a Circle
일단 여기서 중요한 것은 각도 차가 가장 큰 두 집 쌍 뿐이다. 문제 조건이 약간 복잡하지만 어떤 상황에서도 각도 차가 가장 큰 쌍만 봐도 된다는 것은 직관적으로도 알 수 있고 수식으로도 보일 수 있다. 각도 차를 알면 삼각 함수를 사용해서 거리를 O(1)에 구할 수 있다. 고로 최대 각도 차만 고려하자.
쿼리 1만 들어온다고 가정하자. 만약 balanced binary search tree에 집들의 위치를 전부 관리하고 있다면, 새로 들어온 집과 가장 각도가 큰 다른 집을 빠르게 찾는 것은 lower_bound 연산으로 $O(lgN)$ 정도에 할 수 있고, 고로 $O(QlgN)$에 할 수 있다. 문제는 쿼리 2가 들어온다는 점인데, 어떠한 Insertion만 되는 자료 구조가 주어졌을 때, 오프라인으로 이 자료구조가 Insertion / Deletion 모두 지원할 수 있게 바꾸는 일반적인 방법이 존재한다. 이에 대해서는 koosaga.com/121 이 도움이 될 것이다. (이번에도 믿고 보는 koosaga.com!!) 이러면 로그가 하나 더 붙어서 $O(Qlg^2N)$ 이다.
여담으로 내가 실수해서 1시간 이상 날려먹은 것은 저 balanced binary search tree를 관리하는 과정이었다. 원이어서 헷갈렸는데.. 아.. 대전에서 저런 실수 하면 정말 재앙 그 자체일 것 같다.
K. Korean RPG
내가 푼 문제는 아니다. 하지만 크게 복잡하지는 않다고 알고 있다..
$Exp[n] = 0, Exp[i] = Min_{k}{(\sum_{j}{A_{k, i, j} * Exp[j]})}$ 와 비슷한 점화식을 해결하는 문제다. 실제로는 이것보다 조금 더 복잡하다.
저런 류 문제는 가우스 조던으로 잘 풀리는데 이 경우에는 min 항이 들어가서 골치아프다. DP를 50000번 돌리면 되지 않을까 (...) 라는 게 처음 관찰이었으나, Min() 항을 $Exp[i] \leq \sum_{j}(Exp[j] * f(j))$ 로 바꿀 수 있기 때문에, 선형 부등식들의 조합으로 바꿔서 simplex method를 돌리면 된다. 가우스 조던에서 바뀐 것은 Min 항으로 인해서 방정식이 부등식이 됐다는 것 뿐이다.
L. LIS++
$O(NlgN)$에 LIS를 찾는 알고리즘으로, lower_bound를 해서 어떤 정렬된 배열을 관리하고, 그 정렬된 배열의 크기를 계산하는 방법이 존재한다. 설명은 http://dyngina.tistory.com/16 의 1번 단락을 참조하라.
$2^N$ 크기의 부분수열을 모두 백트래킹으로 나열한다고 생각해 보자. 각 위치에서 부분수열의 끝 원소를 정렬된 배열에 넣을 수도 있고 안 넣을 수도 있고. 결국 중요한 것은 현재 위치와 정렬된 배열 두가지 뿐이다.
그런데, v는 중복된 원소가 없는 정렬된 배열이다. 고로 그냥 집합으로 간주해도 무방하다. 집합도 크기가 10 이하일 테니 bitmask로 관리하면 된다. 그러면 저 과정 전부를 메모이제이션 할 수 있고 시간 복잡도가 $O(N * 1024)$로 갑자기 줄어버린다. 끝..
FORTRESS2는 채점에 문제가 있으니 일단 생략 (비슷한 문제이며 난이도 (특히 코딩 난이도)가 조금 더 낮은 BOJ 14968을 추천한다.)
KEDIT은 시간 제한이 너무 빡빡한 면이 있긴 한데.. 간단히 풀이를 쓰자면
KEDIT은 각각의 문자열 pair를 모두 순회하면서 해결해도 괜찮다. |S|와 |T| 사이의 edit distance가 k 이하인지를 200번 정도의 상수 연산안에 해결해야 하는데 놀랍게도 그게 되기 때문이다.
DP[i][j][k] = (S[0, i-1]과 T[0, j-1]이 k 이하의 edit distance로 매칭되는가?) 라고 정의하면, 상태 전이를 어렵지 쓸 수 있다. 이 DP 테이블이 불리언이니 비트마스크를 통해서 최적화할 수 있는데, DP2[j][k] = (DP[i][j][k]가 true인 i의 집합) 라고 한 후 bitwise operation만으로 DP 상태 전이를 할 수 있다. 실질적으로 bitset과 거의 비슷하게 사용한다. 이렇게 해도 약간 느리기 때문에 상수 최적화를 조금 더 해야 하긴 한다.
