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:
import sys 
input = sys.stdin.readline
def dfs(state):
    if memo[state[0]][state[1]][state[2]] != -1:
        return memo[state[0]][state[1]][state[2]]
    ret = 0
    if state[0] > 0:
        ret += (dfs((state[0]-1,state[1],state[2]))*state[0])
    if state[1] > 0:
        ret += (dfs((state[0]+1,state[1]-1,state[2]))*state[1])
    if state[2] > 0:
        ret += (dfs((state[0],state[1]+1,state[2]-1))*state[2])
    memo[state[0]][state[1]][state[2]] = (ret + N) / sum(state)
    return memo[state[0]][state[1]][state[2]]
if __name__ == '__main__':
    N = int(input())
    a = list(map(int,input().split(" ")))
    memo = [ [ [-1]*(N+1)  for i in range(N+1)] for j in range(N+1) ]
    memo[0][0][0] = 0
    cur = ( a.count(1) , a.count(2) , a.count(3) )
    print(dfs(cur))

Submission status: Time Limit Exceeded

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

memo = [ [ [-1]*(N+1)  for i in range(N+1)] for j in range(N+1) ]
memo[0][0][0] = 0
def dfs(state):
    if memo[state[0]][state[1]][state[2]] != -1:
        return memo[state[0]][state[1]][state[2]]
    ret = 0
    if state[0] > 0:
        ret += (dfs((state[0]-1,state[1],state[2]))*state[0])
    if state[1] > 0:
        ret += (dfs((state[0]+1,state[1]-1,state[2]))*state[1])
    if state[2] > 0:
        ret += (dfs((state[0],state[1]+1,state[2]-1))*state[2])
    memo[state[0]][state[1]][state[2]] = (ret + N) / sum(state)
    return memo[state[0]][state[1]][state[2]]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    if i > 0: DP[i][j][k] += i / n * dfs(i - 1, j + 1, k)
    if j > 0: DP[i][j][k] += j / n * dfs(i, j - 1, k + 1)
    if k > 0: DP[i][j][k] += k / n * dfs(i, j, k - 1)
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

def dfs(i, j, k):
    if DP[i][j][k] != -1:
        return DP[i][j][k]
    
    DP[i][j][k] = 1
    DP[i][j][k] += i / n * dfs(i - 1, j + 1, k) if i != 0 else 0
    DP[i][j][k] += j / n * dfs(i, j - 1, k + 1) if j != 0 else 0
    DP[i][j][k] += k / n * dfs(i, j, k - 1) if k != 0 else 0
    DP[i][j][k] *= n / (i + j + k)

    return DP[i][j][k]

print(dfs(a, b, c))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
cnt = [0]*5
for i in range(n):
    cnt[a[i]] += 1
maxn = 301
memo = [[[-1]*maxn for i in range(maxn)]for j in range(maxn)]
def dp(i,j,k):
    if i==0 and j==0 and k==0:
        return 0.0
    
    if memo[i][j][k] != -1:
        return memo[i][j][k]

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                if i1 == i2 == i3 == 0:
                    continue
                tmp = N / (i1+i2+i3)
                if i1 > 0:
                    tmp += i1 * dp[i1-1][i2][i3] / (i1+i2+i3)
                if i2 > 0:
                    tmp += i2 * dp[i1+1][i2-1][i3] / (i1+i2+i3)
                if i3 > 0:
                    tmp += i3 * dp[i1][i2+1][i3-1] / (i1+i2+i3)
                dp[i1][i2][i3] = tmp

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

dp = [[[0.0] * 301 for _ in range(301)] for _ in range(301)]
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])

Submission status: Time Limit Exceeded

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

def DP(a1, a2, a3, memo = {}):
    if a1 == a2 == a3 == 0: return 0
    try:
        return memo[(a1, a2, a3)]
    except KeyError:
        ans = N
        if a1 > 0:
            ans += DP(a1-1, a2, a3, memo) * a1 
        if a2 > 0:
            ans += DP(a1+1, a2-1, a3, memo) * a2 
        if a3 > 0:
            ans += DP(a1, a2+1, a3-1, memo) * a3 
        ans /= (a1 + a2 + a3)
        memo[(a1, a2, a3)] = ans
        return ans

