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:
def main():
    n = int(input())
    l1 = l2 = l3 = 0
    l = [int(i) for i in input().split()]
    for i in l:
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1
    a = l2+l3
    dp = [[[0]*(l3+1) for i in range(a+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,a)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n/(s+t+k)
                if s > 0:
                    count += dp[s-1][t][k]*(s/(s+t+k))     
                if t > 0 :
                    count += dp[s+1][t-1][k]*(t/(s+t+k))
                if k > 0 :
                    count += dp[s][t+1][k-1]*(k/(s+t+k))

                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    l1 = l2 = l3 = 0
    l = [int(i) for i in input().split()]
    for i in l:
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1
    a = l2+l3
    dp = [[[0]*(l3+1) for i in range(a+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,a)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n/(s+t+k)
                if s > 0:
                    count += dp[s-1][t][k]*(s/(s+t+k))     
                if t > 0 :
                    count += dp[s+1][t-1][k]*(t/(s+t+k))
                if k > 0 :
                    count += dp[s][t+1][k-1]*(k/(s+t+k))

                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    l1 = l2 = l3 = 0
    l = [int(i) for i in input().split()]
    for i in l:
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

    dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,l2+l3)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n
                if s > 0:
                    count += dp[s-1][t][k]*s     
                if t > 0 :
                    count += dp[s+1][t-1][k]*t
                if k > 0 :
                    count += dp[s][t+1][k-1]*k

                count /= (s+t+k)
                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    
    l1 = l2 = l3 = 0
    for i in map(int,input().split()):
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

    dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,l2+l3)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n
                if s > 0:
                    count += dp[s-1][t][k]*s
                    
                if t > 0 :
                    count += dp[s+1][t-1][k]*t
                if k > 0 :
                    count += dp[s][t+1][k-1]*k

                count *= 1/(s+t+k)
                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    l = list(map(int,input().split()))
    l1 = l.count(1)
    l2 = l.count(2)
    l3 = l.count(3)

    dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

    for i in range(1,n+1):
        for j in range(min(i,l2+l3)+1):
            for k in range(min(j,l3)+1):
                s = i-j
                t = j-k
                count = n
                if s > 0:
                    count += dp[s-1][t][k]*s
                    
                if t > 0 :
                    count += dp[s+1][t-1][k]*t
                if k > 0 :
                    count += dp[s][t+1][k-1]*k

                count *= 1/(s+t+k)
                dp[s][t][k] = count

    print(dp[l1][l2][l3])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = list(map(int,input().split()))
l1 = l.count(1)
l2 = l.count(2)
l3 = l.count(3)

dp = [[[0]*(l3+1) for i in range(l2+l3+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(min(i,l2+l3)+1):
        for k in range(min(j,l3)+1):
            s = i-j
            t = j-k
            count = n
            if s > 0:
                count += dp[s-1][t][k]*s
                
            if t > 0 :
                count += dp[s+1][t-1][k]*t
            if k > 0 :
                count += dp[s][t+1][k-1]*k

            count *= 1/(s+t+k)
            dp[s][t][k] = count

print(dp[l1][l2][l3])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            for i in range(N+1):
                if i+j+k > N:
                    continue
                if i > 0:
                    dp[i][j][k] += (dp[i-1][j][k] + (N / (i+j+k))) * (i / (i+j+k))
                if j > 0 and i < N:
                    dp[i][j][k] += (dp[i+1][j-1][k] + (N / (i+j+k))) * (j / (i+j+k))
                if k > 0 and j < N:
                    dp[i][j][k] += (dp[i][j+1][k-1] + (N / (i+j+k))) * (k / (i+j+k))
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            for i in range(N+1):
                if i > 0:
                    dp[i][j][k] += (dp[i-1][j][k] + (N / (i+j+k))) * (i / (i+j+k))
                if j > 0 and i < N:
                    dp[i][j][k] += (dp[i+1][j-1][k] + (N / (i+j+k))) * (j / (i+j+k))
                if k > 0 and j < N:
                    dp[i][j][k] += (dp[i][j+1][k-1] + (N / (i+j+k))) * (k / (i+j+k))
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

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.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]  # ←ここを0で初期化するとTLE
 
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:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

dp[n][n][n] = 0
divT = [1/i for i in range(1,n+1)]

for x in range(n,cnt[1]+cnt[2]-1,-1):## -2だったのを-1に
    for y in range(x,cnt[2]-1,-1):##cnt[2]
        for z in range(y,-1,-1):
            delta = n*divT[n-z-1]#2枚以下を引くまで
            if x != n:
                dp[x][y][z] += (dp[x+1][y][z] + delta) * (n-x)
            if y != x:
                dp[x][y][z] += (dp[x][y+1][z] + delta) * (x-y)#x+1,y+1ではない
            if z != y:
                dp[x][y][z] += (dp[x][y][z+1] + delta)* (y-z)#x+1,y+1,z+1ではない
            dp[x][y][z] *=divT[n-z-1]

print(dp[cnt[1]+cnt[2]][cnt[2]][0])

Submission status: Time Limit Exceeded

Solution code:
# how does this actually work?

n = int(input())
cnt = [0] * 4

dp = [[[-1 for k in range(310)] for i in range(310)] for j in range(310)]

def dfs(a, b, c):
    if a + b + c == 0:
        return 0.0
    if dp[a][b][c] > -0.5:
        return dp[a][b][c]
    ks = float(n / (a + b + c))
    ra = 0

    if (a):
        ra += (dfs(a - 1, b, c) + ks) * (a / (a + b + c))
    if (b):
        ra += (dfs(a + 1, b - 1, c) + ks) * (b / (a + b + c))
    if (c):
        ra += (dfs(a, b + 1, c - 1) + ks) * (c / (a + b + c))

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

temp = list(map(int,input().split()))

for i in range(n):
    cnt[temp[i]] += 1

ret = dfs(cnt[1], cnt[2], cnt[3])
print(ret)

Submission status: Time Limit Exceeded

Solution code:
#事象が確率pで起きるとき, 事象が起きるまでの回数の期待値は1/p
#https://qiita.com/drken/items/03c7db44ccd27820ea0d

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = tuple(map(int, input().split()))
    c1 = a.count(1) #i
    c2 = a.count(2) #j
    c3 = a.count(3) #k

    dp = [[[0]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
    for i in range(c3+1):
        for j in range(c2+c3-i+1):
            for k in range(N-i-j+1):
                if i == j == k == 0:
                    continue
                tmp = N
                if k != 0:
                    tmp += k*dp[k-1][j][i]
                if j != 0:
                    tmp += j*dp[k+1][j-1][i]
                if i != 0:
                    tmp += i*dp[k][j+1][i-1]
                dp[k][j][i] = tmp/(i+j+k)

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# dp[i][j][k]: 寿司が残り1個の皿がi枚, 残り2個の皿がj枚, 残り3個の皿がk枚から寿司をすべてなくす操作回数の期待値
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]

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

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + (two + (three - k) - j) + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 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[i][j][k])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=0
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+2):
  for j in range(1,n-k-i+4):
    for i in range(1,n-k-j+4):
      if i+j+k!=3:
        dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=0
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+2):
  for j in range(1,n-k-i+4):
    for i in range(1,n-k-j+4):
      if i==1 and j==1 and k==1:
        continue
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+3):
  for j in range(1,n+2):
    for i in range(1,n+2):
      if i==1 and j==1 and k==1:
        continue
      if i+2*j+3*k>d+10:
        break
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,n+2):
  for j in range(1,n+2):
    for i in range(1,n+2):
      if i==1 and j==1 and k==1:
        continue
      dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = np.array(list(map(int, input().split())))

