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:
# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

N = int(input())
A = list(map(int, input().split()))
cnt1 = A.count(1)
cnt2 = A.count(2)
cnt3 = A.count(3)

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

# dp[c1][c2][c3]=1
# 	+dp[c1−1][c2][c3]∗(1個の皿が選ばれる確率)
# 	+dp[c1+1][c2−1][c3]∗(2個の皿が選ばれる確率)
# 	+dp[c1][c2+1][c3−1]∗(3個の皿が選ばれる確率)
# 	+dp[c1][c2][c3]∗(0個の皿が選ばれる確率)
# ↓式変形↓
# dp[c1][c2][c3]=1/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1−1][c2][c3]*(1個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1+1][c2−1][c3]*(2個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))
# 			+ dp[c1][c2+1][c3−1]*(3個の皿が選ばれる確率)/(1−(0個の皿が選ばれる確率))


def func(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    temp = 1 / (1 - ((N - c1 - c2 - c3) / N))
    if c1 > 0:
        temp += func(c1 - 1, c2, c3) * (c1 / N) / (1 - (N - c1 - c2 - c3) / N)
    if c2 > 0:
        temp += func(c1 + 1, c2 - 1, c3) * (c2 / N) / \
            (1 - (N - c1 - c2 - c3) / N)
    if c3 > 0:
        temp += func(c1, c2 + 1, c3 - 1) * (c3 / N) / \
            (1 - (N - c1 - c2 - c3) / N)

    dp[c1][c2][c3] = temp
    return temp


print(func(cnt1, cnt2, cnt3))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
#from numba import njit


#@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1
    sh = (N+1, N-sushi_count[1]+1, sushi_count[3]+1)
    expv = np.full(sh, -1.0)

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit


@njit('f8(i8,i8,i8,i8,f8[:,:,:])')
def get_expv(N, i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(N, i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(N, i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(N, i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

def main():
    N = int(input())

    sushi_count = {1:0, 2:0, 3:0}
    for a in map(int, input().split()):
        sushi_count[a] += 1

    expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

    expv[0][0][0] = 0.0

    print(get_expv(N, sushi_count[1], sushi_count[2], sushi_count[3], expv))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

expv[0][0][0] = 0.0

@njit('f8(i8,i8,i8,f8[:,:,:])')
def get_expv(i, j, k, expv):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k, expv) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k, expv) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1, expv) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3], expv))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import njit

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = np.array([[[-1.0] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)])

expv[0][0][0] = 0.0

def get_expv(i, j, k):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3]))

Submission status: Time Limit Exceeded

Solution code:
'''
expv[i][j][k] = 1 +
                expv[i-1][j][k] * (i / N) +
                expv[i+1][j-1][k] * (j / N) +
                expv[i][j+1][k-1] * (k / N) + 
                expv[i][j][k] * ((N - i - j - k) / N)

nonlp = 1 - (N-i-j-k) / N 
expv[i][j][k] =  (1 + ~~) / nonlp

'''

N = int(input())

sushi_count = {1:0, 2:0, 3:0}
for a in map(int, input().split()):
    sushi_count[a] += 1

expv = [[[-1] * (sushi_count[3]+1) for i in range(N-sushi_count[1]+1)] for i in range(N+1)]

expv[0][0][0] = 0.0

def get_expv(i, j, k):
    result = 0.0
    if expv[i][j][k] != -1:
        return expv[i][j][k]
    nonlp = 1.0 - (N-i-j-k) / N
    result += 1
    if i != 0:
        result += get_expv(i-1, j, k) * (i / N)
    if j != 0:
        result += get_expv(i+1, j-1, k) * (j / N)
    if k != 0:
        result += get_expv(i, j+1, k-1) * (k / N)
    result /= nonlp
    expv[i][j][k] = result
    return result

