Codeforces Goodbye 2017 Contest

http://codeforces.com/contest/908

Result :

A, B, C(+3), D (4 / 8)

Rating Change :

1985 -> 2046 (+61, 343rd place)

Editorial : 

---

This section is intentionally left blank.

---

A. New Year and Counting Cards (04 : 52)

Tag : Implementation

A 답게 간단한 문제이다. 모든 홀수와 모음의 개수가 답이 된다. 대회에서는 문제 해석 + 코드 세팅하느라 시간을 많이 잡아먹었다.

B. New Year and Buggy Bot (20 : 24)

Tag : Brute - Force

B 답게 간단하...지만 일단 그리드이기 때문에 코딩이 빡친다. 다양한 구현 방법이 존재하겠지만, 나는 dx, dy 배열과 std::next_permutation을 사용해서 브루트 포싱을 짰다.

C. New Year and Curling (35 : 05) (45 : 00) (86 : 07)

Tag : Geometry, D**n Codeforces I/O

코드포스에서는 %.Lf 출력이 안됩니다

문제 자체는 C 치고 간단하다. 각각의 x좌표에 대해서 가장 위에 쌓인 원 중심의 \(y\)좌표를 저장하는 배열 top을 만든다. (초기값은 모두 0이다)

\(k\)번째 원의 \(x\)좌표를 \(x_k\), \(y\)좌표를 \(y_k\)라 하자. \(y_k\)의 초기값은 \(r\)이다.

\( j = max(1, x_{k}-2r) \cdots min(1000, x_{k}+2r)\)에 대해서 \(top[j] \ \neq 0\)일 경우에 \(y_k \leftarrow max(y_k, top[j] + \sqrt{4r^2 - (x_{k}-j)^{2}})\)를 반복해 주면 된다. \(y_k\)의 값이 결정된 후에는 \(top[x_{k}] \leftarrow y_{k}\)로 top배열을 갱신해 준다.

precision을 위해서 long double 타입을 사용했고, 출력을 %.10Lf로 한게 2틀의 화근이었다. %lld가 안된다고 했을 때 대충 눈치를 챘어야 하는데.... 무려 Pretest 1에서 WA를 받았다. 나중에 cout<<fixed와 cout.precision(10)을 추가했더니 바로 AC. ㅂㄷㅂㄷ...

Complexity : \(O(n \cdot (x+r))\)

D. New Year and Arbitrary Arrangement (71 : 27)

Tag : Combinatorics, Expectation, Dynamic Programming

굉장히 더러운 문제지만, C를 못 풀면 레이팅 떨각이라는 생각에 굉장히 절박했던 것 같다.

\((a,b)\)-부분수열의 개수를 편의상 '점수'라고 하자.

\(\frac{p_a}{p_a+p_b}\)를 \(r\), \(1-r\)을 \(s\)라고 표기하자.

\(f(i,j)\)를 문자열에 \(a\)가 \(i\)개 있고, 이미 얻은 점수가 \(j\)점일 경우에 추가로 얻을 수 있는 점수의 기댓값이라고 하자. 이때 \(i\)의 값에 따라서 DP를 쪼개야 한다.

* \(j >= k\)일 경우 \(f(i,j) = 0\)이다.

\(i = k\)

이 경우에는 \(b\)가 추가되기만 하면 시행이 종료된다. 따라서 기댓값을 그냥 수식으로 적을 수 있다.

$$ f(k,j) = sk + rs(k+1) + r^2 s(k+2) + \cdots  = k-1 + \frac{1}{s} $$ 

해석을 부여하자면, \(s\)의 확률로 시행이 끝나는 기하분포의 시행 횟수 기댓값 + \(k-1\)이 된다.

\(0 < i < k\)

이 경우에는 DP 점화식을 간단히 찾을 수 있다.

$$ f(i,j) = r \cdot f(i+1,j) + s \cdot (f(i,j+i) + i) $$

여기서 DP는 당연히 i, j가 감소하는 순서대로 채워야 하고, \(i\)가 최대 1 증가하기 때문에 toggling을 사용할 수 있다.

\(i = 0\)

DP 점화식도 그대로지만, 이 경우에 그냥 \(f(i,j+i) = f(i,j)\)가 되기 때문에 DP를 막 채우면 안된다.

수학적으로 \(f(0,j) = r \cdot f(1,j) + s \cdot f(0,j)\)에서 \(f(0,j) = \frac{r}{1-s} f(1,j) = f(1,j)\)가 됨을 보일 수 있다. 

우리의 답은 \(f(0,0)\)이지만, \(f(0,0) = f(1,0)\)이므로 \(f(1,0)\)을 출력하면 된다.

Complexity : \(O(k^2)\)

E, F, G, H는 나중에...