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:
#!/usr/bin/env python3
import sys
from collections import Counter


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

    c = Counter(a)
    kitai = [[[0]*(N+2) for _ in range(N+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
                res = N
                res += kitai[k][j][i-1]*i
                res += kitai[k][j-1][i+1]*j
                res += kitai[k-1][j+1][i]*k
                res /= tot
                kitai[k][j][i] = res
    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 = Counter(a)
    kitai = [[[0]*(N+2) for _ in range(N+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):
                if i == 0 and j == 0 and k == 0:
                    continue
                res = N
                if i:
                    res += kitai[k][j][i-1]*i
                if j:
                    res += kitai[k][j-1][i+1]*j
                if k:
                    res += kitai[k-1][j+1][i]*k
                res /= (i+j+k)
                kitai[k][j][i] = res
    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 = Counter(a)
    kitai = [[[0]*(N+2) for _ in range(N+2)] for _ in range(c[3]+1)]
    kitai[0][0][0] = 0
    for k in range(c[3]+1):
        for j in range(N+1):
            for i in range(N+1):
                if i == 0 and j == 0 and k == 0:
                    continue
                res = N
                if i:
                    res += kitai[k][j][i-1]*i
                if j:
                    res += kitai[k][j-1][i+1]*j
                if k:
                    res += kitai[k-1][j+1][i]*k
                res /= (i+j+k)
                kitai[k][j][i] = res
    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
INF = float("inf")


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

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

    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
INF = float("inf")


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

    c = Counter(a)
    kitai = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
    kitai[0][0][0] = 0
    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
                res = N
                if i - 1 >= 0:
                    res += kitai[i-1][j][k]*i
                if j - 1 >= 0:
                    res += kitai[i+1][j-1][k]*j
                if k - 1 >= 0:
                    res += kitai[i][j+1][k-1]*k
                res /= (i+j+k)
                kitai[i][j][k] = res
    print(kitai[c[1]][c[2]][c[3]])

    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
import functools
sys.setrecursionlimit(10**8)
INF = float("inf")


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

    c = Counter(a)
    kitai = [[[-1]*310 for _ in range(310)] for _ in range(310)]

    @functools.lru_cache(maxsize=None)
    def rec(i, j, k):
        if kitai[i][j][k] >= 0:
            return kitai[i][j][k]
        if i == 0 and j == 0 and k == 0:
            return 0

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

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

    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:
import sys
sys.setrecursionlimit(10**8)
n=int(input())
a=list(map(int,input().split()))
b,c,d=a.count(1),a.count(2),a.count(3)
s=[[[0 for i in range(301)]for j in range(301)]for h in range(301)]
def f(x,y,z):
    if s[x][y][z]:
        return s[x][y][z]
    else:
        if x+y+z==0:
            return 0
        else:
            p=0
            if x>0:p+=x*f(x-1,y,z)
            if y>0:p+=y*f(x+1,y-1,z)
            if z>0:p+=z*f(x,y+1,z-1)
            p+=n
            s[x][y][z]=p/(x+y+z)
            return s[x][y][z] 
print(f(b,c,d))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
b,c,d=a.count(1),a.count(2),a.count(3)
s=[[[0 for i in range(301)]for j in range(301)]for h in range(301)]
def f(x,y,z):
    if s[x][y][z]:
        return s[x][y][z]
    else:
        if x+y+z==0:
            return 0
        else:
            p=0
            if x>0:p+=x*f(x-1,y,z)
            if y>0:p+=y*f(x+1,y-1,z)
            if z>0:p+=z*f(x,y+1,z-1)
            p+=n
            s[x][y][z]=p/(x+y+z)
            return s[x][y][z] 
print(f(b,c,d))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n=int(input())
a=list(map(int,input().split()))
b,c,d=a.count(1),a.count(2),a.count(3)
s=np.zeros((301,301,301))
def f(x,y,z):
    if s[x][y][z]:
        return s[x][y][z]
    else:
        if x+y+z==0:
            return 0
        else:
            p=0
            if x>0:p+=x*f(x-1,y,z)
            if y>0:p+=y*f(x+1,y-1,z)
            if z>0:p+=z*f(x,y+1,z-1)
            p+=n
            s[x][y][z]=p/(x+y+z)
            return s[x][y][z] 
print(f(b,c,d))

Submission status: Time Limit Exceeded

Solution code:

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

def memodp(i,j,k,N):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = N
    if i > 0:
        res += memodp(i-1,j,k,N)*i
    if j > 0:
        res += memodp(i+1,j-1,k,N)*j
    if k > 0:
        res += memodp(i,j+1,k-1,N)*k
    dp[i][j][k] = res/(i+j+k)
    return dp[i][j][k]
    
    
def main():
    N = int( input())
    A = list( map( int, input().split()))
    dishes = [0]*4
    for a in A:
        dishes[a] += 1
    print(memodp(dishes[1], dishes[2], dishes[3], N))
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

def memodp(i,j,k,N):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    res = N
    if i > 0:
        res += memodp(i-1,j,k,N)*i
    if j > 0:
        res += memodp(i+1,j-1,k,N)*j
    if k > 0:
        res += memodp(i,j+1,k-1,N)*k
    dp[i][j][k] = res/(i+j+k)
    return dp[i][j][k]
    
    
def main():
    N = int( input())
    A = list( map( int, input().split()))
    dishes = [0]*4
    for a in A:
        dishes[a] += 1
    print(memodp(dishes[1], dishes[2], dishes[3], N))
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
num3 = a.count(3); num2 = a.count(2)
num1 = n - num2 - num3
dp = [[[0]*(num3+1) for _ in range(n-num1+1)] for _ in range(n+1)]
for k in range(num3+1):
  for j in range(n-num1+1-k):
    for i in range(n+1-j-k):
      if i+j+k == 0:
        continue
      s = i+j+k; c = n
      if i: c += dp[i-1][j][k]*i
      if j: c += dp[i+1][j-1][k]*j
      if k: c += dp[i][j+1][k-1]*k
      dp[i][j][k] = c/s
print(dp[num1][num2][num3])

Submission status: Time Limit Exceeded

Solution code:
def solve(ones, twos, threes, n):
    dp = [[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0

    stack = [(ones, twos, threes, False)]

    while stack:
        a, b, c, proc = stack.pop()

        if dp[a][b][c] >= 0:
            continue

        if not proc:
            stack.append((a, b, c, True))

            if a >= 1:
                stack.append((a-1, b, c, False))

            if a+1 <= n and b >= 1:
                stack.append((a+1, b-1, c, False))

            if b+1 <= n and c >= 1:
                stack.append((a, b+1, c-1, False))
        else:
            den = a + b + c
            ans = n / den
            if a > 0:
                ans += a / den * dp[a-1][b][c]
            if b > 0:
                ans += b / den * dp[a+1][b-1][c]
            if c > 0:
                ans += c / den * dp[a][b+1][c-1]

            dp[a][b][c] = ans

    return dp[ones][twos][threes]


def main():
    n = int(input())
    dishes = [int(c) for c in input().split()]
    
    abc = [0] * 4
    for d in dishes:
        abc[d] += 1

    _, ones, twos, threes = abc
    ans = solve(ones, twos, threes, n)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve(ones, twos, threes, n):
    dp = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0

    stack = [(ones, twos, threes, False)]

    while stack:
        a, b, c, proc = stack.pop()

        if dp[a][b][c] >= 0:
            continue

        if not proc:
            stack.append((a, b, c, True))

            if a > 0:
                stack.append((a-1, b, c, False))

            if b > 0:
                stack.append((a+1, b-1, c, False))

            if c > 0:
                stack.append((a, b+1, c-1, False))
        else:
            den = a + b + c
            ans = n / den
            if a > 0:
                ans += a / den * dp[a-1][b][c]
            if b > 0:
                ans += b / den * dp[a+1][b-1][c]
            if c > 0:
                ans += c / den * dp[a][b+1][c-1]

            dp[a][b][c] = ans

    return dp[ones][twos][threes]


def main():
    n = int(input())
    dishes = [int(c) for c in input().split()]
    
    abc = [0] * 4
    for d in dishes:
        abc[d] += 1

    _, ones, twos, threes = abc
    ans = solve(ones, twos, threes, n)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
dishes = [int(c) for c in input().split()]
dp = [[[0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
abc = [0] * 3
for d in dishes:
    abc[d-1] += 1


def dfs(a, b, c):
    den = a + b + c
    if den == 0:
        return 0

    if dp[a][b][c] > 0:
        return dp[a][b][c]

    ans = n / den
    if a > 0:
        ans += a / den * dfs(a-1, b, c)
    if b > 0:
        ans += b / den * dfs(a+1, b-1, c)
    if c > 0:
        ans += c / den * dfs(a, b+1, c-1)

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


ans = dfs(abc[0], abc[1], abc[2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n=int(input())
    C=[0]*3
    for a in map(int,input().split()):
        C[a-1]+=1

    @lru_cache(None)
    def dfs(x,y,z)->float:
        if((x,y,z)==(0,0,0)): return 0.0
        if(x<0 or y<0 or z<0): return 0.0
        s=x+y+z
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/s

    print(dfs(*C))
resolve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 4
for x in a:
    cnt[x] += 1
#ev[a][b][c] - the expected number of operations so far to get to state (a,b,c)
# easier: p-bility of getting to this state at all
p = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
ev = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
p[cnt[1]][cnt[2]][cnt[3]] = 1
for c in range(cnt[3], -1, -1):
    for b in range(n - cnt[1], -1, -1):
        for a in range(n, -1, -1):
            if a == b == c == 0 or a + b + c > n:
                continue
            p_waste = (n - (a + b + c)) / n
            ev_all = p_waste / (1 - p_waste) + 1
            ev[a][b][c] += ev_all * p[a][b][c]
            # remove 1
            if a != 0:
                p_go = a / (a + b + c)
                p[a - 1][b][c] += p[a][b][c] * p_go
                ev[a - 1][b][c] += ev[a][b][c] * p_go
            # remove 2
            if b != 0:
                p_go = b / (a + b + c)
                p[a + 1][b - 1][c] += p[a][b][c] * p_go
                ev[a + 1][b - 1][c] += ev[a][b][c] * p_go
            # remove 3
            if c != 0:
                p_go = c / (a + b + c)
                p[a][b + 1][c - 1] += p[a][b][c] * p_go
                ev[a][b + 1][c - 1] += ev[a][b][c] * p_go
print(ev[0][0][0])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = [0] * 4
for x in a:
    cnt[x] += 1
#ev[a][b][c] - the expected number of operations so far to get to state (a,b,c)
# easier: p-bility of getting to this state at all
p = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
ev = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
p[cnt[1]][cnt[2]][cnt[3]] = 1
for c in range(n, -1, -1):
    for b in range(n, -1, -1):
        for a in range(n, -1, -1):
            if a == b == c == 0 or a + b + c > n:
                continue
            p_waste = (n - (a + b + c)) / n
            ev_all = p_waste / (1 - p_waste) + 1
            ev[a][b][c] += ev_all * p[a][b][c]
            # remove 1
            if a != 0:
                p_go = a / (a + b + c)
                p[a - 1][b][c] += p[a][b][c] * p_go
                ev[a - 1][b][c] += ev[a][b][c] * p_go
            # remove 2
            if b != 0:
                p_go = b / (a + b + c)
                p[a + 1][b - 1][c] += p[a][b][c] * p_go
                ev[a + 1][b - 1][c] += ev[a][b][c] * p_go
            # remove 3
            if c != 0:
                p_go = c / (a + b + c)
                p[a][b + 1][c - 1] += p[a][b][c] * p_go
                ev[a][b + 1][c - 1] += ev[a][b][c] * p_go
print(ev[0][0][0])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

def rec(x, y, z):
    if dp[x][y][z] != 0:
        return dp[x][y][z]
    if x + y + z == 0:
        return 0
    res = N
    if x > 0:
        res += x * rec(x-1, y, z)
    if y > 0:
        res += y * rec(x+1, y-1, z)
    if z > 0:
        res += z * rec(x, y+1, z-1)
    dp[x][y][z] = res / (x + y + z)
    return dp[x][y][z]

print(rec(C[1], C[2], C[3]))

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(C[3]+1):
    for j in range(C[3]+C[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(C[3]+1):
    for j in range(C[3]+C[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
M = [0] * 4
for a in A:
    M[a] += 1
dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(M[3]+1):
    for j in range(M[3]+M[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print("{:.10f}".format(dp[M[1]][M[2]][M[3]]))

Submission status: Time Limit Exceeded

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

N = int(input())
A = list(map(int, input().split()))
dp = [[[0] * 301 for _ in range(301)] for _ in range(301)]

def rec(x, y, z):
    if dp[x][y][z] != 0:
        return dp[x][y][z]
    if x + y + z == 0:
        return 0
    res = N
    if x > 0:
        res += x * rec(x-1, y, z)
    if y > 0:
        res += y * rec(x+1, y-1, z)
    if z > 0:
        res += z * rec(x, y+1, z-1)
    dp[x][y][z] = res / (x + y + z)
    return dp[x][y][z]

M = [0] * 4
for a in A:
    M[a] += 1
ans = rec(M[1], M[2], M[3])
print("{:.10f}".format(ans))

Submission status: Time Limit Exceeded

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

c1 = 0
c2 = 0
c3 = 0
for i in range(N):
    if A[i] == 1:
        c1 += 1
    elif A[i] == 2:
        c2 += 1
    else:
        c3 += 1
        
dp = [[[0]*(c3+1) for _ in range(c2+c3+1)] for _ in range(N+1)]

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

ans = f(dp, N, 0, 0)
ans = f(dp, c1, c2, c3)
print(ans)

Submission status: Time Limit Exceeded

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

c1 = 0
c2 = 0
c3 = 0
for i in range(N):
    if A[i] == 1:
        c1 += 1
    elif A[i] == 2:
        c2 += 1
    else:
        c3 += 1
        
dp = [[[0]*(c3+1) for _ in range(c2+c3+1)] for _ in range(N+1)]

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

ans = f(dp, c1, c2, c3)
print(ans)

Submission status: Time Limit Exceeded

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

c1 = 0
c2 = 0
c3 = 0
for i in range(N):
    if A[i] == 1:
        c1 += 1
    elif A[i] == 2:
        c2 += 1
    else:
        c3 += 1
        
dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

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

ans = f(dp, c1, c2, c3)
print(ans)

Submission status: Time Limit Exceeded

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

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


def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0.0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))
    
p_j()

Submission status: Time Limit Exceeded

Solution code:
def p_j():
    def recursion_j(i, j, k):
        if dp[i][j][k] > 0:
            return dp[i][j][k]
        if i == j == k == 0:
            return 0

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

    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(c[0], c[1], c[2]))
    
p_j()

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin
 
input = stdin.readline
sys.setrecursionlimit(10 ** 6)
 
def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0
 
    res = 0
    if i > 0:
        res += recursion_j(n, dp, i - 1, j, k) * i
    if j > 0:
        res += recursion_j(n, dp, i + 1, j - 1, k) * j
    if k > 0:
        res += recursion_j(n, dp, i, j + 1, k - 1) * k
    res += n
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res
 
 
def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))
    
if __name__ == '__main__':
	p_j()

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import stdin

input = stdin.readline
sys.setrecursionlimit(10 ** 6)
 
def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0
 
    res = 0
    if i > 0:
        res += recursion_j(n, dp, i - 1, j, k) * i
    if j > 0:
        res += recursion_j(n, dp, i + 1, j - 1, k) * j
    if k > 0:
        res += recursion_j(n, dp, i, j + 1, k - 1) * k
    res += n
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res
 
 
def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))
    
if __name__ == '__main__':
	p_j()

Submission status: Time Limit Exceeded

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

def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0

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


def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))

p_j()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

    for i in range(c3+1):
        for j in range(N+1):
            for k in range(N+1):
                if i>0 and j<N:
                    dp[i][j][k] += (i/N)*dp[i-1][j+1][k]
                if j>0 and k<N:
                    dp[i][j][k]+=(j/N)*dp[i][j-1][k+1]
                if k>0:
                    dp[i][j][k]+=(k/N)*dp[i][j][k-1]
                if  i+j+k == 0:
                    continue
                dp[i][j][k]+=1
                dp[i][j][k]*=N/(i+j+k)
    print(dp[c3][c2][c1])
main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
c1, c2, c3 = 0, 0, 0
for ai in a:
    if ai == 1:
        c1+=1
    elif ai == 2:
        c2 += 1
    else:
        c3 += 1
dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)

# dp[i][j][k] := 3個残りがi個、2個残りがj個、1個残りがk個である状態にするまでの操作回数の期待値
dp = list3d(N+1, N+1, N+1, 0.0)
# 全て残0なら残り回数は0
dp[0][0][0] = 0.0
for i in range(N+1):
    for j in range(N+1):
        for k in range(N+1):
            if i == j == k == 0:
                continue
            # 今現在残っている皿を取る確率
            tmp = (i + j + k) / N
            # そのために必要な回数
            res = 1 / tmp
            # それ以降に必要な回数
            if i and j < N: 
                res += (i/N) / tmp * dp[i-1][j+1][k]
            if j and k < N: 
                res += (j/N) / tmp * dp[i][j-1][k+1]
            if k: 
                res += (k/N) / tmp * dp[i][j][k-1]
            dp[i][j][k] = res
print(dp[C[3]][C[2]][C[1]])