print(get_expv(sushi_count[1], sushi_count[2], sushi_count[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
dp[0][0][0] = 0
C = [0 for i in range(4)]
for x in A:
    C[x] += 1


def recur(X, Y, Z):
    if X<0 or Y<0 or Z<0: 
      return 0
    if dp[X][Y][Z] < 0:
        dp[X][Y][Z] = N/(X+Y+Z) + recur(X-1, Y, Z)*X / (X+Y+Z) + recur(X+1, Y-1, Z)*Y/(X+Y+Z) + recur(X, Y+1, Z-1)*Z/(X+Y+Z)
        return dp[X][Y][Z]
    else:
        return dp[X][Y][Z]


X, Y, Z = C[1], C[2], C[3]

ans = recur(X,Y,Z)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3*10**7)
N = int(input())
A = list(map(int, input().split()))
dp = [[[-1]*(N+10) for i in range(N+10)] for j in range(N+10)]
dp[0][0][0] = 0
C = [0 for i in range(4)]
for x in A:
    C[x] += 1


def recur(X, Y, Z):
    if X<0 or Y<0 or Z<0: 
      return 0
    if dp[X][Y][Z] < 0:
        dp[X][Y][Z] = N/(X+Y+Z) + recur(X-1, Y, Z)*X / (X+Y+Z) + recur(X+1, Y-1, Z)*Y/(X+Y+Z) + recur(X, Y+1, Z-1)*Z/(X+Y+Z)
        return dp[X][Y][Z]
    elif dp[X][Y][Z] >= 0:
        return dp[X][Y][Z]


X, Y, Z = C[1], C[2], C[3]

ans = recur(X,Y,Z)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
print(dfs(c[1],c[2],c[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
print(dfs(c[1],c[2],c[3]))
'''print(dp[0])
print(dp[1])
print(dp[2])
print(dp[3])'''
#print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            dfs(i,j,k)
'''print(dp[0])
print(dp[1])
print(dp[2])
print(dp[3])'''
print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

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


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


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


a1, a2, a3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        a1 += 1
    elif A[i] == 2:
        a2 += 1
    elif A[i] == 3:
        a3 += 1

print(solve(a1, a2, a3))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))

Submission status: Time Limit Exceeded

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

n1, n2, n3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        n1 += 1
    elif A[i] == 2:
        n2 += 1
    elif A[i] == 3:
        n3 += 1

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


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


print(solve(n1, n2, n3))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nl = lambda: list(map(int, readline().split()))

N = in_n()
A = in_nl()

n1, n2, n3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        n1 += 1
    elif A[i] == 2:
        n2 += 1
    elif A[i] == 3:
        n3 += 1

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


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


print(solve(n1, n2, n3))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


N = in_n()
A = in_nl()

n1, n2, n3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        n1 += 1
    elif A[i] == 2:
        n2 += 1
    elif A[i] == 3:
        n3 += 1

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


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


print(solve(n1, n2, n3))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1, n2, n3 = 0, 0, 0
    for i in range(N):
        if A[i] == 1:
            n1 += 1
        elif A[i] == 2:
            n2 += 1
        elif A[i] == 3:
            n3 += 1

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] >= 0.0:
            return dp[n1][n2][n3]
        if n1 == n2 == n3 == 0:
            return 0.0

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] >= 0.0:
            return dp[n1][n2][n3]
        if n1 == n2 == n3 == 0:
            return 0.0

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] >= 0:
            return dp[n1][n2][n3]

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] != -1:
            return dp[n1][n2][n3]

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1

        ret = (ret + N) / cnt
        dp[n1][n2][n3] = ret
        return ret

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N = in_n()
    A = in_nl()

    n1 = A.count(1)
    n2 = A.count(2)
    n3 = A.count(3)

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

    def solve(n1, n2, n3):

        if dp[n1][n2][n3] != -1:
            return dp[n1][n2][n3]

        cnt = n1 + n2 + n3
        ret = 0
        if n3 >= 1:
            ret += solve(n1, n2 + 1, n3 - 1) * n3 / cnt
        if n2 >= 1:
            ret += solve(n1 + 1, n2 - 1, n3) * n2 / cnt
        if n1 >= 1:
            ret += solve(n1 - 1, n2, n3) * n1 / cnt

        dp[n1][n2][n3] = ret + (N / cnt)
        return ret + (N / cnt)

    print(solve(n1, n2, n3))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