n1 = len(a[a==1])
n2 = len(a[a==2])
n3 = len(a[a==3])

dp = np.zeros((n + 1, n + 1, n + 1))


def solve(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

    total = float(n)
    if i > 0:
        total += solve(i-1, j, k) * i
    if j > 0:
        total += solve(i+1, j-1, k) * j
    if k > 0:
        total += solve(i, j+1, k-1) * k
    total /= (i + j + k)

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


print(solve(n1, n2, n3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    dp = [[[0.0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    def rec(i,j,k):
        #global res
        if dp[i][j][k] > 0.0:
            return dp[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0.0
        res = 0.0
    
        if i > 0.0: res += rec(i-1,j,k)*i
        if j > 0.0: res += rec(i+1,j-1,k)*j
        if k > 0.0: res += rec(i,j+1,k-1)*k
        res += N
        res *= 1.0/(i+j+k)
        dp[i][j][k] = res
        return res
    
    one = a.count(1)
    two = a.count(2)
    three = a.count(3)
    
    #print(dp)
    print(rec(one,two,three))
    #print(dp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[0.0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] > 0.0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

    if i > 0.0: res += rec(i-1,j,k)*i
    if j > 0.0: res += rec(i+1,j-1,k)*j
    if k > 0.0: res += rec(i,j+1,k-1)*k
    res += N
    res *= 1.0/(i+j+k)
    dp[i][j][k] = res
    return res

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

#print(dp)
print(rec(one,two,three))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

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

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

#print(dp)
print(rec(one,two,three))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

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

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

#print(dp)
print(rec(one,two,three))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

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

one = 0
two = 0
three = 0
for aa in a:
    if aa == 1:one+=1
    if aa == 2:two+=1
    if aa == 3:three+=1

#print(dp)
print(rec(one,two,three))
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c1,c2,c3 = c[1],c[2],c[3]
dp = [[[0 for i in range(c3+1)] for j in range(c2+c3+1)] for k in range(c1+c2+c3+1)]
#dp[i][j][k] := 1個×i皿、2個×j皿、3個×k皿における期待値
for k in range(c3+1):
  for j in range(c2+c3+1):
    for i in range(n+1):
      if i+j+k > n or i == j == k == 0:
        continue
      x = (n-i-j-k)/n
      dp[i][j][k] = 1
      if 0<i :
        dp[i][j][k] += dp[i-1][j][k]*(i/n)
      if 0<j and i+1<=n:
        dp[i][j][k] += dp[i+1][j-1][k]*(j/n)
      if 0<k and j+1<=c2+c3:
        dp[i][j][k] += dp[i][j+1][k-1]*(k/n)
      dp[i][j][k] /= 1-x
print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(input())
a = list(map(int, input().split()))
memo = {(0, 0, 0): 0}

def dfs(x, y, z):
    if (x, y, z) in memo:
        return memo[(x, y, z)]
    w = x + y + z
    res = (N-w) / w
    if x > 0:
        res += (1 + dfs(x-1, y, z)) * x / w
    if y > 0:
        res += (1 + dfs(x+1, y-1, z)) * y / w
    if z > 0:
        res += (1 + dfs(x, y+1, z-1)) * z / w
    memo[(x, y, z)] = res
    return res
print(dfs(a.count(1), a.count(2), a.count(3)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
INF = -1
dp = [[[INF]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 0

def dfs(C1, C2, C3):
#i個の皿がCi皿ある時の期待値
  if dp[C1][C2][C3]==INF:
    ret = N
    if C1>=1:#1個の皿
      ret += dfs(C1-1, C2, C3)*C1
    if C2>=1:#2個の皿
      ret += dfs(C1+1, C2-1, C3)*C2
    if C3>=1:#3個の皿
      ret += dfs(C1, C2+1, C3-1)*C3
    ret = ret / (C1+C2+C3)
    dp[C1][C2][C3] = ret
  return dp[C1][C2][C3]
print(dfs(P.count(1), P.count(2), P.count(3)))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
a = counter[1]
b = counter[2]
c = counter[3]
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[-1] * (310) for _ in range(310)] for _ in range(310)]

def rec(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
    res = 0
    if i > 0:
        res += rec(i-1,j,k) * i
    if j > 0:
        res += rec(i+1,j-1,k) * j
    if k > 0:
        res += rec(i,j+1,k-1) * k
    res += N
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res

for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            rec(i, j, k)
print(dp[a][b][c])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = list(map(int, input().split()))
INF = -1
dp = [[[INF]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
dp[0][0][0] = 0

def dfs(C1, C2, C3):
#i個の皿がCi皿ある時の期待値
  if dp[C1][C2][C3]==INF:
    ret = N
    if C1>=1:#1個の皿
      ret += dfs(C1-1, C2, C3)*C1
    if C2>=1:#2個の皿
      ret += dfs(C1+1, C2-1, C3)*C2
    if C3>=1:#3個の皿
      ret += dfs(C1, C2+1, C3-1)*C3
    ret = ret / (C1+C2+C3)
    dp[C1][C2][C3] = ret
  return dp[C1][C2][C3]
print(dfs(P.count(1), P.count(2), P.count(3)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
#solve
def solve():
    n = II()
    d = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    for i in range(n + 1):
        di = d[i]
        dim1 = d[i - 1]
        for j in range(n + 1):
            dim1jp1 = dim1[j + 1]
            dijm1 = di[j - 1]
            dij = di[j]
            for k in range(n + 1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * dim1jp1[k]
                if j: res += j * dijm1[k + 1]
                if k: res += k * dij[k-1]
                d[i][j][k] = res / l
    print(d[c3][c2][c1])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
#solve
def solve():
    n = II()
    d = defaultdict(int)
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    for i in range(n+1):
        for j in range(n+1):
            for k in range(n+1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * d[(k, j + 1, i - 1)]
                if j: res += j * d[(k + 1, j - 1, i)]
                if k: res += k * d[(k - 1, j, i)]
                d[(k, j, i)] = res / l
    print(d[(c1, c2, c3)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
#solve
def solve():
    n = II()
    d = defaultdict(int)
    @lru_cache(maxsize=300 ** 3)
    def f(c1, c2, c3):
        tmp = 1 / (1 - (n - c1 - c2 - c3) / n) if c1 != 0 or c2 != 0 or c3 != 0 else 0
        if c1: tmp += f(c1 - 1, c2, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c2: tmp += f(c1 + 1, c2 - 1, c3) * c2 / n / (1 - (n - c1 - c2 - c3) / n)
        if c3: tmp += f(c1, c2 + 1, c3 - 1) * c3 / n / (1 - (n - c1 - c2 - c3) / n)
        return tmp
    c = LI()
    print(f(c.count(1), c.count(2), c.count(3)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    d = defaultdict(int)
    def f(c1, c2, c3):
        if d[(c1,c2,c3)]: return d[(c1,c2,c3)]
        tmp = 1 / (1 - (n - c1 - c2 - c3) / n) if c1 != 0 or c2 != 0 or c3 != 0 else 0
        if c1: tmp += f(c1 - 1, c2, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c2: tmp += f(c1 + 1, c2 - 1, c3) * c2 / n / (1 - (n - c1 - c2 - c3) / n)
        if c3: tmp += f(c1, c2 + 1, c3 - 1) * c3 / n / (1 - (n - c1 - c2 - c3) / n)
        d[(c1, c2, c3)] = tmp
        return tmp
    c = LI()
    print(f(c.count(1), c.count(2), c.count(3)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    d = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    def f(c1, c2, c3):
        if d[c1][c2][c3]: return d[c1][c2][c3]
        tmp = 1 / (1 - (n - c1 - c2 - c3) / n) if c1 != 0 or c2 != 0 or c3 != 0 else 0
        if c1: tmp += f(c1 - 1, c2, c3) * c1 / n / (1 - (n - c1 - c2 - c3) / n)
        if c2: tmp += f(c1 + 1, c2 - 1, c3) * c2 / n / (1 - (n - c1 - c2 - c3) / n)
        if c3: tmp += f(c1, c2 + 1, c3 - 1) * c3 / n / (1 - (n - c1 - c2 - c3) / n)
        d[c1][c2][c3] = tmp
        return tmp
    c = LI()
    print(f(c.count(1), c.count(2), c.count(3)))
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

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

def calc(i, j, k):
    if i < 0 or j < 0 or k < 0:
        return 0
    if dp[k][j][i] != -1:
        return dp[k][j][i]
    if i == j == k == 0:
        dp[i][j][k] = 0
        return 0
    if i > N or j > J + K or k > K:
        dp[k][i][j] = 0
        return 0
    tmp = N / (i + j + k)
    tmp += i / (i + j + k) * calc(i - 1, j, k)
    tmp += j / (i + j + k) * calc(i + 1, j - 1, k)
    tmp += k / (i + j + k) * calc(i, j + 1, k - 1)
    dp[k][j][i] = tmp
    return tmp

I = 0
J = 0
K = 0
for a in A:
    if a == 1:
        I += 1
    elif a == 2:
        J += 1
    else:
        K += 1

# print (i, j , k)
print (calc(I, J , K))