World Finals Problems

ICPC 월드 파이널 2017 주간이 다가와서 최근 옛날 기출문제를 풀어보고 있다. World Finals 2008도 opencup 팀연습으로 돌았었는데, 문제가 좋다는 느낌은 안 들었다. 특히 어려운 문제들이 찍어 맞춰라 / 단순 코딩 지옥이라 불만족스러웠음.

이번 ICPC에서 한국 팀들의 성적이 그 전과 비교가 안 될 정도로 우수하다. 어느 정도 훌륭할 것이라고 예상은 했지만 이 정도일 것이라고 예상한 사람은 아무도 없었을 것이다. 팀원들이 대부분 젊은데, 앞으로도 많은 활약을 기대해 본다.

2011 G. Magic Sticks

일단 모든 막대기를 사용해야 하는 상황이라고 가정해보자. 넓이를 최대화하려면 모든 정점을 원 위에 뿌려주는 것이 최선이다. 직관적으로 그럴듯 해 보이긴 하는데 증명은 음.. 암튼 그게 최선이니 이러한 원을 구하는 방법에 대해서 알아보자.

원을 구하기 위해서는 원의 반지름을 가지고 이분 탐색을 하면 된다. 반지름이 너무 커지면 원을 만들 각도가 불충분해지기 때문에 이를 토대로 이분 탐색이 가능하다. 케이스가 두가지 있는데, 하나는 원의 중심이 다각형 안에 있을 수 있는 경우, 또 하나는 그럴 수 없는 경우이다. 구분할 수 있으니 잘 구분하자. 이 정도 관찰만 해도, DP에 섞으면 O(n^3lg(eps)) 인데, 시간 안에는 당연히 안 돈다...

이를 최적화 하기 위해서는 또 하나의 관찰이 필요하다. 현재 골라야 하는 막대기 셋에서, 최댓값을 가지는 막대기를 중심으로 생각해보자. 이 막대기를 제외하고 나머지 막대기들은 자유자재로 아래에 원호처럼 끼워넣을 수 있고, 이는 넓이를 증가시킨다. 고로 최댓값을 가지는 막대기를 넣었다면 모든 막대기를 넣는 것이 이득이다. 그렇다면, 모든 막대기를 넣지 않는다는 것은, 최댓값을 가지는 막대기를 넣지 않는 것이라고 해석할 수 있다. 이는 양 옆에 두개의 subproblem으로 문제를 쪼갠다. 시간 복잡도는 O(n^2lg(eps)) 로 줄어들고 이제 DP는 딱히 필요 없다.

저 문제를 풀때 DP 풀이에 갇혀서 다른 생각을 하지 못했다. 그래서 풀이를 봤을 때 너무 슬펐다. 발전이 필요하다. 

2013 B. Hey, Better Bettor

플레이어가 선택할 수 있는 것은 딱 하나다 : 한 판 더 하거나, 카지노를 나오거나. 또한 각각의 게임은 독립이기 때문에, 플레이어가 현재 상황에서 결정을 내릴 때 고민해야 할 유일한 인자는 바로 "현재의 금액" 이다. 즉, "전략" 이라는 것은 현재의 금액이 주어졌을 때 게임을 할 것이냐 안 할 것이냐를 결정하는 함수라고 할 수 있다.

이 함수에 대해서 관찰을 해보자. 먼저 0달러일 때는 무조건 게임을 한다. (안 할수도 있겠지만 이건 예외처리를 해주자.) 현재 돈이 어떠한 양수이고, 플레이어가 게임을 포기했다고 하자. 해당 양수를 X라고 했을 때, X+1 이상의 전략은 필요하지 않다 (그 전에 포기해 버릴 테니까). 음수에서도 이는 마찬가지이다. 고로, 전략이라는 것은 단순히 두 개의 정수로 나타낼 수 있으며, A달러 이상을 잃었을 때 / B달러 이상을 벌었을 때 게임을 포기한다 의 형태로 표현된다. 전략의 표현 방법이 아주 간단함을 알 수 있다.

