Problem:


Score : 100 points

Problem Statement

There are N dishes, numbered 1, 2, \ldots, N.
Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.

Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:

Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.

Find the expected number of times the operation is performed before all the pieces of sushi are eaten.

Constraints

All values in input are integers.

1 \leq N \leq 300

1 \leq a_i \leq 3

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the expected number of times the operation is performed before all the pieces of sushi are eaten.
The output is considered correct when the relative difference is not greater than 10^{-9}.

Sample Input 1

3
1 1 1

Sample Output 1

5.5

The expected number of operations before the first piece of sushi is eaten, is 1.
After that, the expected number of operations before the second sushi is eaten, is 1.5.
After that, the expected number of operations before the third sushi is eaten, is 3.
Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5.

Sample Input 2

1
3

Sample Output 2

3

Outputs such as 3.00, 3.000000003 and 2.999999997 will also be accepted.

Sample Input 3

2
1 2

Sample Output 3

4.5

Sample Input 4

10
1 3 2 3 3 2 3 2 1 3

Sample Output 4

54.48064457488221



Sample input:
3
1 1 1


Sample output:
5.5

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 3:
        I += 1
    elif a[i] == 2:
        J += 1
    elif a[i] == 1:
        K += 1

DP = [[[-1 for i in range(N+1)] for i in range(N+1)] for i in range(N+1)]
DP[0][0][0]=0

