A, B는 어렵지 않게 풀었다. C는 실수가 나와서 당황했는데, 어쨌든 오차가 아주 중요한 문제는 아니었다. D는 interactive형 문제였는데, 처음 보는 형태라서 조금 얼탔다. E는 튜토리얼을 읽고 업솔빙 중이다. A는 00:05에, B는 00:11에, C는 00:39에, D1은 01:05에, D2는 01:38에 풀었다. E는 풀지 못했다.
최종적으로 58위가 되었고, 아주 좋은 결과라고 생각한다.
1543A Exciting Bets
는 불변량이다. 이면 를 증가시킬 때 흥분excitement도 항상 증가하고, 팬들은 무한한 흥분을 얻는다. 일 때, 를 조작하여 모두 의 배수가 되도록 하였을 때 이다. 보다 큰 수 에 대해 를 로 나눈 나머지가 다르므로 이는 의 최대공약수가 될 수 없다. 따라서 흥분의 최댓값은 가 된다. 가 의 배수에 이르기까지 조작이 덜 필요한 쪽을 선택하여 증가시키거나 감소시키면 된다.
1543B Customising the Track
가 오름차순으로 정렬되어 있다고 가정하자. 인 경우, 을 각각 으로 바꾸었다고 하자. 을 만족하는 의 최댓값을 , 을 만족하는 의 최솟값을 라고 하자. 이므로 이다. 값을 변경하였을 때 불편inconvenience의 변화량을 다음과 같이 계산할 수 있다.
, 으로 변경했을 때 불편의 변화량은 이 된다. 배열을 다시 정렬했을 때 인 한, 불편을 계속하여 감소시킬 수 있다. 따라서 가 되는 분배는 최적해가 아니다.
라고 가정하면, 이를 만족하는 분배는 의 형태이다. 와 의 개수가 각각 일 때 원하는 답은 이다. 일 때, , 이다.
1543C Need for Pink Slips
기댓값의 의미를 잘 생각하고, 문제에서 주어진 설명을 잘 따라서 재귀 함수를 잘 구성하여 완전 탐색으로 풀 수 있다… 실수 오차나 스택 오버플로우 등을 상상하면 두려워지는데, Pink Slip를 뽑지 않을 때마다 Pink Slip을 뽑을 확률이 적어도 0.05 증가하므로 많아야 20단계 내에 끝나게 된다.
1543D RPD and Rap Sheet
비밀번호를 로 추측할 때마다, 틀린 추측이라면 원래 비밀번호 는 를 만족하는 로 바뀐다. 를 번 -itwise XOR한 것을 로 표기하자. 즉, 인데 우변의 식에서 는 번 등장한다. 를 관찰하자.
양 변에 를 번 취하여
를 얻는다.
번째 추측을 으로 하자. 에 대해, 번째 추측을 으로 하자. 원래 비밀번호를 라고 하자. 번째 추측에 비밀번호를 틀렸을 때, 바뀐 비밀번호가 라고 가정하자. 만약 이면, 번째 추측에서 비밀번호를 맞추게 된다. 이면 다음 비밀번호는
이고, 이를 정리하면 이 된다. 원래 비밀번호는 에 있으므로, 귀납법을 통해 에 대해 번째 추측을 시도하였을 때 이 중 한 번은 옳은 추측임을 알 수 있다.
임의의 에 대해 이므로, 이를 이용하여 번째 추측 를 계산해서 1을 입력받을 때까지 출력하면 된다.
