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:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    I = 0
    J = 0
    K = 0
    for a in A:
        if a == 1:
            I += 1
        elif a == 2:
            J += 1
        else:
            K += 1

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

    # def output(lst):
    #     for tmp in lst:
    #         print (tmp)

    for k in range(K + 1):
        for j in range(K + J + 1):
            for i in range(N + 1):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0 and i < N:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0 and j < K + J:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    # output(dp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    I = 0
    J = 0
    K = 0
    for a in A:
        if a == 1:
            I += 1
        elif a == 2:
            J += 1
        else:
            K += 1

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

    # def output(lst):
    #     for tmp in lst:
    #         print (tmp)

    for k in range(K + 1):
        for j in range(K + J + 1):
            for i in range(N + 1):
                if i == j == k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[k][j][i - 1]
                if j > 0 and i < N:
                    tmp += j * dp[k][j - 1][i + 1]
                if k > 0 and j < K + J:
                    tmp += k * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp / (i + j + k)

    print (dp[K][J][I])

    # output(dp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    I = 0
    J = 0
    K = 0
    for a in A:
        if a == 1:
            I += 1
        elif a == 2:
            J += 1
        else:
            K += 1

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

    # def output(lst):
    #     for tmp in lst:
    #         print (tmp)

    for k in range(K + 1):
        for j in range(K + J + 1):
            for i in range(N + 1):
                if i == j == k == 0:
                    continue
                tmp = N / (i + j + k)
                if i > 0:
                    tmp += i / (i + j + k) * dp[k][j][i - 1]
                if j > 0 and i < N:
                    tmp += j / (i + j + k) * dp[k][j - 1][i + 1]
                if k > 0 and j < K + J:
                    tmp += k / (i + j + k) * dp[k - 1][j + 1][i]
                dp[k][j][i] = tmp

    print (dp[K][J][I])

    # output(dp)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

I = 0
J = 0
K = 0
for a in A:
    if a == 1:
        I += 1
    elif a == 2:
        J += 1
    else:
        K += 1

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

# def output(lst):
#     for tmp in lst:
#         print (tmp)

for k in range(K + 1):
    for j in range(K + J + 1):
        for i in range(N + 1):
            if i == j == k == 0:
                continue
            tmp = N / (i + j + k)
            if i > 0:
                tmp += i / (i + j + k) * dp[k][j][i - 1]
            if j > 0 and i < N:
                tmp += j / (i + j + k) * dp[k][j - 1][i + 1]
            if k > 0 and j < K + J:
                tmp += k / (i + j + k) * dp[k - 1][j + 1][i]
            dp[k][j][i] = tmp

print (dp[K][J][I])

# output(dp)

Submission status: Time Limit Exceeded

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

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

def calc(i, j, k):
    if i < 0 or j < 0 or k < 0:
        return 0
    if dp[k][j][i] != -1:
        return dp[k][j][i]
    if i == j == k == 0:
        dp[i][j][k] = 0
        return 0
    tmp = N / (i + j + k)
    tmp += i / (i + j + k) * calc(i - 1, j, k)
    tmp += j / (i + j + k) * calc(i + 1, j - 1, k)
    tmp += k / (i + j + k) * calc(i, j + 1, k - 1)
    dp[k][j][i] = tmp
    return tmp

i = 0
j = 0
k = 0
for a in A:
    if a == 1:
        i += 1
    elif a == 2:
        j += 1
    else:
        k += 1

# print (i, j , k)
print (calc(i, j , k))

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, DP):
    if DP[a][b][c] > -1: return DP[a][b][c]
    ans = N
    if a > 0: ans += sushi(a-1, b, c, N, DP) * a
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, DP) * b
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, DP) * c
    DP[a][b][c] = ans = ans / (a + b + c)
    return ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    dish = [0, 0, 0]
    for a in list(map(int, input().split())): dish[a-1] += 1
    DP = [[[-1] * (dish[2] + 1) for j in range(dish[1] + dish[2] + 1)] for i in range(N + 1)]
    DP[0][0][0] = 0
    
    print(sushi(dish[0], dish[1], dish[2], N, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, DP):
    if DP[a][b][c] > -1: return DP[a][b][c]
    ans = N
    if a > 0: ans += sushi(a-1, b, c, N, DP) * a
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, DP) * b
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, DP) * c
    DP[a][b][c] = ans / (a + b + c)
    return DP[a][b][c]