또한 x와 p가 클수록, 플레이어는 카지노에서 더 많은 리스크를 부담하려 할 것이며 (즉, 더 큰 A가 전략으로 사용 가능), 만약 돈을 벌고 있는 상황이라면 더 벌 수 있다는 희망을 줄 것이다 (즉, 더 큰 B가 전략으로 사용 가능). 이렇게 계산해 보면 A와 B의 하한이 나온다고 하는데 솔루션을 보니 이 수가 20528 / 2498 정도라고 한다. 49.90이라는 오묘한 숫자 덕분에 이러한 하한이 나오는 거 같은데 아무튼 이 덕에 모든 가능한 전략을 다 시도해 볼 수 있다.

이제 전략이 주어졌을 때 기댓값을 계산해야 하는데, P(X)를 현재 X달러가 있을 때 B달러에서 게임을 끝낼 확률 이라고 정의하자. P(B) = 1, P(-A) = 0이며, 우리가 계산해야 하는 것은 BP(0) + A(1 - P(0)) * (1 - x / 100) 이다. P(X) = p P(X + 1) + (1 - p) P(X - 1) 이다. 피보나치 일반항 유도하듯이 P(X) = a + b * (??) ^ X 와 같은 형태로 유도시킬 수가 있고, 미정계수 법으로 a하고 b를 구하면 O(1)에 기댓값을 구할 수 있어서 풀 수 있다. 어렵고 신기한 문제였다. 

2014 E. Maze Reduction

아무리 생각해도 못 풀겠어서 풀이를 봤던 문제였다. 그 풀이가 상당히 신기해서 적어둠.

각각의 정점의 상태를 어떠한 숫자로 표현한다고 하자. 해당 정점에서 D번의 이동을 통해서 알아낼 수 있는 상태 -> 해당 정점에서 D+1번의 이동을 통해서 알아낼 수 있는 상태, 와 같이 이 숫자를 업데이트해 줄 것이다. 일단 해당 정점에서 0번의 이동을 통해서 알아낼 수 있는 상태는 degree뿐이니, 여기서 시작을 해 보자. 

새로운 상태를 부여할 때, 인접한 정점들에서 D번의 이동을 통해서 알아낼 수 있는 상태를 계산해 줄 수 있다. 이를 순서대로 문자열로 저장했다고 하자. 정점 u, v가 D+1번의 이동에서도 같으려면, 일단 현재의 상태가 같고, 또한 u의 문자열을 적당히 cyclic shift해서 v의 문자열을 만들 수 있어야 한다. 이렇게 새로운 상태를 부여할 수도 있고, 다음 업데이트가 없을 때까지 계속 돌려주면 답이 나옴을 알 수 있다. 

업데이트 횟수가 관건인데 별로 안 되는 거 같다. 그런 데이터를 주기 쉽지 않은가 본데 아무튼 정말 대충 해 줘도 됐다. 필요하다면 해싱을 쓸 수도 있겠다. 여담으로 DFA minimization이라는 문제가 이거랑 비슷한 문제인 거 같은데 위키백과 보니까 상당히 유명한 것 같다. 옛날 NEERC에 비슷한 문제 위키백과

2015 H. Qanat

n-1개의 shaft로 만들어진 qanat solution을 통해서 n개의 shaft로 만들어진 qanat solution을 construct하는 것이 풀이의 열쇠이다. 놀랍게도 qanat이라는 구조가 약간의 귀납적인 형태를 가지기 때문이다.

가장 오른쪽에 사용한 통로를 생각해 보면, 이 통로를 기준으로 왼쪽에는 n-1개의 솔루션으로 이루어진 똑같은 qanat이 있고, 그의 오른쪽에 무언가를 붙이는 형태로 문제를 해석할 수 있다. 다른 말로 하면, n-1에서의 최적해를 r배 축소시켜 왼쪽에 넣고, 오른쪽에 mother well을 넣는 식으로 새로운 qanat을 만들 수 있을 것이다. 

r을 고정시키고 n에서의 최적해의 cost를 계산해 보면, r에 대한 이차함수로 cost가 나옴을 알 수 있다. 이차함수의 유일한 최솟값을 식을 쓰거나 삼분 탐색을 쓰는 등으로 구할 수 있다. (식 더러우니 삼분탐색 추천) 위치를 구하는 것도 어렵지 않다. 다만 개인적으로 long double을 써야 AC가 나왔다.