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:
# 入力
N = int(input())
c = [0]*4
for a in input().split():
    c[int(a)] += 1

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]
dp[0][0][0] = 0


for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            temp = N+i*dp[i - 1][j][k]+j * \
                dp[i + 1][j - 1][k]+k*dp[i][j + 1][k - 1]
            dp[i][j][k] = temp / (i + j + k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
# 入力
N = int(input())
c = [0]*4
for a in input().split():
    c[int(a)] += 1

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]
dp[0][0][0] = 0


for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            temp = N
            if i != 0:
                temp += i*dp[i - 1][j][k]
            if j != 0:
                temp += j*dp[i + 1][j - 1][k]
            if k != 0:
                temp += k*dp[i][j + 1][k - 1]
            dp[i][j][k] = temp / (i + j + k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(1000000)


# 入力
N = int(input())
A = [int(x) for x in input().split()]

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]
dp[0][0][0] = 0


c = collections.Counter(A)
# print(c)

for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            temp = N
            if i != 0:
                temp += i*dp[i - 1][j][k]
            if j != 0:
                temp += j*dp[i + 1][j - 1][k]
            if k != 0:
                temp += k*dp[i][j + 1][k - 1]
            dp[i][j][k] = temp / (i + j + k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys
sys.setrecursionlimit(1000000)


# 入力
N = int(input())
A = [int(x) for x in input().split()]

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]


def rec(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 += rec(i-1, j, k)*i
    if j > 0:
        res += rec(i+1, j-1, k)*j
    if k > 0:
        res += rec(i, j+1, k-1)*k
    res += N
    res *= 1.0/(i+j+k)

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

    return res


c = collections.Counter(A)


# 答えを得て出力
print(rec(c[1], c[2], c[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


# 入力
N = int(input())
A = [float(x) for x in input().split()]

# DPテーブルを初期化
dp = [[[-1 for k in range(310)] for j in range(310)] for i in range(310)]


def rec(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 += rec(i-1, j, k)*i
    if j > 0:
        res += rec(i+1, j-1, k)*j
    if k > 0:
        res += rec(i, j+1, k-1)*k
    res += N
    res *= 1.0/(i+j+k)

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

    return res


one, two, three = 0, 0, 0
for a in A:
    if a == 1:
        one += 1
    elif a == 2:
        two += 1
    else:
        three += 1

# 答えを得て出力
print(rec(one, two, three))

Submission status: Time Limit Exceeded

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

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()

# a,b,c = 1個、2個、3個
# S = a + 2b + 3c：total スシ
# S の小さい方から求めていく
# S ごとには、b,c だけ持てば a が分かる

b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = np.ones_like(prev) * N
    dp += prev * a# 1個の皿
    dp[1:] += prev[:-1] * b[1:] # 2個の皿
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:] # 3個の皿
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[0]*(z+2) for i in range(n-x+2)]for i in range(n+2)]
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)/(i+j+k)
print(dp[x][y][z])

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),map(int,input().split());c=[0]*3;l=[1.0/i for i in range(1,n+1)]
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[0]*(z+2) for i in range(n-x+2)]for i in range(n+2)]
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*l[i+j+k-1]
print(dp[x][y][z])

Submission status: Time Limit Exceeded

Solution code:
n=int(input());c=[0]*3;l=[1.0/i for i in range(1,n+1)]
for i in map(int,input().split()):c[i-1]+=1
x,y,z=c;dp=[[[-1]*(z+2) for i in range(n-x+2)]for i in range(n+2)]
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*l[i+j+k-1]
print(dp[x][y][z]+1)

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()));c=[0,0,0];x=[1.0/i for i in range(1,n+1)]
for i in a:c[i-1]+=1
dp=[[[-1]*(c[2]+2) for i in range(c[1]+c[2]+2)]for i in range(n+2)]
for k in range(c[2]+1):
  for j in range(c[2]+c[1]-k+1):
    for i in range(n-k-j+1):
      if i+j+k: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)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());c=[0,0,0];x=[1.0/i for i in range(1,n+1)];dp=[[[-1]*(n+2) for i in range(n+2)]for i in range(n+2)]
for i in list(map(int,input().split())):c[i-1]+=1
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if i+j+k>0:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()));c=[0,0,0];x=[1.0/i for i in range(1,n+1)];dp=[[[-1]*(n+2) for i in range(n+2)]for i in range(n+2)]
for i in a:c[i-1]+=1
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if i+j+k>0:dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]]+1)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if n+1>i+j+k>0:
        dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if not n+1>i+j+k>0:continue
      dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n+1):
    for i in range(n+1):
      if not n+1>i+j+k>0:continue
      dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n+1):
    for i in range(n+1):
      if not n+1>i+j+k>0:continue
      p=n
      if i>0:p+=dp[i-1][j][k]*i
      if j>0:p+=dp[i+1][j-1][k]*j
      if k>0:p+=dp[i][j+1][k-1]*k
      dp[i][j][k]=p*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()))
