Problem:


Score : 100 points

Problem Statement

There are N dishes, numbered 1, 2, \ldots, N.
Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.

Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:

Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.

Find the expected number of times the operation is performed before all the pieces of sushi are eaten.

Constraints

All values in input are integers.

1 \leq N \leq 300

1 \leq a_i \leq 3

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the expected number of times the operation is performed before all the pieces of sushi are eaten.
The output is considered correct when the relative difference is not greater than 10^{-9}.

Sample Input 1

3
1 1 1

Sample Output 1

5.5

The expected number of operations before the first piece of sushi is eaten, is 1.
After that, the expected number of operations before the second sushi is eaten, is 1.5.
After that, the expected number of operations before the third sushi is eaten, is 3.
Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5.

Sample Input 2

1
3

Sample Output 2

3

Outputs such as 3.00, 3.000000003 and 2.999999997 will also be accepted.

Sample Input 3

2
1 2

Sample Output 3

4.5

Sample Input 4

10
1 3 2 3 3 2 3 2 1 3

Sample Output 4

54.48064457488221



Sample input:
3
1 1 1


Sample output:
5.5

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
num1, num2, num3 = 0, 0, 0
for a in A:
    if a == 1:
        num1 += 1
    elif a == 2:
        num2 += 1
    else:
        num3 += 1