def solve():
    input = sys.stdin.readline
    N = int(input())
    dish = [0, 0, 0]
    for a in list(map(int, input().split())): dish[a-1] += 1
    DP = [[[-1 for _ in range(dish[2] + 1)] for j in range(dish[1] + dish[2] + 1)] for i in range(N + 1)]
    DP[0][0][0] = 0
    
    print(sushi(dish[0], dish[1], dish[2], N, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, DP):
    if DP[a][b][c] > -1: return DP[a][b][c]
    ans = N
    if a > 0: ans += sushi(a-1, b, c, N, DP) * a
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, DP) * b
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, DP) * c
    DP[a][b][c] = ans / (a + b + c)
    return DP[a][b][c]

def solve():
    input = sys.stdin.readline
    N = int(input())
    dish = [0, 0, 0]
    for a in list(map(int, input().split())): dish[a-1] += 1
    DP = [[[-1 for _ in range(N + 1)] for j in range(N + 1)] for i in range(N + 1)]
    DP[0][0][0] = 0
    
    print(sushi(dish[0], dish[1], dish[2], N, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, DP):
    if DP[a][b][c] > -1: return DP[a][b][c]
    ans = 1
    finDish = N - (a + b + c)
    if a > 0: ans += sushi(a-1, b, c, N, DP) * (a / N)
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, DP) * (b / N)
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, DP) * (c / N)
    DP[a][b][c] = ans / (1 - (finDish / N))
    return DP[a][b][c]

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    dish = [0, 0, 0]
    for a in A: dish[a-1] += 1
    DP = dict()
    for i in range(N + 1):
        DP[i] = dict()
        for j in range(N + 1):
            DP[i][j] = dict()
            for k in range(N + 1): DP[i][j][k] = -1
    DP[0][0][0] = 0
    
    print(sushi(dish[0], dish[1], dish[2], N, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, DP):
    if DP[a][b][c] > -1: return DP[a][b][c]
    ans = 1
    finDish = N - (a + b + c)
    if a > 0: ans += sushi(a-1, b, c, N, DP) * (a / N)
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, DP) * (b / N)
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, DP) * (c / N)
    ans /= (1 - (finDish / N))
    DP[a][b][c] = ans
    return ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    dish = [0, 0, 0]
    for a in A: dish[a-1] += 1
    DP = dict()
    for i in range(N + 1):
        DP[i] = dict()
        for j in range(N + 1):
            DP[i][j] = dict()
            for k in range(N + 1): DP[i][j][k] = -1
    DP[0][0][0] = 0
    
    print(sushi(dish[0], dish[1], dish[2], N, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

def sushi(a, b, c, N, fin, DP):
    if fin[a][b][c] == 1: return DP[a][b][c]
    ans = 1
    finDish = N - (a + b + c)
    if a > 0: ans += sushi(a-1, b, c, N, fin, DP) * (a / N)
    if b > 0 and a < N: ans += sushi(a+1, b-1, c, N, fin, DP) * (b / N)
    if c > 0 and b < N: ans += sushi(a, b+1, c-1, N, fin, DP) * (c / N)
    ans /= (1 - (finDish / N))
    fin[a][b][c] = 1
    DP[a][b][c] = ans
    return ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    dish = [0, 0, 0]
    for a in A: dish[a-1] += 1
    DP = [[[0 for _ in range(N + 1)] for j in range(N + 1)] for i in range(N + 1)]
    fin = [[[0 for _ in range(N + 1)] for j in range(N + 1)] for i in range(N + 1)]
    fin[0][0][0] = 1
    print(sushi(dish[0], dish[1], dish[2], N, fin, DP))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def sushi(a, b, c, N, memo = dict()):
    try: return memo[(a, b, c)]
    except KeyError:
        ans = 1
        finDish = N - (a + b + c)
        if a > 0: ans += sushi(a-1, b, c, N, memo) * (a / N)
        if b > 0: ans += sushi(a+1, b-1, c, N, memo) * (b / N)
        if c > 0: ans += sushi(a, b+1, c-1, N, memo) * (c / N)
        ans /= (1 - (finDish / N))
        memo[(a, b, c)] = ans
        return ans

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    dish = [0, 0, 0]
    for a in A: dish[a-1] += 1
    memo = dict()
    memo[(0, 0, 0)] = 0
    print(sushi(dish[0], dish[1], dish[2], N, memo))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-0.1] * (n+1) for i in range(n+1)] for i in range(n+1)]

def rec (a,b,c):
  if not (a >= 0 and b >= 0 and c >= 0):
    return 0.0
  if a == b == c == 0:
    return 0.0
  if dp[a][b][c] >= 0.0:
    return dp[a][b][c]
  result = n
  result += rec(a-1,b,c) * a
  result += rec(a+1,b-1,c) * b
  result += rec(a,b+1,c-1) * c
  dp[a][b][c] = result / (a+b+c)
  return dp[a][b][c]