memo  = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
memo[0][0][0] = 0
def f(i, j, k):
    if memo[i][j][k] != -1:
        return memo[i][j][k]
    s = i + j + k
    ret = n - s
    if i:
        ret += i * (f(i - 1, j, k) + 1)
    if j:
        ret += j * (f(i + 1, j - 1, k) + 1)
    if k:
        ret += k * (f(i, j + 1, k - 1) + 1)
    memo[i][j][k] = ret / s
    return memo[i][j][k]

one, two, three = 0, 0, 0
for i in range(n):
    if A[i] == 1:
        one += 1
    elif A[i] == 2:
        two += 1
    else:
        three += 1

print(f(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
memo  = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
memo[0][0][0] = 0
def f(i, j, k):
    if memo[i][j][k] != -1:
        return memo[i][j][k]
    s = i + j + k
    ret = n - s
    if i:
        ret += i * (f(i - 1, j, k) + 1)
    if j:
        ret += j * (f(i + 1, j - 1, k) + 1)
    if k:
        ret += k * (f(i, j + 1, k - 1) + 1)
    memo[i][j][k] = ret / s
    return memo[i][j][k]



one, two, three = 0, 0, 0
for i in range(n):
    if A[i] == 1:
        one += 1
    elif A[i] == 2:
        two += 1
    else:
        three += 1

print(f(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
memo  = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
memo[0][0][0] = 0
def f(i, j, k):
    if memo[i][j][k] != -1:
        return memo[i][j][k]
    s = i + j + k
    ret = (n - s) / s
    if i:
        ret += i / s * (f(i - 1, j, k) + 1)
    if j:
        ret += j / s * (f(i + 1, j - 1, k) + 1)
    if k:
        ret += k / s * (f(i, j + 1, k - 1) + 1)
    memo[i][j][k] = ret
    return memo[i][j][k]



one, two, three = 0, 0, 0
for i in range(n):
    if A[i] == 1:
        one += 1
    elif A[i] == 2:
        two += 1
    else:
        three += 1

print(f(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def FI(): return list(map(float, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
memo  = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
memo[0][0][0] = 0
def f(i, j, k):
    if memo[i][j][k] != -1:
        return memo[i][j][k]
    s = i + j + k
    ret = (n - s) / n
    if i:
        ret += i / n * (f(i - 1, j, k) + 1)
    if j:
        ret += j / n * (f(i + 1, j - 1, k) + 1)
    if k:
        ret += k / n * (f(i, j + 1, k - 1) + 1)
    memo[i][j][k] = n / s * ret
    return memo[i][j][k]



one, two, three = 0, 0, 0
for i in range(n):
    if A[i] == 1:
        one += 1
    elif A[i] == 2:
        two += 1
    else:
        three += 1

print(f(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(100000000)
n = int(input())
a = [int(i) for i in input().split(' ')]
z,o,tw,th = 0,0,0,0
for i in a:
    if i==0:
        z+=1
    elif i==1:
        o+=1
    elif i==2:
        tw+=1
    else:
        th+=1

def expectedValue(z,o,tw, th):
    if o+tw+th==0:
        return 0
    return (z+o+tw+th)/(o+th+tw)

def solve(z,o,tw,th):
    dp = [[[0]*(th+1) for i in range(th+tw+1)] for i in range(n+1)]
    dp[0][0][0] = 0 
    for th_1 in range(th+1):
        for tw_1 in range(th+tw+1):
            for o_1 in range(n+1):
                dp[o_1][tw_1][th_1] = expectedValue(n-o_1-tw_1-th_1, o_1,tw_1,th_1) 
                tot = (o_1+tw_1+th_1)
                if o_1>0:
                    dp[o_1][tw_1][th_1] += ((o_1)/tot)*dp[o_1-1][tw_1][th_1] 
                if tw_1>0 and o_1<n:
                    dp[o_1][tw_1][th_1] += ((tw_1)/tot)*dp[o_1+1][tw_1-1][th_1] 
                if th_1>0 and tw_1<th+tw:
                    dp[o_1][tw_1][th_1] += ((th_1)/tot)*dp[o_1][tw_1+1][th_1-1] 
    return dp[o][tw][th]                

print(solve(z,o,tw,th))