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:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)


def find(a0,a1,a2,a3):
    if a1+a2+a3==0:
        return 0
    if d[(a0,a1,a2,a3)]!=0:
        return d[(a0,a1,a2,a3)]
    if a1<0 or a2<0 or a3<0:
        return -1
    p0=a0/n
    p1=a1/n
    p2=a2/n
    p3=a3/n
    d[(a0, a1, a2, a3)]= p0 + p1*(find(a0+1,a1-1,a2,a3)+1) + p2*(find(a0,a1+1,a2-1,a3)+1) +p3*(find(a0,a1,a2+1,a3-1)+1)
    d[(a0, a1, a2, a3)]/=(1-p0)
    return d[(a0,a1,a2,a3)]





n=int(inp())
temp=lis()
ar=[0,0,0,0]
d=defaultdict(int)
for i in temp:
    if i==1:
        ar[1]+=1
    elif i==2:
        ar[2]+=1
    else:
        ar[3]+=1
print(find(ar[0],ar[1],ar[2],ar[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * 4
for i in range(n):
    B[A[i]] += 1

# B = [0, 0,0,300]
# n = sum(B)

C = []
for i in range(B[3],-1,-1):
    for j in range(B[3]+B[2],-1,-1):
        for k in range(n,-1,-1):
            if i+j+k <= n and i+j <= B[3]+B[2]:
                C.append([i, j, k])

# for i in range(2, -1, -1):
#     C.sort(reverse=True, key=lambda x:x[i])

# print(C)
# print(len(C))
# print("sorted")

n2 = n**2 + 1
n1 = n + 1
def ind3(i, j, k):
    return i * n2 + j * n1 + k

# D = [[[0] * (n+1) for i in range(n+1)] for j in range(n+1)]
D = {}

m = len(C)
for i in range(m):
    D[ind3(C[i][0], C[i][1], C[i][2])] = i

# M = [[] for i in range(m)]
# for i in range(m):
#     IND = [[C[i][0]+1, C[i][1]-1, C[i][2]], [C[i][0], C[i][1]+1, C[i][2]-1],\
#            [C[i][0], C[i][1], C[i][2]+1]]
#     for j in range(3):
#         if 0 <= IND[j][0] < n+1 and 0 <= IND[j][1] < n+1 and 0 <= IND[j][2] < n+1:
#             ind = D[IND[j][0]][IND[j][1]][IND[j][2]]
#             M[ind].append(i)

P = [[] for i in range(m)]
E = [[] for i in range(m)]

# print("edge ok")

s_ind = 0
while C[s_ind][:3] != [B[3], B[2], B[1]]:
    # print(C[s_ind][:3] ,[B[3], B[2], B[1]])
    s_ind += 1

# print("s_ind ok")

P[s_ind].append(1)
E[s_ind].append(0)
for i in range(s_ind, m):
    # print(i, C[i], P[i])
    # print(i)
    p = 0
    e = 0
    if len(P[i]) > 0:
        for j in range(len(P[i])):
            p += P[i][j]
            e += P[i][j] * E[i][j]
        e /= p

        if i == m-1:
            print(e)
            break
        
        s3 = C[i][0]
        s2 = C[i][1]
        s1 = C[i][2]
        su = s3 + s2 + s1
        y = n - su
        new_e = e + 1 + (y / (n - y))
        if s3 > 0:
            ind = D[ind3(s3-1, s2+1, s1)]
            # print(ind)
            P[ind].append(p * s3 / su)
            E[ind].append(new_e)
        if s2 > 0:
            ind = D[ind3(s3, s2-1, s1+1)]
            # print(ind)
            P[ind].append(p * s2 / su)
            E[ind].append(new_e)
        if s1 > 0:
            ind = D[ind3(s3, s2, s1-1)]
            # print(ind)
            P[ind].append(p * s1 / su)
            E[ind].append(new_e)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * 4
for i in range(n):
    B[A[i]] += 1

# B = [0, 0,0,300]
# n = sum(B)

C = []
for i in range(B[3],-1,-1):
    for j in range(B[3]+B[2],-1,-1):
        for k in range(n,-1,-1):
            if i+j+k <= n and i+j <= B[3]+B[2]:
                C.append([i, j, k])

# for i in range(2, -1, -1):
#     C.sort(reverse=True, key=lambda x:x[i])

# print(C)
# print(len(C))
# print("sorted")


D = [[[0] * (n+1) for i in range(n+1)] for j in range(n+1)]

m = len(C)
for i in range(m):
    D[C[i][0]][C[i][1]][C[i][2]] = i

# M = [[] for i in range(m)]
# for i in range(m):
#     IND = [[C[i][0]+1, C[i][1]-1, C[i][2]], [C[i][0], C[i][1]+1, C[i][2]-1],\
#            [C[i][0], C[i][1], C[i][2]+1]]
#     for j in range(3):
#         if 0 <= IND[j][0] < n+1 and 0 <= IND[j][1] < n+1 and 0 <= IND[j][2] < n+1:
#             ind = D[IND[j][0]][IND[j][1]][IND[j][2]]
#             M[ind].append(i)

P = [[] for i in range(m)]

# print("edge ok")

s_ind = 0
while C[s_ind][:3] != [B[3], B[2], B[1]]:
    # print(C[s_ind][:3] ,[B[3], B[2], B[1]])
    s_ind += 1

# print("s_ind ok")

P[s_ind].append([1.0, 0])
for i in range(s_ind, m):
    # print(i, C[i], P[i])
    p = 0
    e = 0
    if len(P[i]) > 0:
        for j in range(len(P[i])):
            p += P[i][j][0]
            e += P[i][j][0] * P[i][j][1]
        e /= p

        if i == m-1:
            print(e)
            break
        
        s3 = C[i][0]
        s2 = C[i][1]
        s1 = C[i][2]
        su = s3 + s2 + s1
        y = n - su
        if s3 > 0:
            ind = D[s3-1][s2+1][s1]
            # print(ind)
            P[ind].append([p * s3 / su, e + 1 + (y / (n - y))])
        if s2 > 0:
            ind = D[s3][s2-1][s1+1]
            # print(ind)
            P[ind].append([p * s2 / su, e + 1 + (y / (n - y))])
        if s1 > 0:
            ind = D[s3][s2][s1-1]
            # print(ind)
            P[ind].append([p * s1 / su, e + 1 + (y / (n - y))])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * 4
for i in range(n):
    B[A[i]] += 1

# B = [0, 0,0,150]
# n = sum(B)

C = []
for i in range(B[3],-1,-1):
    for j in range(B[3]+B[2],-1,-1):
        for k in range(n,-1,-1):
            if i+j+k <= n and i+j <= B[3]+B[2]:
                C.append([i, j, k])

# for i in range(2, -1, -1):
#     C.sort(reverse=True, key=lambda x:x[i])

# print(C)
# print("sorted")


D = [[[0] * (n+1) for i in range(n+1)] for j in range(n+1)]

m = len(C)
for i in range(m):
    D[C[i][0]][C[i][1]][C[i][2]] = i

M = [[] for i in range(m)]
for i in range(m):
    IND = [[C[i][0]+1, C[i][1]-1, C[i][2]], [C[i][0], C[i][1]+1, C[i][2]-1], [C[i][0], C[i][1], C[i][2]+1]]
    for j in range(3):
        if 0 <= IND[j][0] < n+1 and 0 <= IND[j][1] < n+1 and 0 <= IND[j][2] < n+1:
            ind = D[IND[j][0]][IND[j][1]][IND[j][2]]
            M[ind].append(i)

P = [[] for i in range(m)]

# print("edge ok")

s_ind = 0
while C[s_ind][:3] != [B[3], B[2], B[1]]:
    # print(C[s_ind][:3] ,[B[3], B[2], B[1]])
    s_ind += 1

P[s_ind].append([1.0, 0])
for i in range(s_ind, m):
    # print(i, C[i], P[i])
    p = 0
    e = 0
    if len(P[i]) > 0:
        for j in range(len(P[i])):
            p += P[i][j][0]
            e += P[i][j][0] * P[i][j][1]
        e /= p

        if i == m-1:
            print(e)
            break
        
        s3 = C[i][0]
        s2 = C[i][1]
        s1 = C[i][2]
        su = s3 + s2 + s1
        y = n - su
        if s3 > 0:
            ind = D[s3-1][s2+1][s1]
            # print(ind)
            P[ind].append([p * s3 / su, e + 1 + (y / (n - y))])
        if s2 > 0:
            ind = D[s3][s2-1][s1+1]
            # print(ind)
            P[ind].append([p * s2 / su, e + 1 + (y / (n - y))])
        if s1 > 0:
            ind = D[s3][s2][s1-1]
            # print(ind)
            P[ind].append([p * s1 / su, e + 1 + (y / (n - y))])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
B = [0] * 4
for i in range(n):
    B[A[i]] += 1

# B = [0, 0,0,150]
# n = sum(B)

C = []
for i in range(B[3],-1,-1):
    for j in range(B[3]+B[2],-1,-1):
        for k in range(n,-1,-1):
            C.append([i, j, k, n-i-j-k])

# for i in range(2, -1, -1):
#     C.sort(reverse=True, key=lambda x:x[i])

# print(C)
# print("sorted")


D = [[[0] * (n+1) for i in range(n+1)] for j in range(n+1)]

m = len(C)
for i in range(m):
    D[C[i][0]][C[i][1]][C[i][2]] = i

M = [[] for i in range(m)]
for i in range(m):
    IND = [[C[i][0]+1, C[i][1]-1, C[i][2]], [C[i][0], C[i][1]+1, C[i][2]-1], [C[i][0], C[i][1], C[i][2]+1]]
    for j in range(3):
        if 0 <= IND[j][0] < n+1 and 0 <= IND[j][1] < n+1 and 0 <= IND[j][2] < n+1:
            ind = D[IND[j][0]][IND[j][1]][IND[j][2]]
            M[ind].append(i)

P = [[] for i in range(m)]

# print("edge ok")

s_ind = 0
while C[s_ind][:3] != [B[3], B[2], B[1]]:
    # print(C[s_ind][:3] ,[B[3], B[2], B[1]])
    s_ind += 1

P[s_ind].append([1.0, 0])
for i in range(s_ind, m):
    # print(i, C[i], P[i])
    p = 0
    e = 0
    if len(P[i]) > 0:
        for j in range(len(P[i])):
            p += P[i][j][0]
            e += P[i][j][0] * P[i][j][1]
        e /= p

        if i == m-1:
            print(e)
            break
        
        s3 = C[i][0]
        s2 = C[i][1]
        s1 = C[i][2]
        su = s3 + s2 + s1
        y = n - su
        if s3 > 0:
            ind = D[s3-1][s2+1][s1]
            # print(ind)
            P[ind].append([p * s3 / su, e + 1 + (y / (n - y))])
        if s2 > 0:
            ind = D[s3][s2-1][s1+1]
            # print(ind)
            P[ind].append([p * s2 / su, e + 1 + (y / (n - y))])
        if s1 > 0:
            ind = D[s3][s2][s1-1]
            # print(ind)
            P[ind].append([p * s1 / su, e + 1 + (y / (n - y))])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))

B = [0] * 4
for i in range(n):
    B[A[i]] += 1

# print(B)

C = []
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            C.append([i, j, k, n-i-j-k])

for i in range(2, -1, -1):
    C.sort(reverse=True, key=lambda x:x[i])

# print(C)


D = [[[0] * (n+1) for i in range(n+1)] for j in range(n+1)]

m = len(C)
for i in range(m):
    D[C[i][0]][C[i][1]][C[i][2]] = i

M = [[] for i in range(m)]
for i in range(m):
    IND = [[C[i][0]+1, C[i][1]-1, C[i][2]], [C[i][0], C[i][1]+1, C[i][2]-1], [C[i][0], C[i][1], C[i][2]+1]]
    for j in range(3):
        if 0 <= IND[j][0] < n+1 and 0 <= IND[j][1] < n+1 and 0 <= IND[j][2] < n+1:
            ind = D[IND[j][0]][IND[j][1]][IND[j][2]]
            M[ind].append(i)

P = [[] for i in range(m)]

s_ind = 0
while C[s_ind][:3] != [B[3], B[2], B[1]]:
    # print(C[s_ind][:3] ,[B[3], B[2], B[1]])
    s_ind += 1

P[s_ind].append([1.0, 0])
for i in range(s_ind, m):
    # print(i, C[i], P[i])
    p = 0
    e = 0
    if len(P[i]) > 0:
        for j in range(len(P[i])):
            p += P[i][j][0]
            e += P[i][j][0] * P[i][j][1]
        e /= p

        if i == m-1:
            print(e)
            break
        
        s3 = C[i][0]
        s2 = C[i][1]
        s1 = C[i][2]
        su = s3 + s2 + s1
        y = n - su
        if s3 > 0:
            ind = D[s3-1][s2+1][s1]
            # print(ind)
            P[ind].append([p * s3 / su, e + 1 + (y / (n - y))])
        if s2 > 0:
            ind = D[s3][s2-1][s1+1]
            # print(ind)
            P[ind].append([p * s2 / su, e + 1 + (y / (n - y))])
        if s1 > 0:
            ind = D[s3][s2][s1-1]
            # print(ind)
            P[ind].append([p * s1 / su, e + 1 + (y / (n - y))])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
ones,twos,threes=0,0,0
for i in l:
    if i==1:
        ones+=1
    elif i==2:
        twos+=1
    else:
        threes+=1
max_ones=ones+twos+threes
max_twos=twos+threes
max_threes=threes
dp=[[[0.0]*(n+1)for i in range(n+1)]for j in range(n+1)]
for k in range(max_threes+1):
    for j in range(max_twos+1-k):
        for i in range(max_ones+1-j-k):
            if i+j+k==0:
                continue
            else:
                dp[i][j][k]=n/(i+j+k)
                if i>0:
                    dp[i][j][k]+=(dp[i-1][j][k]*i)/(i+j+k)
                if j>0:
                    dp[i][j][k]+=(dp[i+1][j-1][k]*j)/(i+j+k)
                if k>0:
                    dp[i][j][k]+=(dp[i][j+1][k-1]*k)/(i+j+k)
print(dp[i][j][k])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


def read_matrix(H, W):
    '''return np.ndarray shape=(H,W) matrix'''
    lines = []
    for _ in range(H):
        lines.append(read())
    lines = ' '.join(lines)  # byte同士の結合ができないのでreadlineでなくreadで
    return np.fromstring(lines, sep=' ', dtype=np.int64).reshape(H, W)


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce, lru_cache
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


N = a_int()
A = ints()
cnt = Counter(A)
'''
dp[i,j,k]...すべての寿司がなくなるまでの操作の期待値(寿司が1つ乗っている皿の数がi,2つがj,3つがk)

dp[i,j,k]= 1(操作回数)+ 
            i/N*(1つの皿が一つ減った場合の操作の期待値) + 
            j/N*(2つの皿が1つ減った場合の操作の期待値) + 
            k/N*(3つの皿が1つ減った場合の操作の期待値)+
            (1-i-j-k)/N * (0つの皿を選んでしまったときの期待値)

dp[i,j,k]= 1+ i/N * dp[i-1,j,k]+ 
            j/N*dp[i+1,j-1,k] + 
            k/N*dp[i,j+1,k-1]+
            (N-i-j-k)/N*dp[i,j,k]

dp[i,j,k]= N/(i+j+k) *
            (1+ i/N * dp[i-1,j,k]+ 
            j/N*dp[i+1,j-1,k] + 
            k/N*dp[i,j+1,k-1])
'''

dp = np.full((N + 1, N + 1, N + 1), -1.0)
# from numba import njit
# @njit('(i8,i8,i8[:])',cache=True)


@lru_cache(maxsize=2**12)
def dfs(i, j, k, N):
    if i < 0 or j < 0 or k < 0 or i == j == k == 0:
        return 0
    ret = 1
    ret += i / N * dfs(i - 1, j, k, N)
    ret += j / N * dfs(i + 1, j - 1, k, N)
    ret += k / N * dfs(i, j + 1, k - 1, N)
    if (i + j + k) == 0:
        return ret
    return N / (i + j + k) * ret


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter as cc
# from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    sys.setrecursionlimit(10**4)
    n = ii()
    a = li()
    c = cc(a)
    N = sum(c.values())
    
    # @lru_cache
    def dfs(x, y, z):
        if x== 0 and y == 0 and z == 0:
            return 0
        tmp = 1
        if x > 0:
            tmp += dfs(x-1, y, z)*x/N
        if y> 0:
            tmp += dfs(x+1, y-1, z)*y/N
        if z > 0:
            tmp += dfs(x, y+1, z-1)*z/N
        tmp *= N/(x+y+z)
        return tmp
    
    print(dfs(c[1], c[2], c[3]))

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter as cc
from functools import lru_cache
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    sys.setrecursionlimit(10**4)
    n = ii()
    a = li()
    c = cc(a)
    N = sum(c.values())
    
    @lru_cache
    def dfs(x, y, z):
        if x== 0 and y == 0 and z == 0:
            return 0
        tmp = 1
        if x > 0:
            tmp += dfs(x-1, y, z)*x/N
        if y> 0:
            tmp += dfs(x+1, y-1, z)*y/N
        if z > 0:
            tmp += dfs(x, y+1, z-1)*z/N
        tmp *= N/(x+y+z)
        return tmp
    
    print(dfs(c[1], c[2], c[3]))

    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(i) for i in input().split()]