count=[0]*3
for i in a:count[i-1]+=1
#dp[i][j][k]...寿司が1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の時の期待値
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n+1):
    for i in range(n+1):
      if i+j+k==0:continue
      #競プロフレンズ解説参照
      p=1
      if i>0:p+=dp[i-1][j][k]*(i/n)
      if j>0:p+=dp[i+1][j-1][k]*(j/n)
      if k>0:p+=dp[i][j+1][k-1]*(k/n)
      dp[i][j][k]=p/(1-((n-i-j-k)/n))
print(dp[count[0]][count[1]][count[2]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,a=int(input()),list(map(int,input().split()))
b=[0]*3
for i in a:b[i-1]+=1
dp=[[[0]*(n+1) for i in range(n+1)]for i in range(n+1)]
flag=[[[False]*(n+1) for i in range(n+1)]for i in range(n+1)];flag[0][0][0]=True
def d(a,b,c):
  if flag[a][b][c]:return dp[a][b][c]
  p=1;flag[a][b][c]=True
  if a>0:p+=d(a-1,b,c)*(a/n)
  if b>0:p+=d(a+1,b-1,c)*(b/n)
  if c>0:p+=d(a,b+1,c-1)*(c/n)
  dp[a][b][c]=p/(1-((n-a-b-c)/n))
  return dp[a][b][c]
print(d(b[0],b[1],b[2]))

Submission status: Time Limit Exceeded

Solution code:
n,a=int(input()),list(map(int,input().split()));b=[0]*3;dp=[[[0]*(n+1) for i in range(n+1)]for i in range(n+1)];flag=[[[False]*(n+1) for i in range(n+1)]for i in range(n+1)];flag[0][0][0]=True
for i in a:b[i-1]+=1
def d(a,b,c):
  if flag[a][b][c]:return dp[a][b][c]
  p=1;flag[a][b][c]=True
  if a>0:p+=d(a-1,b,c)*(a/n)
  if b>0:p+=d(a+1,b-1,c)*(b/n)
  if c>0:p+=d(a,b+1,c-1)*(c/n)
  dp[a][b][c]=p/(1-((n-a-b-c)/n));return dp[a][b][c]
print(d(b[0],b[1],b[2]))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    count_1 = a.count(1)
    count_2 = a.count(2)
    count_3 = a.count(3)

    # dp[count_1][count_2][count_3] = expectation of attempts for all dishes are cleared
    expectation_of_attempts = [[[0.0 for num_dishes_3 in range(n + 1)] for num_dishes_2 in range(n + 1)] for num_dishes_1 in range(n + 1)]

    recursive_call(n, count_1, count_2, count_3, expectation_of_attempts)
    return expectation_of_attempts[count_1][count_2][count_3]


def recursive_call(n, i, j, k, expectation_of_attempts):
    if i == 0 and j == 0 and k == 0:
        return 0.0
    if expectation_of_attempts[i][j][k] > 0.0:
        return expectation_of_attempts[i][j][k]
    a = 0.0 if i == 0 else recursive_call(n, i - 1, j, k, expectation_of_attempts)
    b = 0.0 if j == 0 else recursive_call(n, i + 1, j - 1, k, expectation_of_attempts)
    c = 0.0 if k == 0 else recursive_call(n, i, j + 1, k - 1, expectation_of_attempts)

    expectation_of_attempts[i][j][k] = (i * a + j * b + k * c + n) / (i + j + k)
    return expectation_of_attempts[i][j][k]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

l=[1]
for i in range(1,1000):
    l.append(1.0/i)
for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            if i==j==k==0:
                continue
            res=n
            if i>0:
                res+=dp[i-1][j][k]*i
            if j>0:
                res+=dp[i+1][j-1][k]*j
            if k>0:
                res+=dp[i][j+1][k-1]*k
            res*=l[i+j+k]
            dp[i][j][k]=res

print(dp[p][q][r])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

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

l=[1]
for i in range(1,1000):
    l.append(1.0/i)
for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            f(i,j,k)
print(dp[p][q][r])

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

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

for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            f(i,j,k)
print(dp[p][q][r])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)

num = max(one,two,three)

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

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

print(dp[one][two][three]+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

import functools
@functools.lru_cache(maxsize=None)
def tami(i,j,k):
  if (dp[i][j][k] >= 0):
    return dp[i][j][k]
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += tami(i-1, j, k) * i
    if (j > 0):
      res += tami(i+1, j-1, k) * j
    if (k > 0):
      res += tami(i, j+1, k-1) * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)
num = max(one,two,three)

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

print(tami(one,two,three))

Submission status: Time Limit Exceeded

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)