def cal(i,j,k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    else:
        res = 0
        if i != 0:
            res += i*cal(i-1,j+1,k)
        if j != 0:
            res += j*cal(i,j-1,k+1)
        if k != 0:
            res += k*cal(i,j,k-1)
        res += N
        res /= i+j+k
        DP[i][j][k] = res
        return res

print(cal(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(q) for q in input().split()]
#a = list(map(int, input().split()))
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[n] * (n+1) for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(min(l-k, Tw+Th)+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			#dp[i][j][k] += n
			dp[i][j][k] /= l

print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(q) for q in input().split()]
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[0] * (n+1) for _ in [0]*(n+1)] for _ in [0]*(n+1)]
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(min(l-k, Tw+Th)+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i/l
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j/l
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k/l
			dp[i][j][k] += n/l

print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(q) for q in input().split()]
#a = list(map(int, input().split()))
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[0] * (n+1) for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(min(l-k, Tw+Th)+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(q) for q in input().split()]
#a = list(map(int, input().split()))
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[0] * (n+1) for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(l-k+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(q) for q in input().split()]
#a = list(map(int, input().split()))
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[0 for _ in [0]*(n+1)] for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(l-k+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
On = a.count(1)
Tw = a.count(2)
Th = n-On-Tw
dp = [[[0 for _ in [0]*(n+1)] for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(l-k+1):
			i = l-k-j
			if k > Th:
				continue
			#print(i, j, k)
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
On = a.count(1)
Tw = a.count(2)
Th = n-On-Tw
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(l+1):
		for j in range(l-k+1):
			i = l-k-j
			if k > Th:
				continue
			#print(i, j, k)
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
I = 0
J = 0
K = 0
for a in A:
    if a == 1:
        J += 1
        K += 1
    elif a == 2:
        K += 1

X = [[[0.0] * (j+1) for j in range(k+1)] for k in range(N+1)]

for k in range(N+1)[::-1]:
    for j in range(k+1)[::-1]:
        for i in range(j+1)[::-1]:
            if i == N:
                X[k][j][i] = 0
            else:
                X[k][j][i] = N/(N-i)
                if i < j:
                    X[k][j][i] += X[k][j][i+1] * (j-i) / (N-i)
                if j < k:
                    X[k][j][i] += X[k][j+1][i] * (k-j) / (N-i)
                if k < N:
                    X[k][j][i] += X[k+1][j][i] * (N-k) / (N-i)

print(X[K][J][I])

Submission status: Time Limit Exceeded

Solution code:
def j_sushi(N, A):
    """
    N枚の皿に1からNまでの番号が振られている。最初、皿iにはa_i個の寿司が
    置かれている。(1個以上3個以下)
    すべての寿司がなくなるまで以下の操作を繰り返す。

    等確率で1からNまでの目が出るサイコロを振り、出た目をiとする。
    皿iに寿司があるならその皿の寿司を1個食べ、ないならなにもしない。

    すべての寿司がなくなるまでの操作回数の期待値を求めよ。
    """
    # 参考: https://qiita.com/drken/items/03c7db44ccd27820ea0d

    from collections import Counter
    num_count = Counter(A)
    one, two, three = num_count[1], num_count[2], num_count[3]

    # dp[i][j][k]: 寿司が残り1枚の皿がi枚、2枚の皿がj枚、3枚の皿がk枚ある状態から
    # 寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[-1] * (three + 1) for j in range(two + three + 1)] for i in range(one + two + three + 1)]
    # 次に引く皿 |  引く確率   | 遷移先
    # 残0枚の皿  | (N-i-j-k)/N | dp[i][j][k]
    # 残1枚の皿  |     i/N     | dp[i-1][j][k]
    # 残1枚の皿  |     j/N     | dp[i+1][j-1][k]
    # 残1枚の皿  |     k/N     | dp[i][j+1][k-1]
    # この表より、漸化式は
    # dp[i][j][k] = (上の表から得られる期待値) + 1(←1回サイコロを振るので)
    # この式を変形したのが下の式

    def memorize_recursion(i, j, k):
        if dp[i][j][k] >= 0:
            return dp[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0.0  # もうサイコロを振る必要はない

        ret = 0
        if i > 0:
            ret += memorize_recursion(i - 1, j, k) * i
        if j > 0:
            ret += memorize_recursion(i + 1, j - 1, k) * j
        if k > 0:
            ret += memorize_recursion(i, j + 1, k - 1) * k
        ret += N
        ret *= 1 / (i + j + k)
        dp[i][j][k] = ret
        return ret

    ans = memorize_recursion(one, two, three)
    return round(ans, 12)

N = int(input())
A = [int(i) for i in input().split()]
print(j_sushi(N, A))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0] * (c3 + 1) for _ in range(c2 + c3 + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (c3 + 1) for _ in range(c2 + c3 + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1), -1):
            a3 = k - a1 - a2
            if a3 > c3:
                break
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1), -1):
            a3 = k - a1 - a2
            if a3 > c3:
                continue
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(k - a1, max(-1, 3 * k - 2 * a1 - total - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, -1, -1):
        for a2 in range(min(k - a1, (total - a1) // 2), -1, -1):
            a3 = k - a1 - a2
            if a1 + 2 * a2 + 3 * a3 > total:
                break
            tmp = 0
            if a1:
                tmp += dp[a1 - 1][a2][a3] * a1
            if a2:
                tmp += dp[a1 + 1][a2 - 1][a3] * a2
            if a3:
                tmp += dp[a1][a2 + 1][a3 - 1] * a3
            dp[a1][a2][a3] = tmp / k + still
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())

counts = [0,0,0,0]
for a in map(int,input().split()):
  counts[a] += 1

dp = defaultdict(float)
dp[tuple(counts)] = 1
res = 1
increment = 1

while increment > 10**-10:
  ndp = defaultdict(float)
  for (a,b,c,d),p in dp.items():
    ndp[(a,b,c,d)] += p*a/N
    if b > 0:
      ndp[(a+1,b-1,c,d)] += p*b/N
    if c > 0:
      ndp[(a,b+1,c-1,d)] += p*c/N
    if d > 0:
      ndp[(a,b,c+1,d-1)] += p*d/N
  dp = ndp
  increment = 1-dp[(N,0,0,0)]
  res += increment

print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
dp = [[[0]*(c1+c2+c3+1) for i in range(c2+c3+2)] for j in range(c3+2)]
for c in range(c3+1):
    M1 = c2+c3-c
    T = dp[c-1]
    S = dp[c]
    for b in range(M1+1):
        M2 = N-b-c
        X = S[b-1]; Y = S[b]
        Z = T[b+1]
        for a in range(M2==N, M2+1):
            r = N
            if a:
                r += a*Y[a-1]
            if b:
                r += b*X[a+1]
            if c:
                r += c*Z[a]
            Y[a] = r / (a+b+c)
print("%.10f" % dp[c3][c2][c1])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
dp = [[[0]*301 for i in range(301)] for j in range(301)]
for c in range(c3+1):
    M1 = c2+c3-c
    for b in range(M1+1):
        M2 = N-b-c
        for a in range(M2==N, M2+1):
            r = N
            if a:
                r += a*dp[a-1][b][c]
            if b:
                r += b*dp[a+1][b-1][c]
            if c:
                r += c*dp[a][b+1][c-1]
            dp[a][b][c] = r / (a+b+c)
print("%.10f" % dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
memo = {}
memo[0, 0, 0] = 0.
V = [0]*(c1+c2+c3+1)
for i in range(c1+c2+c3):
    V[i+1] = V[i] + N / (i+1)
def dfs(a, b, c):
    key = (a, b, c)
    if b == c == 0:
        return V[a]
    if key in memo:
        return memo[key]
    r = 0
    if a:
        r += a*(dfs(a-1, b, c)+1)
    if b:
        r += b*(dfs(a+1, b-1, c)+1)
    if c:
        r += c*(dfs(a, b+1, c-1)+1)
    p = (a + b + c)
    memo[key] = r = (r + N - p) / p
    return r
print("%.10f" % dfs(c1, c2, c3))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
memo = {}
memo[0, 0, 0] = 0.
def dfs(a, b, c):
    key = (a, b, c)
    if key in memo:
        return memo[key]
    r = 0
    if a:
        r += a*(dfs(a-1, b, c)+1)
    if b:
        r += b*(dfs(a+1, b-1, c)+1)
    if c:
        r += c*(dfs(a, b+1, c-1)+1)
    p = (a + b + c)
    memo[key] = r = (r + N - p) / p
    return r
print("%.10f" % dfs(c1, c2, c3))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))

dp_state = [0,0,0]
for a in A:
    dp_state[a-1] += 1
dp_state = tuple(dp_state)
dp = [[[-1 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
def solve(sushi_count):
    if dp[sushi_count[0]][sushi_count[1]][sushi_count[2]] != -1:
        return dp[sushi_count[0]][sushi_count[1]][sushi_count[2]]
    trays = sum(sushi_count)
    ans = n/trays #expected number of trays we need to pick before we get one with a sushi on it
    if sushi_count[0] > 0:
        ans += sushi_count[0]/trays*solve((sushi_count[0]-1, sushi_count[1], sushi_count[2]))
    if sushi_count[1] > 0:
        ans += sushi_count[1]/trays*solve((sushi_count[0]+1, sushi_count[1]-1, sushi_count[2]))
    if sushi_count[2] > 0:
        ans += sushi_count[2]/trays*solve((sushi_count[0], sushi_count[1]+1, sushi_count[2]-1))

    dp[sushi_count[0]][sushi_count[1]][sushi_count[2]] = ans
    return ans

print(solve(dp_state))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
A = list(map(int, input().split()))

dp_state = [0,0,0]
for a in A:
    dp_state[a-1] += 1
dp_state = tuple(dp_state)
dp = {}
def solve(sushi_count):
    if sushi_count in dp:
        return dp[sushi_count]
    if sushi_count == (0,0,0):
        return 0
    trays = sum(sushi_count)
    dp[sushi_count] = n/trays #expected number of trays we need to pick before we get one with a sushi on it
    if sushi_count[0] > 0:
        dp[sushi_count] += sushi_count[0]/trays*solve((sushi_count[0]-1, sushi_count[1], sushi_count[2]))
    if sushi_count[1] > 0:
        dp[sushi_count] += sushi_count[1]/trays*solve((sushi_count[0]+1, sushi_count[1]-1, sushi_count[2]))
    if sushi_count[2] > 0:
        dp[sushi_count] += sushi_count[2]/trays*solve((sushi_count[0], sushi_count[1]+1, sushi_count[2]-1))
    return dp[sushi_count]



print(solve(dp_state))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a = list(map(int,input().split()))
cnt = [0,0,0] #1個の個数、二個の個数、三個の個数
for i in range(n):
    cnt[a[i]-1] += 1
    
def f(i,j,k):
    if [i,j,k] == [0,0,0]:
        return 0.0
    if dp[i][j][k] != 0.0:
        return dp[i][j][k]
    tmp = 0.0
    if i>0:
        tmp += f(i-1,j,k)*float(i)/float(i+j+k)
    if j>0:
        tmp += f(i+1,j-1,k)*float(j)/float(i+j+k)
    if k>0:
        tmp += f(i,j+1,k-1)*float(k)/float(i+j+k)
    tmp += float(n)/float(i+j+k)
    

    dp[i][j][k] = tmp
    return tmp
dp = np.zeros((n+1,n+1,n+1))
#dp = [[[0.0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]

print(f(cnt[0],cnt[1],cnt[2]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int,input().split()))
cnt = [0,0,0] #1個の個数、二個の個数、三個の個数
for i in range(n):
    cnt[a[i]-1] += 1
    
def f(i,j,k):
    if [i,j,k] == [0,0,0]:
        return 0.0
    if dp[i][j][k] != 0.0:
        return dp[i][j][k]
    tmp = 0.0
    if i>0:
        tmp += f(i-1,j,k)*float(i)/float(i+j+k)
    if j>0:
        tmp += f(i+1,j-1,k)*float(j)/float(i+j+k)
    if k>0:
        tmp += f(i,j+1,k-1)*float(k)/float(i+j+k)
    tmp += float(n)/float(i+j+k)
    

    dp[i][j][k] = tmp
    return tmp

dp = [[[0.0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
dp[0][0][0] = 0.0

print(f(cnt[0],cnt[1],cnt[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

N = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().split()))
I = J = K = 0
for a in A:
    if a == 1: I += 1
    elif a == 2: J += 1
    else: K += 1

dp = [[[None]*(K+1) for j in range(J+K+1)] for i in range(N+1)]
dp[0][0][0] = 0
def rec(i,j,k):
    if dp[i][j][k] is not None: return dp[i][j][k]
    ret = N / (i+j+k)
    if i:
        ret += rec(i-1,j,k) * i / (i+j+k)
    if j:
        ret += rec(i+1,j-1,k) * j / (i+j+k)
    if k:
        ret += rec(i,j+1,k-1) * k / (i+j+k)
    dp[i][j][k] = ret
    return ret

print(rec(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
A = list(map(int,input().split()))
I = J = K = 0
for a in A:
    if a == 1: I += 1
    elif a == 2: J += 1
    else: K += 1

dp = [[[None]*(K+1) for j in range(J+K+1)] for i in range(N+1)]
dp[0][0][0] = 0
def rec(i,j,k):
    if dp[i][j][k] is not None: return dp[i][j][k]
    ret = N / (i+j+k)
    if i:
        ret += rec(i-1,j,k) * i / (i+j+k)
    if j:
        ret += rec(i+1,j-1,k) * j / (i+j+k)
    if k:
        ret += rec(i,j+1,k-1) * k / (i+j+k)
    dp[i][j][k] = ret
    return ret

print(rec(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DP=dict()
DP[SC]=[1,0]#遷移確率0,経過日数

def plus(A,B):
    xa,ya=A
    xb,yb=B

    return [xa+xb,(xa*ya+xb*yb)/(xa+xb)]
#print(DP)

for test in range(sum(A)):
    
    NEXT=dict()
    
    for a,b,c,d in DP:
        x,y=DP[(a,b,c,d)]
        

        #print(a,b,c,d,x,y)
        #print(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if b>0:
            NEXT[(a+1,b-1,c,d)]=plus(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if c>0:
            NEXT[(a,b+1,c-1,d)]=plus(NEXT.get((a,b+1,c-1,d),[0,0]),[x*c/(b+c+d),y+N/(b+c+d)])

        if d>0:
            NEXT[(a,b,c+1,d-1)]=plus(NEXT.get((a,b,c+1,d-1),[0,0]),[x*d/(b+c+d),y+N/(b+c+d)])

        #print(NEXT)

    DP=NEXT

print(list(DP.values())[0][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

N=int(input())
A=list(map(int,input().split()))

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DP=dict()
DP[SC]=[1,0]#遷移確率0,経過日数

def plus(A,B):
    xa,ya=A
    xb,yb=B

    x=xa+xb
    y=(xa*ya+xb*yb)/(xa+xb)
    return [x,y]
#print(DP)
while True:
    NEXT=dict()
    
    for a,b,c,d in DP:
        x,y=DP[(a,b,c,d)]
        

        #print(a,b,c,d,x,y)
        #print(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if b>0:
            NEXT[(a+1,b-1,c,d)]=plus(NEXT.get((a+1,b-1,c,d),[0,0]),[x*b/(b+c+d),y+N/(b+c+d)])

        if c>0:
            NEXT[(a,b+1,c-1,d)]=plus(NEXT.get((a,b+1,c-1,d),[0,0]),[x*c/(b+c+d),y+N/(b+c+d)])

        if d>0:
            NEXT[(a,b,c+1,d-1)]=plus(NEXT.get((a,b,c+1,d-1),[0,0]),[x*d/(b+c+d),y+N/(b+c+d)])

        #print(NEXT)

    DP=copy.deepcopy(NEXT)

    #print(DP)

    if len(DP)==1:
        a,b,c,d=list(DP.keys())[0]
        if b==c==d==0:
            print(DP[(a,b,c,d)][1])
            sys.exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
*A, = map(int, input().split())
C = [0]*4
for a in A:
    C[a] += 1

c1, c2, c3 = C[1:]
memo = [[[-1]*(301) for i in range(301)] for j in range(301)]
memo[0][0][0] = 0.
def dfs(a, b, c):
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    r = 0
    if a:
        r += a*(dfs(a-1, b, c)+1)
    if b:
        r += b*(dfs(a+1, b-1, c)+1)
    if c:
        r += c*(dfs(a, b+1, c-1)+1)
    p = (a + b + c)
    memo[a][b][c] = r = (r + N - p) / p
    return r

print("%.10f" % dfs(c1, c2, c3))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**8)

def main():
    n = int(input())
    a = list(map(int, input().split()))

    dp = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0.0

    def search(i, j, k):
        num = n
        if i > 0:
            if dp[i-1][j][k] == -1:
                num += search(i-1, j, k) * i
            else:
                num += dp[i-1][j][k] * i
        if j > 0:
            if dp[i+1][j-1][k] == -1:
                num += search(i+1, j-1, k) * j
            else:
                num += dp[i+1][j-1][k] * j
        if k > 0:
            if dp[i][j+1][k-1] == -1:
                num += search(i, j+1, k-1) * k
            else:
                num += dp[i][j+1][k-1] * k
        num /= i + j + k

        dp[i][j][k] = num
        return num

    print(search(a.count(1), a.count(2), a.count(3)))

main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys


def main():
    sys.setrecursionlimit(10**6)
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))
    C = Counter(A)

    l, m, n = C[3], C[2], C[1]
    dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    dp[0][0][0] = 0

    def exval(i, j, k):
        if dp[i][j][k]!=-1:
            return dp[i][j][k]
        s = N
        if i > 0:
            s += i*exval(i-1, j+1, k)
        if j > 0:
            s += j*exval(i, j-1, k+1)
        if k > 0:
            s += k*exval(i, j, k-1)
        dp[i][j][k] = s / (i+j+k)
        return dp[i][j][k]


    print(exval(l, m, n))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def f(c1, c2, c3):
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(10 ** 9)
#import math
#import numpy as np
N = int(input())
A = list(map(int, input().split()))

one = A.count(1)
two = A.count(2)
three = A.count(3)

dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]

def calc(a, b, c):
    if dp[a][b][c] >= 0:
        return dp[a][b][c]

    if a + b + c == 0:
        return 0

    t = N

    if a > 0:
        t += calc(a - 1, b + 1, c) * a
    if b > 0:
        t += calc(a, b - 1, c + 1) * b
    if c > 0:
        t += calc(a, b, c - 1) * c
        
    t /= a + b + c

    dp[a][b][c] = t
    return t

ans = calc(three, two, one)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = Counter(A)
DP = [[[0.0] * (B[3] + 1) for _ in range(N + 1)] for __ in range(N + 2)]

for k in range(B[3]+1):
    for j in range(B[2] + B[3] + 1 - k):
        for i in range(B[1] + B[2] + B[3] + 1 - k - j):
            if i == j == k == 0:
                continue
            tmp = float(N)
            if i > 0:
                tmp += i * DP[i - 1][j][k]
            if j > 0:
                tmp += j * DP[i + 1][j - 1][k]
            if k > 0:
                tmp += k * DP[i][j + 1][k - 1]
            DP[i][j][k] = tmp / (i + j + k)
print(DP[B[1]][B[2]][B[3]])

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(float, input().split()))
dp=[[[0.0] *(N+2) for _ in range(N+2)] for _ in range(N+2)]
one,two,three=a.count(1),a.count(2),a.count(3)
for k in range(three+1):
    for j in range(two+three+1):
        for i in range(N+1):
            if k==0 and j==0 and i==0:
                continue
            num=N
            if i>0:
                num+=dp[i-1][j][k]*i
            if j>0:
                num+=dp[i+1][j-1][k]*j
            if k>0:
                num+=dp[i][j+1][k-1]*k
            dp[i][j][k]=num/(k+j+i)
print(dp[one][two][three])

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(float, input().split()))
dp=[[[0.0] *(N+2) for _ in range(N+2)] for _ in range(N+2)]
one,two,three=a.count(1),a.count(2),a.count(3)
for k in range(three+1):
    for j in range(two+three+1-k):
        for i in range(N+1):
            if k==0 and j==0 and i==0:
                continue
            num=N
            if i>0:
                num+=dp[i-1][j][k]*i
            if j>0:
                num+=dp[i+1][j-1][k]*j
            if k>0:
                num+=dp[i][j+1][k-1]*k
            dp[i][j][k]=num/(k+j+i)
print(dp[one][two][three])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    alst = list(map(float, input().split()))
    dp = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    one = alst.count(1)
    two = alst.count(2)
    three = alst.count(3)
    for k in range(three + 1):
        for j in range(two + three + 1):
            if k + j > n:
                continue
            for i in range(n + 1):
                if k + j + i > n:
                    continue
                ijk = i + j + k
                if ijk == 0:
                    continue
                tmp = n
                if i != 0:
                    tmp += dp[i - 1][j][k] * i
                if j != 0 and i != n:
                    tmp += dp[i + 1][j - 1][k] * j
                if k != 0 and j != n:
                    tmp += dp[i][j + 1][k - 1] * k
                dp[i][j][k] = tmp / ijk
    
    print(dp[one][two][three])


main()

Submission status: Accepted

Solution code:
n=int(input())
lst_a=list(map(int,input().split()))
one,two,three=lst_a.count(1),lst_a.count(2),lst_a.count(3)
# dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から、
# 寿司をすべてなくすのに必要な操作回数の期待値
dp=[[[0.0] *(n+1) for _ in range(n+1)] for _ in range(n+1)]
#print(dp)
for k in range(three+1):
  for j in range(two+three+1-k):
    for i in range(one+two+three+1-k-j):
      if i==0 and j==0 and k==0:
        continue
      tmp=n*1.0
      if i>0:
        tmp+=i*dp[i-1][j][k]
      if j>0:
        tmp+=j*dp[i+1][j-1][k]
      if k>0:
        tmp+=k*dp[i][j+1][k-1]
      dp[i][j][k]=tmp/(i+j+k)
#print(dp)
print(dp[one][two][three])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
dp = [[[0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)] 
for i in a:
    d[i-1] +=1
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i+j+k==0 or i+j+k>n:
                continue
            ans = n/(i+j+k)
            x = i/(i+j+k)
            if x:
                ans += x*dp[k][j][i-1]
            x = j/(i+j+k)
            if x:
                ans += x*dp[k][j-1][i+1]
            x = k/(i+j+k)
            if x:
                ans += x*dp[k-1][j+1][i]
            dp[k][j][i] = ans
print(dp[d[2]][d[1]][d[0]])