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: Runtime Error

Solution code:
def memoize(f):
    """ Memoization decorator for functions taking one or more arguments. """
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)
@memoize
def sushi(c0,c1,c2,c3):
	if c2==c3==0 and c1==1:
		return n
	answer = n/(n-c0)
	if c1>0:
		answer+=(c1/(c1+c2+c3))*(sushi(c0+1,c1-1,c2,c3))
	if c2>0:
		answer+=(c2/(c1+c2+c3))*(sushi(c0,c1+1,c2-1,c3))
	if c3>0:
		answer+=(c3/(c1+c2+c3))*(sushi(c0,c1,c2+1,c3-1))

	return answer


n = int(raw_input())
plates = map(int,raw_input().split(' '))

count = {i:0 for i in range(4)}
for plate in plates:
	count[plate]+=1

print sushi(float(count[0]),float(count[1]),float(count[2]),float(count[3]))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

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

num = max(one,two,three)

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

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

print(dp[one][two][three])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**5)
n = int(input())
cnt = [0,0,0]
dp = [[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
for i in map(int,input().split()):
  cnt[i-1] += 1
def fj(i,j,k):
  global dp
  if i < 0 or j < 0 or k < 0 or i>n or j>n or k>cnt[2]:
    return 0.0
  if dp[i][j][k] != 0.0:
    return dp[i][j][k]
  s = i+j+k
  res = n/s + fj(i-1,j,k)*i/s + fj(i+1,j-1,k)*j/s + fj(i,j+1,k-1)*k/s
  dp[i][j][k] = res
  return dp[i][j][k]
print(fj(*cnt))

Submission status: Runtime Error

Solution code:
import numpy as np
n = int(input())
a = list(map(int, input().split()))

dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
def dfs(n1, n2, n3):
    if n1 == 1 and n2 == n3 == 0:
        return n

    if dp[n1][n2][n3] is not None:
        return dp[n1][n2][n3]

    r = (
        (n1 > 0 and dfs(n1 - 1, n2, n3) * n1) +
        (n2 > 0 and dfs(n1 + 1, n2 - 1, n3) * n2) +
        (n3 > 0 and dfs(n1, n2 + 1, n3 - 1) * n3)
    ) + n
    r /= n1 + n2 + n3
    dp[n1][n2][n3] = r
    return r

from collections import Counter
cnt = Counter(a)
print(dfs(*(cnt.get(i, 0) for i in range(1, 3 + 1))))

Submission status: Runtime Error

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

import sys
import bisect
input = sys.stdin.readline
def LI(): return list(map(int,input().split()))
def LIR(n): return [LI() for _ in range(n)]

def J():
    n = int(input())
    a = LI()
    a.sort()
    one = bisect.bisect_right(a,1)
    two = bisect.bisect_right(a,2) - one
    three = n - one - two

    #dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から
    #               寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(three+1):
        for j in range(two+three+1 - k):
            for i in range(one+two+three+1-k-j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = n*1.0
                if i > 0:
                    tmp += i*dp[i-1][j][k]
                if j > 0:
                    tmp += j*dp[i+1][j-1][k]
                if k > 0:
                    tmp += k*dp[i][j+1][k-1]
                dp[i][j][k] = tmp/(i+j+k)
    print(dp[one][two][three])
if __name__ == '__main__':
    J()
#!/usr/bin/env python3
#dp9 #Sushi

import sys
import bisect
input = sys.stdin.readline
def LI(): return list(map(int,input().split()))
def LIR(n): return [LI() for _ in range(n)]

def J():
    n = int(input())
    a = LI()
    a.sort()
    one = bisect.bisect_right(a,1)
    two = bisect.bisect_right(a,2) - one
    three = n - one - two

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

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
from functools import lru_cache
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]


N = I()
A = LI()
t = [0, 0, 0]
for a in A:
    t[a-1] += 1
A, B, C = t

dp = [[[0]*(N+1) for i in range(N+1)] for j 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) and (j==0) and (k==0):
                continue
            dp[i][j][k] += N/(i+j+k)
            d = dp[i][j][k]
            if (i<N):
                dp[i+1][j][k] += (i+1)*d/(i+1+j+k)
            if (i>0) and (j<N):
                dp[i-1][j+1][k] += (j+1)*d/(i+j+k)
            if (j>0) and (k<N):
                dp[i][j-1][k+1] += (k+1)*d/(i+j+k)

print(dp[A][B][C])



"""

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

dp = [[[0]*303 for i in range(303)] for j in range(303)]

def calc(n1,n2,n3):
    tmp = 1
    if dp[n1][n2][n3] != 0:
        return dp[n1][n2][n3]
    elif n1 == n2 == n3 == 0:
        return 0
    else:
        if n1 != 0:
            tmp += n1/N*calc(n1-1,n2,n3)
        if n2 != 0:
            tmp += n2/N*calc(n1+1,n2-1,n3)
        if n3 != 0:
            tmp += n3/N*calc(n1,n2+1,n3-1)
        tmp *= N/(n1+n2+n3)
        dp[n1][n2][n3] = tmp
        return tmp

N = inp()
aa = inpl()
cnts = [0]*4
for a in aa:
    cnts[a] += 1

print(calc(*cnts[1:]))

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

dp = np.zeros((300,300,300),dtype=int)

def calc(n1,n2,n3):
    tmp = 1
    if dp[n1][n2][n3] != 0:
        return dp[n1][n2][n3]
    elif n1 == n2 == n3 == 0:
        return 0
    else:
        if n1 != 0:
            tmp += n1/N*calc(n1-1,n2,n3)
        if n2 != 0:
            tmp += n2/N*calc(n1+1,n2-1,n3)
        if n3 != 0:
            tmp += n3/N*calc(n1,n2+1,n3-1)
        tmp *= N/(n1+n2+n3)
        dp[n1][n2][n3] = tmp
        return tmp

N = inp()
aa = inpl()
cnts = [0]*4
for a in aa:
    cnts[a] += 1

print(calc(*cnts[1:]))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I * 3 + 10, J * 3 + 10 , K * 3 + 10), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I * 2 + 10, J * 2 + 10 , K * 2 + 10), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I * 2, J * 2 , K * 2), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I + 50, J + 50, K + 50), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I + 50, J + 50, K + 50), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I + 10, J + 10, K + 10), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

Solution code:
import numpy as np

def calcdp(i, j, k):
    global dp, N
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    else:
        if i == j == k == 0:
            return 0.0
        else:
            res = float(N)
            if i > 0:
                res += calcdp(i-1, j, k) * i
            if j > 0:
                res += calcdp(i+1, j-1, k) * j
            if k > 0:
                res += calcdp(i, j+1, k-1) * k
            res /= (i + j + k)
            dp[i][j][k] = res
            return res
        

# 入力を受け取る
N = int(input())
al = [int(x) for x in input().split()]

# お寿司の個数毎の皿枚数を数える
I = al.count(1)
J = al.count(2)
K = al.count(3)

# テーブルの初期化
dp = np.zeros((I + 10, J + 10, K + 10), dtype = float)
print(calcdp(I, J, K))

Submission status: Runtime Error

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

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


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

for k in range(three + 1):
    for j in range(two + three + 1 - k):
        for i in range(one + two + three + 1 -k -j):
            if i == 0 and j == 0 and k == 0:
                continue
            ret = 0
            if i > 0:
                ret += dp[i - 1][j][k] * i
            if j > 0:
                ret += dp[i + 1][j - 1][k] * j 
            if k > 0:
                ret += dp[i], [j + 1], [k -1] * k

            ret += N
            ret *= 1.0 / (i + j + k)
            dp[i][j][k] = ret

print(dp[one][two][three])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())

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

@lru_cache(maxsize=N*4)
def calc(i, j, k):
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i > 0:
        ret += calc(i - 1, j, k) * i
    if j > 0:
        ret += calc(i + 1, j - 1, k) * j 
    if k > 0:
        ret += calc(i, j + 1, k -1) * k

    ret += N
    ret *= 1.0 / (i + j + k)
    return ret


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

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

Submission status: Runtime Error

Solution code:
N=int(input())
x,y,z=0,0,0
for i in input().split():
    if i=="1":
        x+=1
    elif i=="2":
        y+=1
    else:
        z+=1
dp=[[[0 for k in range(N+1)] for j in range(y+z+1)] for i in range(z+1)]
fl=[[[0 for k in range(N+1)] for j in range(y+z+1)] for i in range(z+1)]
def f(a,b,c):
    if fl[a][b][c]==1:
        return dp[a][b][c]
    fl[a][b][c]=1
    if a+b+c==0:
        dp[a][b][c]=0
        return 0
    fans=1/(1-(N-a-b-c)/N)
    if a>0:
        fans+=f(a-1,b,c)*a/N/(1-(N-a-b-c)/N)
    if b>0:
        fans+=f(a+1,b-1,c)*b/N/(1-(N-a-b-c)/N)
    if c>0:
        fans+=f(a,b+1,c-1)*c/N/(1-(N-a-b-c)/N)
    dp[a][b][c]=fans
    return fans
print(f(x,y,z))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import os
import sys
from collections import Counter
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

# input = BytesIO(os.read(0, os.fstat(0).st_size)).readline


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


def main():
    n = int(input())
    a = Counter(int(ai) for ai in input().split())

    @memoize
    def solve(i, j, k):
        if (i < 0) or (j < 0) or (k < 0) or (i == j == k == 0):
            return 0

        res = n / (i + j + k) - 1
        res += (solve(i - 1, j, k) + 1) * i / (i + j + k)
        res += (solve(i + 1, j - 1, k) + 1) * j / (i + j + k)
        res += (solve(i, j + 1, k - 1) + 1) * k / (i + j + k)
        return res

    for k in range(n + 1):
        for j in range(n + 1):
            for i in range(n + 1):
                solve(i, j, k)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import os
import sys
from collections import Counter
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

# input = BytesIO(os.read(0, os.fstat(0).st_size)).readline


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


def main():
    n = int(input())
    a = Counter(int(ai) for ai in input().split())

    @memoize
    def solve(i, j, k):
        if (i < 0) or (j < 0) or (k < 0) or (i == j == k == 0):
            return 0

        res = n / (i + j + k) - 1
        res += (solve(i - 1, j, k) + 1) * i / (i + j + k)
        res += (solve(i + 1, j - 1, k) + 1) * j / (i + j + k)
        res += (solve(i, j + 1, k - 1) + 1) * k / (i + j + k)
        return res

    for k in range(a[3] + 1):
        for j in range(a[2] + 1):
            for i in range(a[1] + 1):
                solve(i, j, k)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import os
import sys
from collections import Counter
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

# input = BytesIO(os.read(0, os.fstat(0).st_size)).readline


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


def main():
    n = int(input())
    a = Counter(int(ai) for ai in input().split())

    @memoize
    def solve(i, j, k):
        if (i < 0) or (j < 0) or (k < 0) or (i == j == k == 0):
            return 0

        res = n / (i + j + k) - 1
        res += (solve(i - 1, j, k) + 1) * i / (i + j + k)
        res += (solve(i + 1, j - 1, k) + 1) * j / (i + j + k)
        res += (solve(i, j + 1, k - 1) + 1) * k / (i + j + k)
        return res

    for i in range(n + 1):
        for j in range(n + 1):
            for k in range(n + 1):
                solve(i, j, k)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import os
import sys
from collections import Counter
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

# input = BytesIO(os.read(0, os.fstat(0).st_size)).readline


def memoize(f):
    """ Memoization decorator for a function taking one or more arguments. """

    class memodict(dict):
        def __getitem__(self, *key):
            return dict.__getitem__(self, key)

        def __missing__(self, key):
            ret = self[key] = f(*key)
            return ret

    return memodict().__getitem__


def main():
    n = int(input())
    a = Counter(int(ai) for ai in input().split())

    @memoize
    def solve(i, j, k):
        if i == j == k == 0:
            return 0

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

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
double memo[305][305][305];
int n;

double dp(int i, int j, int k)
{
    if (i==0 && j==0 && k ==0) return 0.0;
    if (memo[i][j][k]!=-1) return memo[i][j][k];

    double res = 0;
    if (i>0) res += dp(i-1,j+1,k)*i;
    if (j>0) res += dp(i,j-1,k+1)*j;
    if (k>0) res += dp(i,j,k-1)*k;
    res += n;
    res *= 1.0/(i+j+k);
    return memo[i][j][k] = res;
}
signed main() {
    cin >>n;
    int cnt[5];
    for(int i = 0; i < n; i++)
    {
        int a;cin >>a;
        cnt[a]++;
    }
    for(int i = 0; i < 303; i++)
    {
        for(int j = 0; j < 303; j++)
        {
            for(int k = 0; k < 303; k++)
            {
                memo[i][j][k] = -1.0;
            }
            
        }
        
    }
    
    cout << fixed;
    cout << std::setprecision(10) << dp(cnt[3],cnt[2],cnt[1])<<endl;
    
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
double memo[305][305][305];
int n;

double dp(int i, int j, int k)
{
    if (i==0 && j==0 && k ==0) return 0.0;
    if (memo[i][j][k]!=-1) return memo[i][j][k];

    double res = 0;
    if (i>0) res += dp(i-1,j+1,k)*i;
    if (j>0) res += dp(i,j-1,k+1)*j;
    if (k>0) res += dp(i,j,k-1)*k;
    res += n;
    res *= 1.0/(i+j+k);
    return res;
}
signed main() {
    cin >>n;
    int cnt[5];
    for(int i = 0; i < n; i++)
    {
        int a;cin >>a;
        cnt[a]++;
    }
    for(int i = 0; i < 303; i++)
    {
        for(int j = 0; j < 303; j++)
        {
            for(int k = 0; k < 303; k++)
            {
                memo[i][j][k] = -1.;
            }
            
        }
        
    }
    
    cout << fixed;
    cout << std::setprecision(10) << dp(cnt[3],cnt[2],cnt[1])<<endl;
    
    return 0;
}

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>

#define F first
#define S second
#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;

int main() {
    ios_base::sync_with_stdio(false);
    cout << setprecision(12);
    cin.tie(nullptr);
    int i0 = 0, j0 = 0, k0 = 0;
    int N; cin >> N;
    forn(i, N) {
        int a; cin >> a;
        if (a == 1)
            i0++;
        else if (a == 2)
            j0++;
        else
            k0++;
    }
    double dp[N + 1][N + 1][N + 1];
    memset(dp, 0, sizeof dp);
    double S = N;
    for (int k = 0; k <= N; k++) {
        for (int j = 0; j <= N; j++) {
            for (int i = 0; i <= N; i++) {
                if (i + j + k == 0)
                    continue;
                double E = 1;
                if (i > 0)
                    E += i / S * dp[i - 1][j][k];
                if (j > 0)
                    E += j / S * dp[i + 1][j - 1][k];
                if (k > 0)
                    E += k / S * dp[i][j + 1][k - 1];
                dp[i][j][k] = S / (i + j + k) * E;
            }
        }
    }
    cout << dp[i0][j0][k0] << endl;
}

Submission status: Runtime Error

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
from collections import defaultdict
input = stdin.readline

n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

# dp = defaultdict(int)
# dp[(0, 0, 0)] = 0
dp = [[[0] * (302) for i in range(302)] for j in range(302)]
# dp[0][0][0] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n - c[0] - n2 - n3 + 1):
            if n1 or n2 or n3:
                dp[n1 + 1][n2 + 1][
                    n3 + 1] = (n + n1 * dp[n1][n2 + 1][n3 + 1] +
                               n2 * dp[n1 + 2][n2][n3 + 1] +
                               n3 * dp[n1 + 1][n2 + 2][n3]) / (n1 + n2 + n3)

print(dp[c[1] + 1][c[2] + 1][c[3] + 1])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

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

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b

@lru_cache()
def f(i,j,k):
    v=0
    if not i+j+k:return 0.0
    v+=n
    if i:v+=f(i-1,j,k)*i
    if j:v+=f(i+1,j-1,k)*j
    if k:v+=f(i,j+1,k-1)*k
    v/=i+j+k
    return v

print(f(k1,k2,k3))

Submission status: Runtime Error

Solution code:
from collections import Counter

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

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, -1, -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, (total - a1) // 2), -1, -1):
            a3 = k - a1 - a2
            if a1 + 2 * a2 + 3 * a3 > total:
                break
            tmp = 0
            if a1:
                tmp += 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])