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():
    from collections import Counter
    from functools import lru_cache
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

    n = int(readline())
    *a, = map(int, readline().split())

    ctr = Counter(a)

    @lru_cache(maxsize=None)
    def prob(c1, c2, c3):
        if c1 == c2 == c3 == 0: return 0

        ret = n
        if c1 > 0:
            ret += c1 * prob(c1 - 1, c2, c3)
        if c2 > 0:
            ret += c2 * prob(c1 + 1, c2 - 1, c3)
        if c3 > 0:
            ret += c3 * prob(c1, c2 + 1, c3 - 1)
        ret /= c1 + c2 + c3
        return ret

    ret = prob(*(ctr[k] for k in range(1, 3 + 1)))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache

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

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

@lru_cache(n**3)
def dfs(one,two,three):
    if one<0 or two<0 or three<0:
        return 0
    s = one+two+three
    if s == 0:
        return 0
    zero = n-s
    tmp = (one*dfs(one-1,two,three) + two*dfs(one+1, two-1, three) + three*dfs(one,two+1,three-1) + n)/(n - zero)
    return tmp

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

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    A = LI()
    cnt = [0]*4
    for a in A:
        cnt[a] += 1
    dp = [ [ [0]*(N+1)  for _ in range(N+1)] for _ in range(N+1)]  #dp[i][j][k] = N/i * dp[i-1][j][k] + N/j * dp[i][j-1][k] + N/k * dp[i][j][k-1]
    dp[0][0][0] = 0
    def dfs(i,j,k):
        if (i,j,k) == (0,0,0):
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]

        res = N/(i+j+k)

        if i:
            res += dfs(i-1,j+1,k) * i/(i+j+k)
        if j:
            res += dfs(i,j-1,k+1) * j/(i+j+k)
        if k:
            res += dfs(i,j,k-1) * k/(i+j+k)

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
C = Counter(A)
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]
def f(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 += f(i-1,j,k) * i
    if j > 0:
        res += f(i+1,j-1,k) * j
    if k > 0:
        res += f(i,j+1,k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res
C1,C2,C3 =C[1],C[2],C[3]
print(f(C1,C2,C3))

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
C = Counter(A)
#dp = -np.ones((N+1,N+1,N+1))
dp = [[[-1 for i in range(N+1)] for j in range(N+1)] for k in range(N+1)]
def f(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 += f(i-1,j,k) * i
    if j > 0:
        res += f(i+1,j-1,k) * j
    if k > 0:
        res += f(i,j+1,k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res
C1,C2,C3 =C[1],C[2],C[3]
print(f(C1,C2,C3))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dic = dict()
dic[0] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  if uno + dos*301 + tres*90601 in dic:
    return dic[uno + dos*301 + tres*90601]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[uno + dos*301 + tres*90601] = res
  return res
print(dfs(a.count(1),a.count(2),a.count(3)))

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
dic = dict()
dic[(0,0,0)] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  if (uno,dos,tres) in dic:
    return dic[(uno,dos,tres)]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[(uno,dos,tres)] = res
  return res
 
print(dfs(a.count(1),a.count(2),a.count(3)))

Submission status: Time Limit Exceeded

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

n = int(input())
a = list(map(int, input().split()))
dic = dict()
dic[(0,0,0)] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  if (uno,dos,tres) in dic:
    return dic[(uno,dos,tres)]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[(uno,dos,tres)] = res
  return res

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
N = int(input())
A = list(map(int,input().split()))
from collections import Counter
C = Counter(A)
dp = -np.ones((N+1,N+1,N+1))
def f(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 += f(i-1,j,k) * i
    if j > 0:
        res += f(i+1,j-1,k) * j
    if k > 0:
        res += f(i,j+1,k-1) * k
    res += N
    res /= i+j+k
    dp[i][j][k] = res
    return res
C1,C2,C3 =C[1],C[2],C[3]
print(f(C[1],C[2],C[3]))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[0]*3
for i in map(int,input().split()):
    A[i-1]+=1
dp=[[[0]*(n+2)for _ in range(n+2)]for __ in range(n+2)]
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if i+j+k!=0:
                dp[i][j][k]=(dp[i-1][j+1][k]*i+dp[i][j-1][k+1]*j+dp[i][j][k-1]*k+n)/(i+j+k)
i,j,k=A
print(dp[k][j][i])

Submission status: Time Limit Exceeded

Solution code:
def rec(i, j, k, n, dp):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i + j + k == 0:
        return 0

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

n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(3)]

for i, ai in enumerate(a):
    b[ai - 1] += 1

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

print(rec(b[0], b[1], b[2], n, dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
N = int(input())
A = [int(a) for a in input().split()]

f = A.count(1)
s = A.count(2)
t = A.count(3)

dp = [[["0"]*(t+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0
def P(i, j, k):
    if dp[i][j][k] != "0":
        return dp[i][j][k]
    res = N
    if i > 0:
        res += P(i-1, j, k)*i
    if j > 0 and i < N:
        res += P(i+1, j-1, k)*j
    if k > 0 and j < N:
        res += P(i, j+1, k-1)*k
    dp[i][j][k] = res/(i+j+k)
    return dp[i][j][k]

print(P(f, s, t))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
one = c[1]
two = c[2]
three = c[3]

m = 301
memo = [[[-1] * m for _ in range(m)] for _ in range(m)]
memo[0][0][0] = 0.0


def sushi(x, y, z):
    if memo[x][y][z] >= 0:
        return memo[x][y][z]

    res = 0.
    if x > 0:
        res += sushi(x - 1, y, z) * x
    if y > 0:
        res += sushi(x + 1, y - 1, z) * y
    if z > 0:
        res += sushi(x, y + 1, z - 1) * z
    res = (res + N) / (x + y + z)
    memo[x][y][z] = res
    return res


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2**20)

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

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

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

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

print(calc(*S))

Submission status: Time Limit Exceeded

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

N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]#1,2,3個の寿司が載っている皿の枚数
for i in A:
    abc[i-1]+=1

#1,2,3個の寿司が載っている皿の枚数がi,j,kから全てを取るのに必要な期待値
dp=[[[0]*(N+1) for _ in range(N+1)] for i in range(N+1)]

          
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
    x,y,z=0,0,0
    if i-1>=0:
        x=rec(i-1,j,k)*i
    if j-1>=0:
        y=rec(i+1,j-1,k)*j
    if k-1>=0:
        z=rec(i,j+1,k-1)*k
    dp[i][j][k]=((x+y+z)+N)/(i+j+k)
    return dp[i][j][k]
            
print(rec(abc[0],abc[1],abc[2]))

Submission status: Time Limit Exceeded

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

N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]#1,2,3個の寿司が載っている皿の枚数
for i in A:
    abc[i-1]+=1

#1,2,3個の寿司が載っている皿の枚数がi,j,kから全てを取るのに必要な期待値
dp=[[[0]*(N+1) for _ in range(N+1)] for i in range(N+1)]

          
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
    x,y,z=0,0,0
    if i-1>=0:
        x=rec(i-1,j,k)*i
    if j-1>=0:
        y=rec(i+1,j-1,k)*j
    if k-1>=0:
        z=rec(i,j+1,k-1)*k
    dp[i][j][k]=((x+y+z)+N)/(i+j+k)
    return dp[i][j][k]
            
print(rec(abc[0],abc[1],abc[2]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
dp = []
for i in range(n+1):
  pp = []
  for j in range(n+1):
    lp = []
    for k in range(n+1):
      lp.append(0)
    pp.append(lp)
  dp.append(pp)
mp = {1:0, 2:0, 3:0}
for x in a:
  mp[x] += 1
#one two three
dp[mp[1]][mp[2]][mp[3]]=0

def probrec(i, j, k):
  if i==0 and j == 0 and k==0:
    return 0
  if i>n or j>mp[2]+mp[3] or k>mp[3]:
    return 0
  if i<0 or j<0 or k<0:
    return 0
  if dp[i][j][k] != 0:
    return dp[i][j][k]

  dp[i][j][k] = (1+probrec(i-1, j, k)*(i)/n + probrec(i+1, j-1, k)*(j)/n + probrec(i, j+1, k-1)*(k)/n)/((i+j+k)/n)
  return dp[i][j][k]

probrec(mp[1], mp[2], mp[3])
print(dp[mp[1]][mp[2]][mp[3]])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

N, *a = map(int, open(0).read().split())
dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]


def dfs(i, j, k):
    if 0 <= dp[i][j][k]:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    
    res = 0
    if 0 < i:
        res += dfs(i - 1, j, k) * i
    if 0 < j:
        res += dfs(i + 1, j - 1, k) * j
    if 0 < k:
        res += dfs(i, j + 1, k - 1) * k
    res += N
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res


def solve():
    one, two, three = 0, 0, 0
    for ai in a:
        if ai == 1:
            one += 1
        elif ai == 2:
            two += 1
        else:
            three += 1
    ans = dfs(one, two, three)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
d = [[[-1]*301 for i in range(301)] for i in range(301)]
def f(one, two, three, n):
	count = one+two+three
	if d[one][two][three] != -1:
		return d[one][two][three]
	else:
		if count == 0:
			return 0

		ans = n/count
		temp = 0

		if one > 0:
			temp += one*f(one-1, two, three, n)

		if two > 0:
			temp += two*f(one+1, two-1, three, n)

		if three > 0:
			temp += three*f(one, two+1, three-1, n)

		d[one][two][three] = ans+temp/count
		return ans+temp/count

n = int(input())
x = list(map(int, input().split()))
one = x.count(1)
two = x.count(2)
three = x.count(3)


print(f(one, two, three, n))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = input().split()
px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nx+1) for y in range(ny+1)] for z in range(nz+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[z][y][x-1]*x/s
        if y > 0:
          t += dp[z][y-1][x+1]*y/s
        if z > 0:
          t += dp[z-1][y+1][x]*z/s
        
        dp[z][y][x] += t


print(dp[pz][py][px])

Submission status: Time Limit Exceeded

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

px = py = pz = 0
for a in A:
  if a == '1':
    px += 1
  elif a == '2':
    py += 1
  elif a == '3':
    pz += 1

nx = px + py + pz
ny = py + pz
nz = pz

dp = [[[0]*(nz+1) for y in range(ny+1)] for x in range(nx+1)]

for z in range(nz+1):
  for y in range(ny+1-z):
    for x in range(nx+1-z-y):
      if x == y == z == 0:
        continue
      
      else:
        s = x + y + z
        t = N/s
        if x > 0:
          t += dp[x-1][y][z]*x/s
        if y > 0:
          t += dp[x+1][y-1][z]*y/s
        if z > 0:
          t += dp[x][y+1][z-1]*z/s
        
        dp[x][y][z] += t


print(dp[px][py][pz])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
pos = [0, 0, 0]
for a in A:
  if a == 1:
    pos[0] += 1
  elif a == 2:
    pos[1] += 1
  elif a == 3:
    pos[2] += 1


dp = [[[0]*(N+1) for y in range(N+1)] for x in range(N+1)]
transition = [[1, 0, 0, 0], [-1, 1, 0, 1], [0, -1, 1, 2]]

def get_expectation(pos):
  global dp
  px, py, pz = pos
  if px == py == pz == 0:
    return 0
  elif px<0 or px>N or py<0 or py>N or pz<0 or pz>N:
    return 0
  else:
    if dp[px][py][pz] > 0:
      return dp[px][py][pz]
    else:
      for dx, dy, dz, idx in transition:
        s = px + py + pz
        dp[px][py][pz] += (get_expectation([px-dx, py-dy, pz-dz]) + N/s)*[px, py, pz][idx]/s
      
      return dp[px][py][pz]


print(get_expectation(pos))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
pos = [0, 0, 0]
for a in A:
  if a == 1:
    pos[0] += 1
  elif a == 2:
    pos[1] += 1
  elif a == 3:
    pos[2] += 1


dp = [[[0]*(N+1) for y in range(N+1)] for x in range(N+1)]


def get_expectation(pos):
  global dp
  px, py, pz = pos
  if px == py == pz == 0:
    return 0
  elif px<0 or px>N or py<0 or py>N or pz<0 or pz>N:
    return 0
  else:
    if dp[px][py][pz] > 0:
      return dp[px][py][pz]
    else:
      transition = [[1, 0, 0, 0], [-1, 1, 0, 1], [0, -1, 1, 2]]
      for dx, dy, dz, idx in transition:
        s = px + py + pz
        dp[px][py][pz] += (get_expectation([px-dx, py-dy, pz-dz]) + N/s)*[px, py, pz][idx]/s
      
      return dp[px][py][pz]


print(get_expectation(pos))

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
a = collections.Counter(list(map(int, input().split())))
dp = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

'''
dp[n][m][k] = 
    # 1個の皿を選ぶ確率
    dp[n-1][m][k] * n/N + 
    # 2
    dp[n+1][m-1][k] * m/N + 
    # 3
    dp[n][m+1][k-1] * k/N + 
    # 0
    dp[n][m][k] * (N-n-m-k)/N + 
    # 操作回数
    1
これを式変形してdp[n][m][k]を右辺から消す
'''


def solve(n, m, k):
    if n == 0 and m == 0 and k == 0:
        return 0

    if dp[n][m][k] >= 0:
        return dp[n][m][k]

    r = 0
    if n > 0:
        r += solve(n-1, m, k) * n
    if m > 0:
        r += solve(n+1, m-1, k) * m
    if k > 0:
        r += solve(n, m+1, k-1) * k

    r = (r+N)/(n+m+k)
    dp[n][m][k] = r
    return r


print(solve(a[1], a[2], a[3]))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
px = py = pz = 0
for a in A:
  if a == 1:
    px += 1
  elif a == 2:
    py += 1
  elif a == 3:
    pz += 1

K = sum(A)

is_not_added = [[[True]*(N+1) for y in range(N+1)] for x in range(N+1)]
xyz = [[[0, 0, 0]]]
is_not_added[0][0][0] = False

transition = [[1, 0, 0, 0], [-1, 1, 0, 1], [0, -1, 1, 2]]
for k in range(1, K+1):
  _xyz = []
  for x, y, z in xyz[k-1]:
    for dx, dy, dz, _ in transition:
      if 0<=x+dx<=N and 0<=y+dy<=N and 0<=z+dz<=N \
          and is_not_added[x+dx][y+dy][z+dz]:
        is_not_added[x+dx][y+dy][z+dz] = False
        _xyz.append([x+dx, y+dy, z+dz])
  
  xyz.append(_xyz)


dp = [[[0]*(N+1) for y in range(N+1)] for x in range(N+1)]
for k in range(1, K+1):
  for x, y, z in xyz[k]:
    for dx, dy, dz, idx in transition:
      if 0<=x-dx<=N and 0<=y-dy<=N and 0<=z-dz<=N:
        w = [x, y, z][idx]
        s = x + y + z
        dp[x][y][z] += (dp[x-dx][y-dy][z-dz] + N/s) * w/s

print(dp[px][py][pz])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
d = [0]*((N+1)**3)
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            if i:
                E += (i*N)/(s0**2) + d[x-1]*(i/s0)
            if j:
                E += (j*N)/(s0**2) + d[x-N]*(j/s0)
            if k:
                E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = list(map(int, input().split()))
d = [0]*((N+1)**3)
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            if s0:
                E += (i*N)/(s0**2) + d[x-1]*(i/s0)
                E += (j*N)/(s0**2) + d[x-N]*(j/s0)
                E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(pow(10, 8))
N = int(input())
As = list(map(int, input().split()))
d = dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
def decode(x):
    return [(x // ((N+1)**i))%(N+1) for  i in range(3)]
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for x in range((N+1)**3):
    E = 0
    i,j,k = decode(x)
    s0 = N-i-j-k
    if i:
        E += (i*N)/((N-s0)**2) + d[x-1]*(i/(N-s0))
    if j:
        E += (j*N)/((N-s0)**2) + d[x-N]*(j/(N-s0))
    if k:
        E += (k*N)/((N-s0)**2) + d[x-N**2-N]*(k/(N-s0))
    d[x] = E
print(d[B])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(pow(10, 8))
N = int(input())
As = list(map(int, input().split()))
d = dict()
def decode(x):
    return [(x // ((N+1)**i))%(N+1) for  i in range(4)]
def f(x):
    if x in d:
        return d[x]
    E = 0
    _x = decode(x)
    for i in range(1, 4):
        if _x[i]:
            E += (_x[i]*N)/((N-_x[0])**2) + f(x - (N+1)**i + (N+1)**(i-1))*(_x[i]/(N-_x[0]))
    d[x] = E
    return E
B = 0
for a in As:
    B += (N+1)**a
print(f(B))

Submission status: Time Limit Exceeded

Solution code:
def sushi(cnt):
    n = sum(cnt)
    a, b, c = cnt
    steps = [[[0] * (c + 1) for _ in range(b + c + 1)] for _ in range(a + b + c + 1)]

    for z in range(c + 1):
        for y in range(b + c - z + 1):
            for x in range(a + b + c - z - y + 1):
                s = x + y + z
                if s == 0:
                    steps[x][y][z] = 0
                else:
                    res = n / s
                    if x > 0:
                        res += x / s * steps[x - 1][y][z]
                    if y > 0:
                        res += y / s * steps[x + 1][y - 1][z]
                    if z > 0:
                        res += z / s * steps[x][y + 1][z - 1]
                    steps[x][y][z] = res

    return steps[a][b][c]


def main():
    input()  # n
    cnt = [0] * 3
    for s in input().split():
        x = int(s)
        cnt[x - 1] += 1
    return sushi(cnt)


print(main())

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(K+1)] for __ in range(J+K+1)] for ___ in range(I+J+K+1)]

for k in range(K+1):
    for j in range(J+K+1-k):
        for i in range(I+J+K+1-k-j):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < I+J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(K+1)] for __ in range(J+K+1)] for ___ in range(I+J+K+1)]

for k in range(K+1):
    for j in range(J+K+1):
        for i in range(I+J+K+1):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < I+J+K+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

I = a.count(1)
J = a.count(2)
K = a.count(3)

dp = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

for k in range(K+1):
    for j in range(J+K+1):
        for i in range(I+J+K+1):
            if i == 0 and j == 0 and k == 0:
                continue
            if k-1 > -1 and j+1 < n+1:
                dp[i][j][k] += (n/(i+j+k))*(k/n)*dp[i][j+1][k-1]
            if j-1 > -1 and i+1 < n+1:
                dp[i][j][k] += (n/(i+j+k))*(j/n)*dp[i+1][j-1][k]
            if i-1 > -1:
                dp[i][j][k] += (n/(i+j+k))*(i/n)*dp[i-1][j][k]
            dp[i][j][k] += n/(i+j+k)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
a = input().split()

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

# dp =[ [[-1] * (n+1) for _ in range(n+1)] for __ in range(c3+1)]
dp = np.full((c3+1, c2+c3+1, n+1), -1.0)
dp[0][0][0] = 0

def calc_dp(t3,t2,t1):
    global dp
    if(dp[t3][t2][t1] > -1):
        return dp[t3][t2][t1]

    temp = 0
    if(t3 > 0):
        temp += calc_dp(t3-1,t2+1,t1) * t3/(t1+t2+t3)
    if(t2 > 0):
        temp += calc_dp(t3,t2-1,t1+1) * t2/(t1+t2+t3)
    if(t1 > 0):
        temp += calc_dp(t3,t2,t1-1) * t1/(t1+t2+t3)
    temp = temp + n/(t1+t2+t3)

    dp[t3][t2][t1] = temp
    return temp

print(calc_dp(c3,c2,c1))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = input().split()

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

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

def calc_dp(t3,t2,t1):
    global dp
    if(dp[t3][t2][t1] > -1):
        return dp[t3][t2][t1]

    temp = 0
    if(t3 > 0):
        temp += calc_dp(t3-1,t2+1,t1) * t3/(t1+t2+t3)
    if(t2 > 0):
        temp += calc_dp(t3,t2-1,t1+1) * t2/(t1+t2+t3)
    if(t1 > 0):
        temp += calc_dp(t3,t2,t1-1) * t1/(t1+t2+t3)
    temp = temp + n/(t1+t2+t3)

    dp[t3][t2][t1] = temp
    return temp

print(calc_dp(c3,c2,c1))

Submission status: Time Limit Exceeded

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

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

memo = {}
memo[(0, 0, 0)] = 0

def solve(c3, c2, c1):
    if (c3, c2, c1) in memo:
        return memo[(c3, c2, c1)]
    tmp = 0
    num = c1 + c2 + c3
    # c3を選ぶ
    if c3 != 0:
        tmp += (c3 / n) * solve(c3 - 1, c2 + 1, c1)
    # c2を選ぶ
    if c2 != 0:
        tmp += (c2 / n) * solve(c3, c2 - 1, c1 + 1)
    # c1を選ぶ
    if c1 != 0:
        tmp += (c1 / n) * solve(c3, c2, c1 - 1)
    memo[(c3, c2, c1)] = n / num * (tmp + 1)
    return memo[(c3, c2, c1)] 

print(solve(cnt3, cnt2, cnt1))

Submission status: Time Limit Exceeded

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

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

dp = [[[-1]*(cnt1 + cnt2 + cnt3 + 1) for _ in range(cnt2 + cnt3 + 1)] for _ in range(cnt3 + 1)]
dp[0][0][0] = 0

def solve(c3, c2, c1):
    if dp[c3][c2][c1] != -1:
        return dp[c3][c2][c1]
    tmp = 0
    num = c1 + c2 + c3
    # c3を選ぶ
    if c3 != 0:
        tmp += (c3 / n) * solve(c3 - 1, c2 + 1, c1)
    # c2を選ぶ
    if c2 != 0:
        tmp += (c2 / n) * solve(c3, c2 - 1, c1 + 1)
    # c1を選ぶ
    if c1 != 0:
        tmp += (c1 / n) * solve(c3, c2, c1 - 1)
    dp[c3][c2][c1] = n / num * (tmp + 1)
    return dp[c3][c2][c1]

print(solve(cnt3, cnt2, cnt1))

Submission status: Time Limit Exceeded

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


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter


def solve(N: int, a: "List[int]"):

    c = [0]*4
    for A in a:
        c[A] += 1
    kitai = [[[0]*(c[1]+c[2]+c[3]+2) for _ in range(c[2]+c[3]+2)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(c[2]+c[3]+1):
            for i in range(c[1]+c[2]+c[3]+1):
                tot = i+j+k
                if tot == 0:
                    continue
                kitai[k][j][i] = N + kitai[k][j][i-1]*i + kitai[k][j-1][i+1]*j
                kitai[k][j][i] += kitai[k-1][j+1][i]*k
                kitai[k][j][i] /= tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()