a1, a2, a3 = 0, 0, 0
for a in A:
    if a == 1: a1 += 1
    elif a == 2: a2 += 1
    else: a3 += 1
memo = {}
print(DP(a1, a2, a3, memo))

Submission status: Time Limit Exceeded

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

def DP(a1, a2, a3, memo = {}):
    if a1 == a2 == a3 == 0: return 0
    try:
        return memo[(a1, a2, a3)]
    except KeyError:
        ans = N
        if a1 > 0:
            ans += DP(a1-1, a2, a3, memo) * a1 
        if a2 > 0:
            ans += DP(a1+1, a2-1, a3, memo) * a2 
        if a3 > 0:
            ans += DP(a1, a2+1, a3-1, memo) * a3 
        ans /= (a1 + a2 + a3)
        memo[(a1, a2, a3)] = ans
        return ans

a1, a2, a3 = 0, 0, 0
for a in A:
    if a == 1: a1 += 1
    elif a == 2: a2 += 1
    else: a3 += 1
memo = {}
print(DP(a1, a2, a3, memo))

Submission status: Time Limit Exceeded

Solution code:
dp = [[[0 for _ in range(301)] for _ in range(301)] for _ in range(301)]
N = int(input())
A = list(map(int, input().split()))
i, j, k = 0, 0, 0
for a in A:
    if a == 1:
        i += 1
    elif a == 2:
        j += 1
    else:
        k += 1

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

print(rec(i, j, k))

Submission status: Time Limit Exceeded

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
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):
            s = n1 + n2 + n3
            if s != 0:
                temp = n
                if n1 != 0:
                    temp += n1 * dp[(n1 - 1, n2, n3)]
                if n2 != 0:
                    temp += n2 * dp[(n1 + 1, n2 - 1, n3)]
                if n3 != 0:
                    temp += n3 * dp[(n1, n2 + 1, n3 - 1)]
                temp /= s
                dp[(n1, n2, n3)] = temp

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.readline

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

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

mem = {}


def dp(n3, n2, n1, n0):
    if n0 == n:
        return 0
    if not mem.get((n3, n2, n1, n0), None):
        ans = n
        if n3 > 0:
            ans += n3 * dp(n3 - 1, n2 + 1, n1, n0)
        if n2 > 0:
            ans += n2 * dp(n3, n2 - 1, n1 + 1, n0)
        if n1 > 0:
            ans += n1 * dp(n3, n2, n1 - 1, n0 + 1)
        ans /= n - n0
        mem[(n3, n2, n1, n0)] = ans
    return mem[(n3, n2, n1, n0)]


print(dp(*c[::-1]))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from functools import lru_cache
input = stdin.readline

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

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


# dp = []
@lru_cache(None)
def dp(n3, n2, n1, n0):
    if n0 == n:
        return 0
    else:
        ans = n
        if n3 > 0:
            ans += n3 * dp(n3 - 1, n2 + 1, n1, n0)
        if n2 > 0:
            ans += n2 * dp(n3, n2 - 1, n1 + 1, n0)
        if n1 > 0:
            ans += n1 * dp(n3, n2, n1 - 1, n0 + 1)
        ans /= n - n0
        return ans


print(dp(*c[::-1]))

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

dp = [ [ [0] * (C+1) 
           for _ in range(B+C+1)
       ]
           for _ in range(A+B+C+1) 
     ]