num2 += num3
num1 += num2
dp = [[[0.0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]
# dp[i][j][k]
# = (i+j+k)**-1 * (i*dp[i-1][j][k] )
for k in range(num3 + 1):
    for j in range(num2 + 1-k):
        for i in range(num1 + 1-k-j):
            if i == 0 and j == 0 and k == 0:
                continue
            dp[i][j][k] = n
            if i - 1 >= 0 and i <= num1:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
num1, num2, num3 = 0, 0, 0
for a in A:
    if a == 1:
        num1 += 1
    elif a == 2:
        num2 += 1
    else:
        num3 += 1
num2 += num3
num1 += num2
dp = [[[0.0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]

for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            dp[i][j][k] = n
            if i - 1 >= 0 and i <= num1:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
num1, num2, num3 = 0, 0, 0
for a in A:
    if a == 1:
        num1 += 1
    elif a == 2:
        num2 += 1
    else:
        num3 += 1
num2 += num3
num1 += num2
dp = [[[0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]
for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            dp[i][j][k] = n
            if i - 1 >= 0 and i <= num1:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

input = sys.stdin.buffer.readline
n = int(input())
A = list(map(int, input().split()))
AC = Counter(A)
num3 = AC[3]
num2 = AC[2] + num3
num1 = AC[1] + num2
dp = [[[0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]
# dp[i][j][k]
# = (i+j+k)**-1 * (i*dp[i-1][j][k] )
for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            dp[i][j][k] = n
            if i - 1 >= 0 and i <= num1:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
AC = Counter(A)
num3 = AC[3]
num2 = AC[2] + num3
num1 = AC[1] + num2
dp = [[[0] * (num3 + 1) for _ in range(num2 + 1)] for _ in range(num1 + 1)]
# dp[i][j][k]
for k in range(num3 + 1):
    for j in range(num2 + 1):
        for i in range(num1 + 1):
            if i == 0 and j == 0 and k == 0:
                continue
            dp[i][j][k] = n
            if i - 1 >= 0 and i <= num1:
                dp[i][j][k] += i * dp[i - 1][j][k]
            if j - 1 >= 0 and i + 1 <= num1:
                dp[i][j][k] += j * dp[i + 1][j - 1][k]
            if j + 1 <= num2 and k - 1 >= 0:
                dp[i][j][k] += k * dp[i][j + 1][k - 1]
            dp[i][j][k] /= i + j + k
print(dp[num1 - num2][num2 - num3][num3])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
ar=list(map(int,input().split()))
dp=[[[0 for i in range(n+2)] for y in range(n+2)] for z in range(n+2)]
c=[0,0,0,0]
for i in ar: c[i]+=1
for k in range(sum(c[3:])+1):
    for j in range(sum(c[2:])+1):
        for i in range(sum(c[1:])+1):
            if i+j+k==0: continue
            if i: dp[i][j][k]+=i*dp[i-1][j][k]
            if j: dp[i][j][k]+=j*dp[i+1][j-1][k]
            if k: dp[i][j][k]+=k*dp[i][j+1][k-1]
            dp[i][j][k]+=n
            dp[i][j][k]/=(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())
C = Counter(map(int, input().split()))
dp = [[[.0] * (N + 2) for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(C[3] + 1):
    for j in range(N - C[1] - i + 1):
        for k in range(N - i - j + 1):
            if i + j + k != 0:
                dp[i][j][k] = (
                    N +
                    i * dp[i - 1][j + 1][k] +
                    j * dp[i][j - 1][k + 1] +
                    k * dp[i][j][k - 1]
                ) / (i + j + k)
print(dp[C[3]][C[2]][C[1]])

Submission status: Time Limit Exceeded

Solution code:

def solve(x, y, z, n, dp):

    if x == 0 and y == 0 and z == 0:
        return 0

    if x < 0 or y < 0 or z < 0:
        return 0

    if (x, y, z) in dp:
        return dp[(x, y, z)]

    exp = n + x * solve(x-1, y, z, n, dp) + y * solve(x + 1, y - 1, z, n, dp) + z * solve(x, y + 1, z - 1, n, dp)
    dp[(x, y, z)] = exp / (x + y + z)
    return dp[(x, y, z)]


n = int(input())
x, y, z = 0, 0, 0

arr = list(map(int, input().split()))

for item in arr:
    if item == 1:
        x += 1

    elif item == 2:
        y += 1

    else:
        z += 1
dp = {}

print(solve(x, y, z, n, dp))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)


@lru_cache(maxsize=None)
def rec(i, j, k):
    if i < 0 or j < 0 or k < 0:
        return 0.0
    if i == 0 and j == 0 and k == 0:
        return 0.0
    global N
    return (rec(i-1, j, k)*i + rec(i+1, j-1, k) * j +
            rec(i, j+1, k-1) * k + N) / (i + j + k)


def main():
    global N
    N = int(input())
    a = map(int, input().split())
    single = double = triple = 0
    for sushi in a:
        if sushi == 1:
            single += 1
        elif sushi == 2:
            double += 1
        elif sushi == 3:
            triple += 1
    print(rec(single, double, triple))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    a = map(int, input().split())
    single = double = triple = 0
    for sushi in a:
        if sushi == 1:
            single += 1
        elif sushi == 2:
            double += 1
        elif sushi == 3:
            triple += 1
    dp = [[[0 for i in range(1+single+double+triple-j-k)]
           for j in range(double + triple + 1 - k)] for k in range(triple + 1)]
    for k in range(triple+1):
        for j in range(double + triple + 1-k):
            for i in range(1+single+double+triple-j-k):
                if i == 0 and j == 0 and k == 0:
                    continue
                first = second = third = 0
                if i-1 >= 0 and j >= 0 and k >= 0:
                    first = dp[k][j][i-1]
                if i+1 >= 0 and j-1 >= 0 and k >= 0:
                    second = dp[k][j - 1][i+1]
                if i >= 0 and j+1 >= 0 and k-1 >= 0:
                    third = dp[k-1][j + 1][i]
                dp[k][j][i] = (first*i + second * j +
                               third * k + N) / (i + j + k)
    print(dp[triple][double][single])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
sys.setrecursionlimit(10 ** 8)
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1

divT = [1/i for i in range(1,n+1)]

from functools import lru_cache### 
@lru_cache(100100100)

def f(x,y,z):
    if x==y==z==n:
        return 0
    res = 0
    delta = n*divT[n-z-1]
    if x != n:
        res += (f(x+1,y,z) + delta) * (n-x)
    if y != x:
        res += (f(x,y+1,z) + delta) * (x-y)#x+1,y+1ではない
    if z != y:
        res += (f(x,y,z+1) + delta)* (y-z)#x+1,y+1,z+1ではない
    res *=divT[n-z-1]
    return res
    

print(f(cnt[1]+cnt[2],cnt[2],0))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1):
        for i in range(lst[0]+lst[1]+lst[2]+1):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(301):
    for j in range(301):
        for i in range(301):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[-1]*310 for i in range(310)] for j in range(310)]

@lru_cache(maxsize=None)
def bfs(one, two, thr):
    if dp[one][two][thr]!=-1:
        return dp[one][two][thr]
    if one==two==thr==0:
        return 0.0
    tmp=1.0
    if one>0:
        tmp+=bfs(one-1,two,thr)*one/n
    if two>0:
        tmp+=bfs(one+1,two-1,thr)*two/n
    if thr>0:
        tmp+=bfs(one,two+1,thr-1)*thr/n
    
    tmp*=n/(one+two+thr)
    dp[one][two][thr]=tmp
    return tmp

print(bfs(lst[0],lst[1],lst[2]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[-1]*310 for i in range(310)] for j in range(310)]

# @lru_cache(maxsize=None)
def bfs(one, two, thr):
    if dp[one][two][thr]!=-1:
        return dp[one][two][thr]
    if one==two==thr==0:
        return 0
    tmp=1
    if one>0:
        tmp+=bfs(one-1,two,thr)*one/n
    if two>0:
        tmp+=bfs(one+1,two-1,thr)*two/n
    if thr>0:
        tmp+=bfs(one,two+1,thr-1)*thr/n
    
    tmp*=n/(one+two+thr)
    dp[one][two][thr]=tmp
    return tmp

print(bfs(lst[0],lst[1],lst[2]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

@lru_cache(maxsize=None)
def bfs(one, two, thr):
    if one==two==thr==0:
        return 0
    tmp=1
    if one>0:
        tmp+=bfs(one-1,two,thr)*one/n
    if two>0:
        tmp+=bfs(one+1,two-1,thr)*two/n
    if thr>0:
        tmp+=bfs(one,two+1,thr-1)*thr/n
    
    return tmp*n/(one+two+thr)

print(bfs(lst[0],lst[1],lst[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(0,N+2,N+2,N+2)
dp[0][0][0] = 0
for  k in range(0,three+1):
    for j in range(0,two+three-k+1):
        for i in range(0,one+two+three-k-j+1):
            if i==j==k==0:
                continue
            zero = N-i-j-k
            p_0 = zero/N
            p_1 = i/N
            p_2 = j/N
            p_3 = k/N
            ret = 1
            if i>0:
                ret += p_1*dp[i-1][j][k]
            if j>0:
                ret += p_2*dp[i+1][j-1][k]
            if k>0:
                ret += p_3*dp[i][j+1][k-1]
            ret /= 1-p_0
            dp[i][j][k] = ret

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(0.0,N+2,N+2,N+2)
dp[0][0][0] = 0
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
            zero = N-i-j-k
            p_0 = zero/N
            p_1 = i/N
            p_2 = j/N
            p_3 = k/N
            ret = 1.0
            if i>0:
                ret += p_1*dp[i-1][j][k]
            if j>0:
                ret += p_2*dp[i+1][j-1][k]
            if k>0:
                ret += p_3*dp[i][j+1][k-1]
            ret /= 1-p_0
            dp[i][j][k] = ret

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(0,N+2,N+2,N+2)
dp[0][0][0] = 0
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
            zero = N-i-j-k
            p_0 = zero/N
            p_1 = i/N
            p_2 = j/N
            p_3 = k/N
            ret = 1
            if i>0:
                ret += p_1*dp[i-1][j][k]
            if j>0:
                ret += p_2*dp[i+1][j-1][k]
            if k>0:
                ret += p_3*dp[i][j+1][k-1]
            ret /= 1-p_0
            dp[i][j][k] = ret

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(-1.0,N+1,N+1,N+1)
dp[0][0][0] = 0
def rec(i,j,k):
    if i<0 or j<0 or k<0:
        return 0
    if dp[i][j][k] != -1.0:
        return dp[i][j][k]
    zero = N-i-j-k
    p_0 = zero/N
    p_1 = i/N
    p_2 = j/N
    p_3 = k/N
    ret = p_1*rec(i-1,j,k) + p_2*rec(i+1,j-1,k) + p_3*rec(i,j+1,k-1) + 1
    ret /= 1-p_0
    dp[i][j][k] = ret
    return ret

print(rec(one,two,three))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(-1,N+1,N+1,N+1)
dp[0][0][0] = 0
def rec(i,j,k):
    if i<0 or j<0 or k<0:
        return 0
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    zero = N-i-j-k
    p_0 = zero/N
    p_1 = i/N
    p_2 = j/N
    p_3 = k/N
    ret = p_1*rec(i-1,j,k) + p_2*rec(i+1,j-1,k) + p_3*rec(i,j+1,k-1) + 1
    ret /= 1-p_0
    dp[i][j][k] = ret
    return ret

print(rec(one,two,three))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
A = LI()
one = 0
two = 0
three = 0
for a in A:
    if a==1:
        one += 1
    elif a==2:
        two += 1
    elif a==3:
        three += 1

dp = FILL3(-1,N+1,N+1,N+1)
def rec(i,j,k):
    if i<0 or j<0 or k<0 or i+j+k==0:
        return 0
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    zero = N-i-j-k
    p_0 = zero/N
    p_1 = i/N
    p_2 = j/N
    p_3 = k/N
    ret = p_1*rec(i-1,j,k) + p_2*rec(i+1,j-1,k) + p_3*rec(i,j+1,k-1) + 1
    ret /= 1-p_0
    dp[i][j][k] = ret
    return ret

print(rec(one,two,three))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1-c):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1):
            for a in range(n-b-c+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
    n=int(input())
    al=tuple(map(int,input().split()))
    arr=[0,0,0]
    for i in al:
        arr[i-1]+=1
    dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
    for c in range(n+1):
        for b in range(n+1):
            for a in range(n+1):
                if a==b==c==0:
                    continue
                if 0<=c-1<=n and 0<=b+1<=n:
                    dp[a][b][c]+=dp[a][b+1][c-1]*c/n
                if 0<=b-1<=n and 0<=a+1<=n:
                    dp[a][b][c]+=dp[a+1][b-1][c]*b/n
                if 0<=a-1<=n:
                    dp[a][b][c]+=dp[a-1][b][c]*a/n
                dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)
    print(dp[arr[0]][arr[1]][arr[2]])
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
al=list(map(int,input().split()))
arr=[0,0,0]
for i in al:
    arr[i-1]+=1
dp=[[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
vis=[[[False for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
#a,b,c=arr
for c in range(n+1):
    for b in range(n+1):
        for a in range(n+1):
            if a==b==c==0:
                continue
            if 0<=c-1<=n and 0<=b+1<=n:
                dp[a][b][c]+=dp[a][b+1][c-1]*c/n
            if 0<=b-1<=n and 0<=a+1<=n:
                dp[a][b][c]+=dp[a+1][b-1][c]*b/n
            if 0<=a-1<=n:
                dp[a][b][c]+=dp[a-1][b][c]*a/n
            dp[a][b][c]=(dp[a][b][c]+1)*n/(a+b+c)

print(dp[arr[0]][arr[1]][arr[2]])