Submission status: Time Limit Exceeded

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t, -1, -1):
    for k in range(N, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)

Submission status: Time Limit Exceeded

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

M = t * 2 + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t, -1, -1):
    for k in range(M, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def tami(i,j,k):
  if (dp[i][j][k] >= 0):
    return dp[i][j][k]
  if (i == j == k == 0):
    return 0
  else:
    res = 0
    if (i > 0):
      res += tami(i-1, j, k) * i
    if (j > 0):
      res += tami(i+1, j-1, k) * j
    if (k > 0):
      res += tami(i, j+1, k-1) * k
    res += N
    res *= (1 / (i + j + k))
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

one = a.count(1)
two = a.count(2)
three = a.count(3)
num = max(one,two,three)

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

print(tami(one,two,three))

Submission status: Time Limit Exceeded

Solution code:
dp = [[[0.0 for i in range(303)]for j in range(303)] for k in range(303)]
a1 = [0 for i in range(4)]
n = int(input())
for i in input().split():
	a1[int(i)] += 1
dp[a1[1]][a1[2]][a1[3]] = 1
ans = 0.0
for c in range(n,-1,-1):
	for b in range(n,-1,-1):
		for a in range(n,-1,-1):
			tot = (a+b+c)
			if(tot == 0):
				continue
			mis = (n-(tot))/n
			waste = mis/(1-mis)
			ans += dp[a][b][c] * waste
			if(a>=1):
				dp[a-1][b][c] += a/(tot) * dp[a][b][c]
			if(b>=1):
				dp[a+1][b-1][c] += b/(tot) * dp[a][b][c]
			if(c>=1):
				dp[a][b+1][c-1] += c/(tot) * dp[a][b][c] 
print(ans+a1[1]+2*a1[2]+3*a1[3])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
Nd = float(N)
N_inv = 1/N
INIT = {1:0,2:0,3:0}
for i in LI():
    INIT[i] += 1

DP=[[[-1.0]*(N+2) for i in range(N+2)] for j in range(N+2)]
def solve(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 += solve(i-1, j, k) * i
    if j > 0: res += solve(i+1, j-1, k) * j
    if k > 0: res += solve(i, j+1, k-1) * k
    res += Nd
    res *= 1.0 / (i + j + k)
    DP[i][j][k] = res
    return res

print(solve(INIT[1],INIT[2],INIT[3]))

Submission status: Time Limit Exceeded

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

# dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
# def dfs(n1, n2, n3):
#     if n1 == 1 and n2 == n3 == 0:
#         return n
#
#     if dp[n1][n2][n3] is not None:
#         return dp[n1][n2][n3]
#
#     r = (
#         (n1 > 0 and dfs(n1 - 1, n2, n3) * n1) +
#         (n2 > 0 and dfs(n1 + 1, n2 - 1, n3) * n2) +
#         (n3 > 0 and dfs(n1, n2 + 1, n3 - 1) * n3)
#     ) + n
#     r /= n1 + n2 + n3
#     dp[n1][n2][n3] = r
#     return r

from collections import Counter
cnt = Counter(a)
# print(dfs(*(cnt.get(i, 0) for i in range(1, 3 + 1))))

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for k in range(0, n + 1):
    for j in range(0, n + 1 - k):
        for i in range(0, n + 1 - k - j):
            if i == j == k == 0:
                continue
            dp[i][j][k] = (n
                 + (i > 0 and dp[i - 1][j][k] * i)
                 + (j > 0 and dp[i + 1][j - 1][k] * j)
                 + (k > 0 and dp[i][j + 1][k - 1] * k)
                 ) / (i + j + k)

i, j, k = (cnt.get(i, 0) for i in range(1, 3 + 1))
print(dp[i][j][k])

Submission status: Time Limit Exceeded

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

# dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
# def dfs(n1, n2, n3):
#     if n1 == 1 and n2 == n3 == 0:
#         return n
#
#     if dp[n1][n2][n3] is not None:
#         return dp[n1][n2][n3]
#
#     r = (
#         (n1 > 0 and dfs(n1 - 1, n2, n3) * n1) +
#         (n2 > 0 and dfs(n1 + 1, n2 - 1, n3) * n2) +
#         (n3 > 0 and dfs(n1, n2 + 1, n3 - 1) * n3)
#     ) + n
#     r /= n1 + n2 + n3
#     dp[n1][n2][n3] = r
#     return r

from collections import Counter
cnt = Counter(a)
# print(dfs(*(cnt.get(i, 0) for i in range(1, 3 + 1))))

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for k in range(0, n + 1):
    for j in range(0, n + 1):
        for i in range(0, n + 1):
            if i == j == k == 0:
                continue
            if i + j + k > n:
                continue
            r = n
            if i > 0:
                r += dp[i - 1][j][k] * i
            if j > 0:
                r += dp[i + 1][j - 1][k] * j
            if k > 0:
                r += dp[i][j + 1][k - 1] * k
            dp[i][j][k] = r / (i + j + k)

i, j, k = (cnt.get(i, 0) for i in range(1, 3 + 1))
print(dp[i][j][k])

Submission status: Time Limit Exceeded

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

dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
def dfs(n1, n2, n3):
    if n1 == 1 and n2 == n3 == 0:
        return n

    if dp[n1][n2][n3] is not None:
        return dp[n1][n2][n3]

    r = (
        (n1 > 0 and dfs(n1 - 1, n2, n3) * n1) +
        (n2 > 0 and dfs(n1 + 1, n2 - 1, n3) * n2) +
        (n3 > 0 and dfs(n1, n2 + 1, n3 - 1) * n3)
    ) + n
    r /= n1 + n2 + n3
    dp[n1][n2][n3] = r
    return r

from collections import Counter
cnt = Counter(a)
print(dfs(*(cnt.get(i, 0) for i in range(1, 3 + 1))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
N_inv = 1/N
INIT = {1:0,2:0,3:0}
for i in LI():
    INIT[i] += 1

DP=[[[[0.0]*(N+2) for i in range(N+2)] for j in range(N+2)] for l in range(2)]
DP[0][INIT[1]][INIT[2]][INIT[3]]=1

cnt=1
mean = 0
# print(DP[0])
for l in range(1, 50*N):
    DP[(l-1)%2][0][0][0] = 0.0
    for i in range(N+1):
        for j in range(N+1):
            for k in range(N+1):
                DP[l%2][i][j][k] = \
                    DP[(l-1)%2][i][j][k]*(N-i-j-k)+ \
                    DP[(l-1)%2][i+1][j][k]*(i+1) + \
                    DP[(l-1)%2][i-1][j+1][k]*(j+1) + \
                    DP[(l-1)%2][i][j-1][k+1]*(k+1)

                DP[l%2][i][j][k] = DP[l%2][i][j][k]*N_inv
    # print(DP[l])
    mean += DP[l%2][0][0][0]*cnt
    cnt+=1
print(mean)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
N_inv = 1/N
INIT = {1:0,2:0,3:0}
for i in LI():
    INIT[i] += 1

DP=[[[[0]*(N+2) for i in range(N+2)] for j in range(N+2)] for l in range(2)]
DP[0][INIT[1]][INIT[2]][INIT[3]]=1

cnt=1
mean = 0
# print(DP[0])
for l in range(1, 50*N):
    DP[(l-1)%2][0][0][0] = 0
    for i in range(N+1):
        for j in range(N+1):
            for k in range(N+1):
                DP[l%2][i][j][k] = \
                    DP[(l-1)%2][i][j][k]*(N-i-j-k)+ \
                    DP[(l-1)%2][i+1][j][k]*(i+1) + \
                    DP[(l-1)%2][i-1][j+1][k]*(j+1) + \
                    DP[(l-1)%2][i][j-1][k+1]*(k+1)

                DP[l%2][i][j][k] = DP[l%2][i][j][k]*N_inv
    # print(DP[l])
    mean += DP[l%2][0][0][0]*cnt
    cnt+=1
print(mean)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N=II()
N_inv = 1/N
INIT = {1:0,2:0,3:0}
for i in LI():
    INIT[i] += 1

DP=[[[[0]*(N+2) for i in range(N+2)] for j in range(N+2)] for l in range(50*N)]
DP[0][INIT[1]][INIT[2]][INIT[3]]=1

cnt=1
mean = 0
dm = 1
# print(DP[0])
for l in range(1, 50*N):
    DP[l-1][0][0][0] = 0
    for i in range(N+1):
        for j in range(N+1):
            for k in range(N+1):
                DP[l][i][j][k] = \
                    DP[l-1][i][j][k]*(N-i-j-k)+ \
                    DP[l-1][i+1][j][k]*(i+1) + \
                    DP[l-1][i-1][j+1][k]*(j+1) + \
                    DP[l-1][i][j-1][k+1]*(k+1)

                DP[l][i][j][k] = DP[l][i][j][k]*N_inv
                # print("{}".format(DP[i][j][k]))
    # print(DP[l])
    dm = DP[l][0][0][0]*cnt
    mean += dm
    cnt+=1
print(mean)

Submission status: Time Limit Exceeded

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

#実家DPと気合い遷移式

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()