for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[a][b][c] = (
                        ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                        ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                        ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
            except:
                continue

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

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

dp = [ [ [0] * (C+1) 
           for _ in range(B+C+1)
       ]
           for _ in range(A+B+C+1) 
     ]


for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # print("a: {}, b: {}, c:{} ".format(a,b,c), end = " ")
            if a == b == c == 0:
                # print("")
                continue

            dp[a][b][c] = (
                    ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                    ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                    ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                   ) / ( a+b+c ) 
            # print(dp[a][b][c])

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    t = [0] * 3
    for c in a:
        t[c-1] += 1
    A,B,C = t
    D = C + 1
    E = B + D
    F = A + E

    r = [[[0]*(F-k-j) for j in range(E-k)] for k in range(D)]

    z = r[0]
    for j in range(E):
        x = z[j]
        if j > 0:
            m = z[j-1]
        for i in range(F-j):
            if not(i or j):
                continue
            w = n
            if i > 0:
                w += x[i-1] * i
            if j > 0:
                w += m[i+1] * j
            x[i] = w / (i+j)

    for k in range(1, D):
        y,z = z,r[k]
        G = F - k

        x = z[0]
        p = y[1]
        for i in range(G):
            x[i] = (n + x[i-1] * i + p[i] * k) / (i+k)

        for j,p,t in zip(range(1,E-k), y[2:],z[1:]):
            for i,w,v in zip(range(G-j), p, x[1:]):
                t[i] = (n + t[i-1] * i + v * j + w * k) / (i+j+k)
            x = t

    return "{:0.9f}".format(r[C][B][A])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    t = [0] * 3
    for c in a:
        t[c-1] += 1
    A,B,C = t
    D = C + 1
    E = B + D
    F = A + E

    r = [[[0]*(F-k-j) for j in range(E-k)] for k in range(D)]
    for k in range(1):
        z = r[k]
        G = F - k
        for j in range(E-k):
            x = z[j]
            if j > 0:
                m = z[j-1]
            l = k + j
            for i in range(G-j):
                if not(i or l):
                    continue
                w = n
                if i > 0:
                    w += x[i-1] * i
                if j > 0:
                    w += m[i+1] * j
                x[i] = w / (i+l)


    y = r[0]
    for k in range(1, D):
        z = r[k]
        G = F - k

        x = z[0]
        p = y[1]
        x[0] = (n + p[0] * k) / k

        for i in range(1,G):
            x[i] = (n + x[i-1] * i + p[i] * k) / (i+k)

        for j in range(1,E-k):
            x = z[j]
            m = z[j-1]
            p = y[j+1]
            l = j + k
            x[0] = (n + m[1] * j + p[0] * k) / l

            for i in range(1,G-j):
                x[i] = (n + x[i-1] * i + m[i+1] * j + p[i] * k) / (i+l)

        y = z


    return "{:0.9f}".format(r[C][B][A])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    t = [0] * 3
    for c in a:
        t[c-1] += 1
    A,B,C = t
    D = C + 1
    E = B + D
    F = A + E

    r = [[[0]*(F-k-j) for j in range(E-k)] for k in range(D)]
    for k in range(D):
        t0 = r[k]
        G = F - k
        for j in range(E-k):
            tj = t0[j]
            if j > 0:
                tm = t0[j-1]
            if k > 0:
                tp = t1[j+1]
            for i in range(G-j):
                if not(i or j or k):
                    continue
                tr = n
                if i > 0:
                    tr += tj[i-1] * i
                if j > 0:
                    tr += tm[i+1] * j
                if k > 0:
                    tr += tp[i] * k
                tj[i] = tr / (i+j+k)
        t1 = t0


    return "{:0.9f}".format(r[C][B][A])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    t = [0] * 4
    for c in a:
        t[c] += 1
    s = [0] * 4
    s[3] = t[3]
    for i in range(2,-1,-1):
        s[i] = s[i+1] + t[i]

    r = [[[0]*(n+1) for _ in range(n+1)] for __ in range(n+1)]
    for c in range(1,n+1):
        for i in range(c,-1,-1):
            if c - i > s[2]:
                break
            ri = r[i]
            if i > 0:
                rm = r[i-1]
            if i < n:
                rp = r[i+1]
            for j in range(c-i,-1,-1):
                k = c - i - j
                if k > s[3]:
                    break
                tr = n / c
                if i > 0:
                    tr += rm[j][k] * i / c
                if j > 0:
                    tr += rp[j-1][k] * j / c
                if k > 0:
                    tr += ri[j+1][k-1] * k / c
                ri[j][k] = tr


    return "{:0.9f}".format(r[t[1]][t[2]][t[3]])


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    t = [0] * 4
    for c in a:
        t[c] += 1

    fm = {}
    fm[(n,0,0,0)] = 0
    def f(t):
        if t in fm:
            return fm[t]
        c = n-t[0]
        r = 1 / (c / n)
        ta = list(t)
        for i in range(1,4):
            if t[i] == 0:
                continue
            ta[i-1] += 1
            ta[i] -= 1
            u = f(tuple(ta))
            r += u * t[i] / c
            ta[i-1] -= 1
            ta[i] += 1
        fm[t] = r
        return r
    r = f(tuple(t))

    return "{:0.9f}".format(r)


print(main())

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

b=[0,0,0]
for i in map(int,input().split()):
    b[i-1]+=1
k1,k2,k3=b
dp=[[[None]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]
dp[0][0][0]=0

for k in range(k3+1):
    for j in range(k2+k3+1-k):
        for i in range(k1+k2+k3+1-j-k):
            if not i+j+k:continue
            dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)

print(dp[k1][k2][k3])

Submission status: Time Limit Exceeded

Solution code:
def solve(n, a):
    c = [0, 0, 0]
    for i in a:
        c[i-1] += 1
    
    stack = [tuple(c)]
    dp = dict()
    dp[(0, 0, 0)] = 0

    while stack:
        x, y, z = stack[-1]
        e = 0.0
        if x > 0:
            if (x - 1, y, z) not in dp:
                stack.append((x - 1, y, z))
                continue
            else:
                e += x * dp[(x - 1, y, z)]

        if y > 0:
            if (x + 1, y - 1, z) not in dp:
                stack.append((x + 1, y - 1, z))
                continue
            else:
                e += y * dp[(x + 1, y - 1, z)]
        
        if z > 0:
            if (x, y + 1, z - 1) not in dp:
                stack.append((x, y + 1, z - 1))
                continue
            else:
                e += z * dp[(x, y + 1, z - 1)]
        
        e += n
        e /= (x + y + z)
        dp[(x, y, z)] = e
        stack.pop()
    
    return dp[tuple(c)]

def main():
    n = int(input())
    a = [int(s) for s in input().split()]

    print(solve(n, a))

main()

Submission status: Time Limit Exceeded

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

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b
dp=[[[0]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]

for k in range(k3+1):
    for j in range(k2+k3+1-k):
        for i in range(k1+k2+k3+1-j-k):
            if not i+j+k:continue
            dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)

print(dp[k1][k2][k3])

Submission status: Time Limit Exceeded

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

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b
dp=[[[0]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]

for b1 in range(1,k1+k2+k3+1):
    for b2 in range(min(b1,k2+k3)+1):
        for b3 in range(min(b2,k3)+1):
            i,j,k=b1-b2,b2-b3,b3
            v=n
            if i:v+=dp[i-1][j][k]*i
            if j:v+=dp[i+1][j-1][k]*j
            if k:v+=dp[i][j+1][k-1]*k
            v/=b1
            dp[i][j][k]=v

print(dp[k1][k2][k3])

Submission status: Time Limit Exceeded

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

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: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (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])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

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

print(h(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (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])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

@lru_cache(maxsize=None)
def h(i,j,k):
  if dp[i][j][k] is None:
    dp[i][j][k] =((i*h(i-1,j  ,k  ) if i else 0)+
                  (j*h(i+1,j-1,k  ) if j else 0)+
                  (k*h(i  ,j+1,k-1) if k else 0)+
                  N)/(i+j+k)
  return dp[i][j][k]

print(h(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (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])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)

@lru_cache(maxsize=None)
def h(i,j,k):
  try:
    return ((i*h(i-1,j  ,k  ) if i else 0)+
            (j*h(i+1,j-1,k  ) if j else 0)+
            (k*h(i  ,j+1,k-1) if k else 0)+
            N)/(i+j+k)
  except ZeroDivisionError:
    return 0

print(h(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (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])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)

@lru_cache(maxsize=None)
def h(i,j,k):
  if (i,j,k) == (0,0,0):
    return 0
  return ((i*h(i-1,j  ,k  ) if i else 0)+
          (j*h(i+1,j-1,k  ) if j else 0)+
          (k*h(i  ,j+1,k-1) if k else 0)+
          N)/(i+j+k)
print(h(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
SC=tuple(SC)

#N=300
#SC=(N-2,1,1,0)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    #if SC[0]<0 or SC[1]<0 or SC[2]<0:
    #    return 0

    k=sum(SC)

    if k==0:
        return 0

    ANS=N
    if SC[0]>0:
        ANS+=days((SC[0]-1,SC[1],SC[2]))*SC[0]
    if SC[1]>0:
        ANS+=days((SC[0]+1,SC[1]-1,SC[2]))*SC[1]
    if SC[2]>0:
        ANS+=days((SC[0],SC[1]+1,SC[2]-1))*SC[2]
        
    DAYSDICT[SC]=ANS/k
    return DAYSDICT[SC]

for k in range(SC[2]+1):
    for j in range(SC[1]+SC[2]+1-k):
        for i in range(SC[0]+SC[1]+SC[2]+1-j-k):
            days((i,j,k))

print(DAYSDICT[SC])

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()))

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1

one,two,three=SC

DAYSLIST=[[[None for k in range(N+1)] for i in range(N+1)] for j in range(N+1)]

def days(one,two,three):
    if one<0 or two<0 or three<0:
        return 0
    if DAYSLIST[one][two][three]!=None:
        return DAYSLIST[one][two][three]
    k=one+two+three

    if k==0:
        return 0

    DAYSLIST[one][two][three]=(days(one-1,two,three)*one+days(one+1,two-1,three)*two+days(one,two+1,three-1)*three+N)/k
    return DAYSLIST[one][two][three]

print(days(one,two,three))

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()))

