Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

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

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

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

print(solve(cnt3, cnt2, cnt1))

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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

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

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

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

print(solve(cnt3, cnt2, cnt1))

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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp = [-1]*((n+1)*(n+1)*(n+1))
dp[0] = 0

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

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt1*(n+1)**2  + cnt2*(n+1)**1 + cnt3*(n+1)**0])


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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp = [-1]*((n+1)*(n+1)*(n+1))
dp[0] = 0

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

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt1*(n+1)**2  + cnt2*(n+1)**1 + cnt3*(n+1)**0])

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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

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

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

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt3][cnt2][cnt1])

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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

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

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

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

dfs(cnt3, cnt2, cnt1, n)
print(dp[cnt3][cnt2][cnt1])

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

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

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

for i in range(cnt3 + 1):
    for j in range(cnt3 + cnt2 + 1 - i):
        for k in range(cnt3 + cnt2 + cnt1 + 1 - i - j):
            if i + j + k == 0:
                continue
            res = 1
            if k > 0:
                res += (k/n) * dp[i][j][k-1]
            if j > 0:
                res += (j/n) * dp[i][j-1][k+1]
            if i > 0:
                res += (i/n) * dp[i-1][j+1][k]
            dp[i][j][k] = (n/(i+k+j)) * res

print(dp[cnt3][cnt2][cnt1])