1월 15일 Moscow IPT Contest 연습

 

 패널티가 과하게 높아서 엄청 잘했다는 생각은 들지 않습니다. 잘하는 팀들이 다 2명이라 제대로 된 비교도 안되고, Cxiv-Dxiv 팀과 4문제 차이를 내면서 부등호 놀이는 의미없다는 것을 다시 한 번 깨닫고 있습니다.

~1시간

 일단 앞쪽 문제인 J, K를 AC. A의 풀이가 나왔으나 증명을 정확하게 하지 않았고, 컴퓨터가 비어있어서 코딩을 시작. 하지만 42분째에 WA를 받고, 풀이와 코드가 모두 틀릴 가능성이 있는 상태가 됩니다.

그 사이에 G를 "해보니까 되던데" AC.

~2시간

 A의 증명을 짚어본 결과 틀릴 부분이 없었고, 코드를 확인한 결과 코드에서 틀린 것을 확인. 고쳐서 AC.

 그동안 상수가 B의 풀이를 생각하고 코딩하여 AC. I는 로컬에서 나오면 제출하기로 하고 코딩하여 AC.

 ~3시간

 상수와 도토리가 의논한 결과 D 풀이가 나왔으나 도토리가 구현 후 WA. 동시에 상수와 같이 H 풀이를 생각하여 AC.

 D를 로컬에서 이것저것 해본 결과 잘못된 부분이 몇 개 있었고, 고쳐서 AC.

~4시간

 일단 상수가 C에 확실히 틀리지만 맞을 수도 있는 풀이를 코딩. 상수와 도토리가 H와 D를 하는 동안 E의 풀이를 생각했고, 잠깐 스왑하고 도토리가 구현하여 AC. 

~5시간

 F의 아이디어를 도토리에게 전달했고, 케이스 분석의 경우가 엄청나게 줄어든 풀이로 구현하여 AC. 동시에 상수가 C에 "모든 테스트케이스가 5초 걸리는" 코드를 열심히 낸 결과 하나가 뚫려 AC.

 문제 각각에서는 실수가 조금씩 있었지만 실수 없는 연습이 거의 불가능하기 때문에 아쉽다는 생각은 들지 않습니다. 연습에서 실수가 많아야 대회때 별로 안하지 않을까 생각하고 있습니다.

---

이상한 문제 E 입니다.

자연수 n과, 확률 p1, ..., pn이 주어져 있습니다. (1 ≤ n ≤ 6, p1 + ... + pn = 1 ) 이 때 f(m)을 다음과 같이 정의합니다.

n*m 격자의 각 열에 대해 보석은 단 하나밖에 없으며, 첫 번째 행에 보석이 있을 확률은 p1, 두 번째 행은 p2, ..., n번째 행은 pn 입니다. 이 보석 배치에서 로봇은 첫 번째 열에서 출발하여 m번째 열까지 이동하면서 보석을 최대한 많이 모으는 것이 목표입니다. (로봇은 오른쪽, 오른쪽 아래, 오른쪽 위 3가지 이동이 가능합니다) 이 때, n^m개의 상태에 대해 로봇이 모으는 보석의 기댓값이 f(m)입니다.

우리가 구해야 하는 값은 다음 식입니다.

참고. 답은 P/Q로 표현 가능하다는 것을 증명할 수 있고, 이 때 P*Q^-1을 출력해야 합니다.

예제 입력

3 0.5 0 0.5 (소수점 아래 첫째자리까지만 입력으로 들어옵니다)

예제 출력

666666672

예제 설명

답은 2/3 입니다.

---

저번 GP of China 문제 풀이입니다.

Spanning tree의 개수를 구하는 문제이기 때문에 키르히호프 알고리즘은 무조건 사용해야 합니다.

파란색 간선을 정확히 b개, 초록색 간선을 정확히 g개 사용하는 Spanning tree의 개수를 A_bg라고 하면,

모든 파란색 간선을 중복간선 p개로, 모든 초록색 간선을 중복간선 q개로 바꾼 그래프에서의 Spanning tree 개수는 아래와 같고, 이 값은 키르히호프 알고리즘을 사용하면 구할 수 있습니다.

p, q를 820개 정도 선택하여 계산하면, 변수 A_bg가 820개 정도 있고, 식이 820개 정도 있는 선형방정식이 나옵니다.

가우스 소거법을 사용해서 풀면 모든 A_bg를 구할 수 있습니다.

---

17년도 Moscow International Workshop 등수를 찾아봤습니다. 

※ (Rating) = 100 * {(푼 문제수) / (1등이 푼 문제수)} * {(2 * (전체 팀 수) - 2) / (전체 팀 수 + 등수 - 2)}, ex. 1등 = 200