SC=[0,0,0]#1個,2個,3個

for a in A:
    SC[a-1]+=1
SC=tuple(SC)

#N=300
#SC=(N-2,1,1,0)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[0]<0 or SC[1]<0 or SC[2]<0:
        return 0

    k=sum(SC)

    if k==0:
        return 0

    DAYSDICT[SC]=(days((SC[0]-1,SC[1],SC[2]))*SC[0]+days((SC[0]+1,SC[1]-1,SC[2]))*SC[1]+days((SC[0],SC[1]+1,SC[2]-1))*SC[2]+N)/k
    return DAYSDICT[SC]

print(days(SC))

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()))

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[1]<0 or SC[2]<0 or SC[3]<0:
        return 0

    k=SC[1]+SC[2]+SC[3]

    if k==0:
        return 0

    DAYSDICT[SC]=N/k+days((SC[0]+1,SC[1]-1,SC[2],SC[3]))*SC[1]/k+days((SC[0],SC[1]+1,SC[2]-1,SC[3]))*SC[2]/k+days((SC[0],SC[1],SC[2]+1,SC[3]-1))*SC[3]/k
    return DAYSDICT[SC]

print(days(SC))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[1]<0 or SC[2]<0 or SC[3]<0:
        return 0

    k=SC[1]+SC[2]+SC[3]

    if k==0:
        return 0

    DAYSDICT[SC]=(SC[0]+k)/k+days((SC[0]+1,SC[1]-1,SC[2],SC[3]))*SC[1]/k+days((SC[0],SC[1]+1,SC[2]-1,SC[3]))*SC[2]/k+days((SC[0],SC[1],SC[2]+1,SC[3]-1))*SC[3]/k
    return DAYSDICT[SC]


print(days(SC))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

SC=[0,0,0,0]#0個,1個,2個,3個

for a in A:
    SC[a]+=1
SC=tuple(SC)

DAYSDICT=dict()

def days(SC):
    if DAYSDICT.get(SC)!=None:
        return DAYSDICT[SC]

    if SC[1]<0 or SC[2]<0 or SC[3]<0:
        return 0

    k=SC[1]+SC[2]+SC[3]

    if k==0:
        return 0

    DAYSDICT[SC]=(SC[0]+k)/k+days((SC[0]+1,SC[1]-1,SC[2],SC[3]))*SC[1]/k+days((SC[0],SC[1]+1,SC[2]-1,SC[3]))*SC[2]/k+days((SC[0],SC[1],SC[2]+1,SC[3]-1))*SC[3]/k
    return DAYSDICT[SC]


print(days(SC))