print(rec(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
ABC = A + B + C
dp=[[[-0.1] * (n+1) for i in range(n+1)] for i in range(n+1)]

def rec (a,b,c):
  if not (a >= 0 and b >= 0 and c >= 0):
    return 0
  if a == b == c == 0:
    return 0
  if dp[a][b][c] >= 0.0:
    return dp[a][b][c]
  result = n
  result += rec(a-1,b,c) * a
  result += rec(a+1,b-1,c) * b
  result += rec(a,b+1,c-1) * c
  dp[a][b][c] = result / (a+b+c)
  return dp[a][b][c]

print(rec(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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

for c in range(C+1):
  for b in range(B+C+1-c):
    for a in range(A+B+C+1-c-b):
      if a == b == c == 0:continue
      result = n
      result += (dp[a-1][b][c]*a if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c]*b if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1]*c if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[0] * (302) for i in range(302)] for i in range(302)]

for c in range(C+1):
  for b in range(B+C+1-c):
    for a in range(A+B+C+1-c-b):
      if a == b == c == 0:continue
      result = n
      result += (dp[a-1][b][c]*a if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c]*b if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1]*c if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

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

# def rec (a,b,c):
  # if not (a >= 0 and b >= 0 and c >= 0):
  #   return 0
  # if a == b == c == 0:
  #   return 0
  # if dp[a][b][c] != -1:
  #   return dp[a][b][c]
  # result = n
  # result += rec(a-1,b,c) * a
  # result += rec(a+1,b-1,c) * b
  # result += rec(a,b+1,c-1) * c
  # dp[a][b][c] = result / (a+b+c)
  # return dp[a][b][c]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[0] * (302) for i in range(302)] for i in range(302)]

for c in range(C+1):
  for b in range(B+C+1):
    for a in range(A+B+C+1):
      if a == b == c == 0:continue
      result = n
      result += (dp[a-1][b][c]*a if a-1 >= 0 else 0)
      result += (dp[a+1][b-1][c]*b if b-1 >= 0 else 0)
      result += (dp[a][b+1][c-1]*c if c-1 >= 0 else 0)
      dp[a][b][c]=result / (a+b+c)

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

# def rec (a,b,c):
  # if not (a >= 0 and b >= 0 and c >= 0):
  #   return 0
  # if a == b == c == 0:
  #   return 0
  # if dp[a][b][c] != -1:
  #   return dp[a][b][c]
  # result = n
  # result += rec(a-1,b,c) * a
  # result += rec(a+1,b-1,c) * b
  # result += rec(a,b+1,c-1) * c
  # dp[a][b][c] = result / (a+b+c)
  # return dp[a][b][c]

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
ABC = A + B + C
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]

def rec (a,b,c):
  if not (a >= 0 and b >= 0 and c >= 0):
    return 0
  if a == b == c == 0:
    return 0
  if dp[a][b][c] != -1:
    return dp[a][b][c]
  result = n
  result += rec(a-1,b,c) * a
  result += rec(a+1,b-1,c) * b
  result += rec(a,b+1,c-1) * c
  dp[a][b][c] = result / (a+b+c)
  return dp[a][b][c]

