국대교육 일지 - 8/3 | Diuven’s Blog

오전 셋

알고스팟 10주년 대회 중 몇개를 돌았다. 2017년 여름에 열린 대회.

C. Computing MDSST
$O(2^N N^2)$ 로 DP를 하면 된다고 한다.

D. Dynamic Input Tool
그냥 앞에서부터 그리디하게 잡아주면 된다.

G. Game of Sorting
우선 모든 점에서부터 왼쪽 / 오른쪽으로 최대한 멀리 얼마나 갈 수 있는지를 체크한다. 이로서 끝난 상태는 판별할 수 있다.
배열의 상태에 따른 승패 함수를 생각해 볼 때, f(l,r)에 속한 가장 긴 정렬된 수열에 길이에 따라 몇가지 경우는 분리할 수 있다. 그 외의 경우는 f(l+1, r-1)의 상태와 같다. 한단계 더 내려가보면 알 수 있다.

L. LIS++
각 부분수열에 대해서, $O(NlogN)$ 으로 LIS를 구할 때 사용하는 그 배열여(‘목록’이라고 하자)의 최종 상태를 생각한다. 이 목록이 가질 수 있는 경우의 수는 $2^{10}$ 이므로, 이를 사용해서 $O(2^{10} N)$ 에 DP를 할 수 있다.

오후 셋

BOI 무언가를 돌았다.

Baltic OI 2007 Rankist Sorting
DP를 잘 돌리면 $O(N^2)$ 에 될수도 있고, 그냥 식을 써서 $O(NlogN)$ 으로 할 수도 있다고 한다. 모르겠다.
10년 전 문제인데..
Baltic OI 2018 Worm Worries
1,2,3차원에서 local maximum을 찾는 문제다. 쿼리 횟수를 최소화해야 한다.
1차원에서는 2개를 써서 1/2로 줄이거나, 1/3로 줄이는 것을 생각해 볼수 있는데, 그래도 안된다. 2개를 써서 줄이는 것이 아니라, 전에 사용한 쿼리를 재사용하는 것을 고려해야 한다. 비율을 잘 계산하면 황금비로 분할했을 때 충분히 적은 횟수로 돌아간다.
2차원에서는 이분 탐색을 잘 하면 된다. 한줄을 잡고 최대값 기준으로 분할하며, 다시 90도 돌려서 비슷한 짓을 계속해서 해주면 된다.
3차원에서는 초기에 랜덤으로 점을 선별한 다음에, gradient descent처럼 6방향 중 가장 큰 쪽으로 가면 된다. 계산해보면 충분히 큰 확률로 로컬 맥시멈을 구할 수 있다.
Baltic OI 16 Park
각 벽들 사이를 지나갈 수 있는지를 알고 있으면 된다. (설명이 어렵다. 위상적으로 지나갈 수 밖에 없는 간격은 뚫려 있어야 한다고 생각하면 편하다.)
모든 나무와 나무 사이, 혹은 나무와 벽 사이의 간격을 정렬하고, 지름이 작은 사람부터 처리하면서 union-find로 해주면 된다.

어려운 문제들이 많다. 뭔가 컴퓨터를 fully 사용하지 못하고 있는 것 같다. 랜덤스러운건 이것저것 시도해 봐야 하는데, 그게 편하지 않다.