x,y,z=0,0,0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    elif i==3:
        z+=1
n=x+y*2+z*3


dp=[[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=0
def calc(h,i,j):
    global n,N
    if h+i+j==0 or h<0 or h>n or i<0 or i>n or j<0:
        return 0
    if dp[h][i][j]!=-1:
        return dp[h][i][j]
    dp[h][i][j]=(calc(h-1,i,j)*h/N+calc(h+1,i-1,j)*i/N+calc(h,i+1,j-1)*j/N+1)*N/(h+i+j)
    return dp[h][i][j]

a=calc(x,y,z)
print(dp[x][y][z])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

x,y,z=a.count(1),a.count(2),a.count(3)
n=x+y*2+z*3


dp=[[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0]=0
def calc(h,i,j):
    global n,N
    if h+i+j==0 or h<0 or h>n or i<0 or i>n or j<0:
        return 0
    if dp[h][i][j]!=-1:
        return dp[h][i][j]
    dp[h][i][j]=(calc(h-1,i,j)*h/N+calc(h+1,i-1,j)*i/N+calc(h,i+1,j-1)*j/N+1)*N/(h+i+j)
    return dp[h][i][j]

a=calc(x,y,z)
print(dp[x][y][z])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(i) for i in input().split()]

x,y,z=a.count(1),a.count(2),a.count(3)
n=x+y*2+z*3


dp=[[[0 for _ in range(n+2)] for _ in range(n+2)] for _ in range(n+2)]

for j in range(n+1):
    for i in range(n+1):
        for h in range(n+1):
            if h+i+j==0 or h+i*2+j*3>n:
                continue
            dp[h][i][j]=(dp[h-1][i][j]*h/N+dp[h+1][i-1][j]*i/N+dp[h][i+1][j-1]*j/N+1)*N/(h+i+j)
            if h==x and i==y and j==z:
                print(dp[x][y][z])
                exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


N = int(input())
memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(a, b, c):
    if a == b == c == 0: return 0
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    
    res = N
    if a > 0: res += a*dp(a-1, b, c)
    if b > 0: res += b*dp(a+1, b-1, c)
    if c > 0: res += c*dp(a, b+1, c-1)
    res /= a+b+c
    
    memo[a][b][c] = res
    return res

def main():
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]

    
    ans = dp(x, y, z)
    
    print(ans)
        

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]
    
    memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    
    def dp(a, b, c):
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        if a > N or b > N or c > N:
            return 0
        
        if memo[a][b][c] != -1:
            return memo[a][b][c]
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[a][b][c] = res
        return res
    
    ans = dp(x, y, z)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]
    
    memo = dict()
    
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        if a + b + c > N:
            return 0
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[(a, b, c)] = res
        return res
    
    ans = dp(x, y, z)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    a, b, c = count[1], count[2], count[3]
    
    memo = dict()
    
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        res = N
        res += a*dp(a-1, b, c)
        res += b*dp(a+1, b-1, c)
        res += c*dp(a, b+1, c-1)
        res /= a+b+c
        
        memo[(a, b, c)] = res
        return res
    
    ans = dp(a, b, c)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)
    
    memo = dict()
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        res = 1
        res += a/N*dp(a-1, b, c)
        res += b/N*dp(a+1, b-1, c)
        res += c/N*dp(a, b+1, c-1)
        res /= 1-(N-a-b-c)/N
        
        memo[(a, b, c)] = res
        return res
    
    a, b, c = count[1], count[2], count[3]
    ans = dp(a, b, c)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

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

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

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


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

    #　1-(0個の皿が選ばれる確率), 繰り返し登場するので先に計算しておく
    prob = 1 - (N - c1 - c2 - c3) / N

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

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


print(func(cnt1, cnt2, cnt3))

Submission status: Time Limit Exceeded

Solution code:
# dp[c1][c2][c3]=
# 		(1個の皿がc1枚、2個の皿がc2枚、3個の皿がc3枚あるとき、全て食べるまでの操作回数の期待値)

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

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

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


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

    #　1-(0個の皿が選ばれる確率), 繰り返し登場するので先に計算しておく
    prob = 1 - (N - c1 - c2 - c3) / N

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

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


print(func(cnt1, cnt2, cnt3))