Atcoder Regular Contest 085

I. Introduction

이 포스트에서는 Atcoder.jp 에서 진행된 Regular Contest 085에 대해서 살펴봅니다.

 

II. Solve

[Prob C] – HSI

Takahashi는 현재 프로그래밍 대회에 참가 중이다. 그는 N개의 문제 중에서 M개의 문제를 각각 1900초 만에 1/2의 확률로 해결할 수 있고, 나머지 (N-M)개의 문제를 각각 100초만에 완전히 해결할 수 있다.

그가 대회를 진행하는 과정은 코드를 제출하고, 모든 테스트 케이스를 통과하지 못하면 통과할 때까지 다시 코드를 제출하는 것이다.  N과 M이 주어질 때 Takahashi가 이 문제를 통과하기 위해 걸리는 시간의 기대값을 구하여라.

 

문제 풀이

기본적인 무한 급수 문제이다. 문제의 수가 M개일 때 이 문제를 모두 맞출 수 있는 확률은 {( {1\over 2} )}^M 이다. 이 확률을 r 이라고 한다면, 총 시간의 기댓값

S = \sum_{k=1}^{\infty} {k * (M * 1900 + (N - M) + 100) * (1 - r)^{ k-1 } * r}

= r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {k * (1-r)^{ k-1 }} 이다.

 

S - (1 - r)S =  r * (M * 1800 + 100 * N) * \sum_{k=1}^{\infty} {(1-r)^{ k-1 }}

rS = r * (M * 1800 + 100 * N) * {1 \over {1 - (1 - r)}} 이므로

S = (M * 1800 + 100 * N) * {1 \over r}

을 출력하면 된다.

 

사용 알고리즘

  • 무한 급수

 

코드

 

[Prob D] – HSI

N개의 카드로 이루어진 덱이 있다. 각각의 카드에는 양의 정수 값이 적혀 있다.

두 명의 사람 X와 Y는 이 카드를 가지고 플레이한다. 가장 처음에 X와 Y는 하나의 카드를 들고 게임을 시작하며 각각 들고 있는 숫자는 Z와 W이다. 매 턴마다 플레이어는 현재 들고 있는 카드를 버리고 덱에서 최소 1장에서 원하는 숫자만큼의 카드를 위에서부터 뽑아 가장 마지막으로 뽑은 카드를 손에 쥔다.

모든 카드가 소진되면 게임은 종료되며 이 때 두 플레이어가 들고 있는 카드의 숫자 차이의 절댓값이 게임의 스코어가 된다. X의 목표는 스코어를 최대화하는 것이고, Y의 목표는 스코어를 최소화하는 것이다. 두 플레이어가 최적의 방식을 따른다고 할 때 게임의 스코어를 구하여라.

 

문제 풀이

선을 쥐고 있는 것이 X이므로 X의 입장에서 생각해보자.

  • X가 첫 턴에서 모든 카드를 다 뽑아버린다면 게임 스코어는 | D_n - W | 이다.
  • X가 첫 턴에서 하나의 카드만 남겨버린다면 게임 스코어는 | D_{n-1} - D_n | 이다.
  • X가 첫 턴에서 하나 이상의 카드를 남긴다면 위의 두 경우보다 큰 차이를 낼 수 있기 때문이다. 이 경우 Y는 이런 시나리오를 피하기 위해서 하나의 카드만 남겨버릴 수 있다. 이 경우 게임 스코어는 두 번째 경우와 동일한 | D_{n-1} - D_n | 이다.

따라서 게임은 X의 선택에 따라서 결정되는 것과 같으며 두 값 중 최댓값을 출력하면 끝이다.

 

사용 알고리즘

  • 게임이론

Leave a Reply

Next Article2017년 11월 26일 [D - 5]