print(rec(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]


def rec (a,b,c):
  if not (a >= 0 and b >= 0 and c >= 0):
    return 0
  if a == b == c == 0:
    return 0
  if dp[a][b][c] != -1:
    return dp[a][b][c]
  result = n
  result += rec(a-1,b,c) * a
  result += rec(a+1,b-1,c) * b
  result += rec(a,b+1,c-1) * c
  dp[a][b][c] = result / (a+b+c)
  return dp[a][b][c]

print(rec(A,B,C))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = map(int, input().split(' '))
dp = {}

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

c = Counter(a)
x = dfs(c[1], c[2], c[3])
print(x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
dp = [[[-1 for _ in range(310)] for _ in range(310)] for _ in range(310)]

def func(i, j, k):
    if dp[i][j][k] >= 0: return dp[i][j][k]
    if i == 0 and j == 0 and k == 0: return 0.0

    res = 0.0
    if i > 0: res += func(i-1, j, k) * i
    if j > 0: res += func(i+1, j-1, k) * j
    if k > 0: res += func(i, j+1, k-1) * k
    res += N
    res *= 1.0 / (i + j + k)

    dp[i][j][k] = res
    return dp[i][j][k]

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

print(func(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
def f(i,j,k):
    return i+j*(N+1)+k*(N+1)**2

N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
    
dp=[0]*(N+1)**3
dp[1]=N
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k<=0 or i+j+k>N:
                continue
            dp[f(i,j,k)]=(i*dp[f(i-1,j,k)]+j*dp[f(i+1,j-1,k)]+k*dp[f(i,j+1,k-1)]+N)/(i+j+k)

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

Submission status: Time Limit Exceeded

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

n = int(input())

dp = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
for d in range(n+1):
  for c in range(n+1-d):
    for b in range(n+1-d-c):
      if b == c == d == 0:
        continue
      dp[b][c][d] = 1
      if b != 0:
        dp[b][c][d] += b/n*dp[b-1][c][d]
      if c != 0:
        dp[b][c][d] += c/n*dp[b+1][c-1][d]
      if d != 0:
        dp[b][c][d] += d/n*dp[b][c+1][d-1]
      dp[b][c][d] /= (b+c+d)
      dp[b][c][d] *= n

L = [0]*3
for a in map(int, input().split()):
  L[a-1] += 1
ans = dp[L[0]][L[1]][L[2]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
INF = 10**9
dp = [[[-1 for k in range(N+1)]for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0.0


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


print(main(A.count(1), A.count(2), A.count(3)))

Submission status: Time Limit Exceeded

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

n = int(input())

dp = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
dp[0][0][0] = 0
for d in range(n+1):
  for c in range(n+1-d):
    for b in range(n+1-d-c):
      if b == c == d == 0:
        continue
      dp[b][c][d] = n
      if b != 0:
        dp[b][c][d] += b*dp[b-1][c][d]
      if c != 0:
        dp[b][c][d] += c*dp[b+1][c-1][d]
      if d != 0:
        dp[b][c][d] += d*dp[b][c+1][d-1]
      dp[b][c][d] /= (b+c+d)

L = [0]*3
for a in map(int, input().split()):
  L[a-1] += 1
ans = dp[L[0]][L[1]][L[2]]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

def main():
  n = int(input())

  D = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
  def dfs(b, c, d):
    if b == c == d == 0:
      return 0
    if D[b][c][d] != -1:
      return D[b][c][d]
    rep = n
    if b != 0:
      rep += b * dfs(b-1, c, d)
    if c != 0:
      rep += c * dfs(b+1, c-1, d)
    if d != 0:
      rep += d * dfs(b, c+1, d-1)
    rep /= (b+c+d)
    D[b][c][d] = rep
    return rep

  L = [0]*3
  for a in map(int, input().split()):
    L[a-1] += 1
  ans = dfs(*L)
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())

D = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
def dfs(b, c, d):
  if b == c == d == 0:
    return 0
  if D[b][c][d] != -1:
    return D[b][c][d]
  rep = n
  if b != 0:
    rep += b * dfs(b-1, c, d)
  if c != 0:
    rep += c * dfs(b+1, c-1, d)
  if d != 0:
    rep += d * dfs(b, c+1, d-1)
  rep /= (b+c+d)
  D[b][c][d] = rep
  return rep

L = [0]*3
for a in map(int, input().split()):
  L[a-1] += 1
ans = dfs(*L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

import sys
sys.setrecursionlimit(10**7)
n = int(input())

D = np.full((n+1, n+1, n+1), -1)
def dfs(a, b, c, d):
  if a == n:
    return 0
  if D[a, b, c] != -1:
    return D[a, b, c]
  rep = n
  if b != 0:
    rep += b * dfs(a+1, b-1, c, d)
  if c != 0:
    rep += c * dfs(a, b+1, c-1, d)
  if d != 0:
    rep += d * dfs(a, b, c+1, d-1)
  rep /= (n-a)
  D[a, b, c] = rep
  return rep

L = [0]*4
for a in map(int, input().split()):
  L[a] += 1
ans = dfs(*L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())

D = dict()
def dfs(a, b, c, d):
  if a == n:
    return 0
  if (a, b, c, d) in D:
    return D[(a, b, c, d)]
  rep = n
  if b != 0:
    rep += b * dfs(a+1, b-1, c, d)
  if c != 0:
    rep += c * dfs(a, b+1, c-1, d)
  if d != 0:
    rep += d * dfs(a, b, c+1, d-1)
  rep /= (n-a)
  D[(a, b, c, d)] = rep
  return rep

L = [0]*4
for a in map(int, input().split()):
  L[a] += 1
ans = dfs(*L)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  a=c1+c2+c3+1
  b=c2+c3+1
  c=c3+1
  
  dp=[[[0]*a for _ in range(b)] for _ in  range(c)]
  
  for i in range(c):
    for j in range(b-i):
      for k in range(a-i-j):
        tmp=i+j+k
        if tmp==0:
          continue
        else:
          dp[i][j][k]=n/tmp
          if i>0:
            dp[i][j][k]+=i*dp[i-1][j+1][k]/tmp
          if j>0:
            dp[i][j][k]+=j*dp[i][j-1][k+1]/tmp
          if k>0:
            dp[i][j][k]+=k*dp[i][j][k-1]/tmp
  print(dp[c3][c2][c1])
             
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  
  def memorize(f):
    table={}
    def func(*args):
        if not args in table:
            table[args]=f(*args)
        return table[args]
    return func

  @memorize
  def sushi(c1,c2,c3):    
      tmp=c1+c2+c3
      if tmp==0:
        return 0
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=True
  
  def memorize(f):
    table={}
    def func(*args):
        if not args in table:
            table[args]=f(*args)
        return table[args]
    return func

  @memorize
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=True
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=True
  
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=True
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  c1,c2,c3=0,0,0
  
  for i in range(n):
    if num[i]==1:
      c1+=1
    elif num[i]==2:
      c2+=1
    else:
      c3+=1
  
  dp=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag=[[[0]*(3*n) for _ in range(3*n)] for _ in  range(3*n)]
  flag[0][0][0]=1
  
  def sushi(c1,c2,c3):    
    if flag[c1][c2][c3]:
      return dp[c1][c2][c3]
    else:
      flag[c1][c2][c3]=1
      tmp=c1+c2+c3
      ans=n/tmp
      if c1>0:
        ans+=c1*sushi(c1-1,c2,c3)/tmp
      if c2>0:
        ans+=c2*sushi(c1+1,c2-1,c3)/tmp
      if c3>0:
        ans+=c3*sushi(c1,c2+1,c3-1)/tmp
      dp[c1][c2][c3]=ans  
      return ans

  #print(dp) 
  print(sushi(c1,c2,c3))      
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
uno = a.count(1)
dos = a.count(2)
tres = n - uno - dos
dp = [[[0]*(n+1) for _ in range(dos+tres+1)] for j in range(tres+1)]
for k in range(tres+1):
  for j in range(dos+tres-k+1):
    for i in range(n+1-j-k):
      if i+j+k == 0: continue
      v = i+j+k
      res = n
      if i: res += i * dp[k][j][i-1]
      if j: res += j * dp[k][j-1][i+1]
      if k: res += k * dp[k-1][j+1][i]
      dp[k][j][i] = res / v
print(dp[tres][dos][uno])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
dic = [None]*(301**3)
dic[0] = 0
def dfs(uno,dos,tres):
  if uno < 0 or dos < 0 or tres < 0:
    return 0
  v = uno + dos*301 + tres*90601
  if dic[v] is not None:
    return dic[v]
  t = uno + dos + tres
  res = n
  res += uno*dfs(uno-1,dos,tres)
  res += dos*dfs(uno+1,dos-1,tres)
  res += tres*dfs(uno,dos+1,tres-1)
  res /= t
  dic[v] = res
  return res
print(dfs(a.count(1),a.count(2),a.count(3)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

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

    ctr = Counter(a)

    def prob(c1, c2, c3):
        if memo[c1][c2][c3] != -1.0:
            return memo[c1][c2][c3]

        ret = n
        if c1 > 0:
            ret += c1 * prob(c1 - 1, c2, c3)
        if c2 > 0:
            ret += c2 * prob(c1 + 1, c2 - 1, c3)
        if c3 > 0:
            ret += c3 * prob(c1, c2 + 1, c3 - 1)
        ret /= c1 + c2 + c3

        memo[c1][c2][c3] = ret
        return ret

    memo = [[[-1.0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]  # 初期値floatにして型変換をさせないようにしてみた
    memo[0][0][0] = 0.0

    ret = prob(*(ctr[k] for k in range(1, 3 + 1)))
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import Counter
    import sys
    sys.setrecursionlimit(10 ** 7)
    readline = sys.stdin.readline

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

    ctr = Counter(a)

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

        ret = n
        if c1 > 0:
            ret += c1 * prob(c1 - 1, c2, c3)
        if c2 > 0:
            ret += c2 * prob(c1 + 1, c2 - 1, c3)
        if c3 > 0:
            ret += c3 * prob(c1, c2 + 1, c3 - 1)
        ret /= c1 + c2 + c3

        memo[c1][c2][c3] = ret
        return ret

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

    ret = prob(*(ctr[k] for k in range(1, 3 + 1)))
    print(ret)


if __name__ == '__main__':
    main()