DP problems.

They choose the coach’s burger. In this case, no further disruptions are caused and Josh gets his burger.

They choose Josh’s burger. In this case, no further disruptions are caused and Josh doesn't get his burger.

They choose someone else’s burger and create another disruption.

Optimal subquestion:

The ith person can get his favourite burger. Assume b[] is the list that is each person's favourite burger. b[0] is coach, b[n-1] is Josh.

f(i) = 1 if b[i] = b[0]

f[i] = f[last[i]] if b[i] is in the last list that is the most right side person faourite burger that is same as ith

f[i] = (1+c)/(n-i) , c is the sum of problity of from n-2 to i.

The result is (1+c)/n.

```
import sys
input = sys.stdin.readline
n = int(input())
b = list(map(int, input().split()))
dp = [0] * n
c = 0
last = {b[-1]: n - 1}
if b[-1] == b[0]:
dp[-1] = 1
c += 1
print("{:.8f}".format(c))
else:
for i in range(n - 2, -1, -1):
if b[i] == b[0]:
dp[i] = 1
elif b[i] in last:
dp[i] = dp[last[b[i]]]
else:
dp[i] = (1 + c) / (n - i)
c += dp[i]
if b[i] not in last:
last[b[i]] = i
print("{:.8f}".format(c / n))
```

This is 15 marks solution.

## コメント