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
sys.setrecursionlimit(10**8)
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def rec(i, j, k):
    global dp
    if dp[i][j][k] != -1.0:
        return dp[i][j][k]
    if i+j+k == 0:
        return 0.0

    num = i+j+k
    ans = N_f / num
    if i > 0:
        ans += (rec(i-1, j, k) * i) / num
    if j > 0:
        ans += (rec(i+1, j-1, k) * j) / num
    if k > 0:
        ans += (rec(i, j+1, k-1) * k) / num
    dp[i][j][k] = ans
    return ans

N = ii()
N_f = float(N)
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1

dp = dp3(-1.0, cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp[0][0][0] = 0

print(rec(cnt[0], cnt[1], cnt[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def rec(i, j, k):
    global dp
    if dp[i][j][k] < float("inf"):
        return dp[i][j][k]
    if i+j+k == 0:
        return 0

    num = float(i+j+k)
    ans = float(N) / num
    if i > 0:
        ans += (rec(i-1, j, k) * i) / num
    if j > 0:
        ans += (rec(i+1, j-1, k) * j) / num
    if k > 0:
        ans += (rec(i, j+1, k-1) * k) / num
    dp[i][j][k] = ans
    return ans

N = ii()
A = li()

cnt = [0, 0, 0]
for a in A:
    cnt[a-1] += 1

dp = dp3(float("inf"), cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
dp[0][0][0] = 0

print(rec(cnt[0], cnt[1], cnt[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): 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)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def rec(i, j, k):
    global dp
    #print(i, j, k)
    if dp[i][j][k] < float("inf"):
        return dp[i][j][k]
    if i+j+k == 0:
        return 0

    num = float(i+j+k)
    ans = float(N) / num
    if i > 0:
        ans += (rec(i-1, j, k) * i) / num
    if j > 0:
        ans += (rec(i+1, j-1, k) * j) / num
    if k > 0:
        ans += (rec(i, j+1, k-1) * k) / num
    dp[i][j][k] = ans
    return ans

N = ii()
A = li()

dp = dp3(float("inf"), N+1, N+1, N+1)
dp[0][0][0] = 0
cnt = [0, 0, 0]

for a in A:
    cnt[a-1] += 1

print(rec(cnt[0], cnt[1], cnt[2]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = [0] * ((n+2)*(z+y+2)*(z+2))


def get(i, j, k):
    return ta[(i * (z + y + 2) + j) * (z + 2) + k]


for k in range(z + 1):
    for j in range(z+y + 1):
        for i in range(n + 1):
            if i == j == k == 0:
                continue
            ans = n
            if i > 0:
                ans += i * get(i - 1, j, k)
            if j > 0:
                ans += j * get(i + 1, j - 1, k)
            if k > 0:
                ans += k * get(i, j + 1, k - 1)
            ta[(i * (z + y + 2) + j) * (z + 2) + k] = ans / (i + j + k)


print(get(x, y, z))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = [[[0]*(z+2) for i in range(z+y+2)]for j in range(n+2)]


for k in range(z + 1):
    for j in range(z+y + 1):
        for i in range(n + 1):
            if i == j == k == 0:
                continue
            ans = n
            if i > 0:
                ans += i*ta[i - 1][j][k]
            if j > 0:
                ans += j*ta[i + 1][j - 1][k]
            if k > 0:
                ans += k * ta[i][j + 1][k - 1]
            ta[i][j][k] = ans/(i+j+k)


print(ta[x][y][z])

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = np.zeros((n+2, z+y+2, z+2))


for k in range(z + 1):
    for j in range(z+y + 1):
        for i in range(n + 1):
            if i == j == k == 0:
                continue
            ans = n
            if i > 0:
                ans += i*ta[i - 1][j][k]
            if j > 0:
                ans += j*ta[i + 1][j - 1][k]
            if k > 0:
                ans += k * ta[i][j + 1][k - 1]
            ta[i][j][k] = ans/(i+j+k)


print(ta[x][y][z])

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = [[[0]*(z+2) for i in range(z+y+3)]for j in range(n+2)]


for k in range(z + 1):
    for j in range(z+y + 1):
        for i in range(n + 1):
            if i == j == k == 0:
                continue
            ans = n
            if i > 0:
                ans += i*ta[i - 1][j][k]
            if j > 0:
                ans += j*ta[i + 1][j - 1][k]
            if k > 0:
                ans += k * ta[i][j + 1][k - 1]
            ta[i][j][k] = ans/(i+j+k)


print(ta[x][y][z])

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = [[[0]*310 for i in range(310)]for j in range(310)]


for k in range(z + 1):
    for j in range(z+y + 1):
        for i in range(n + 1):
            if i == j == k == 0:
                continue
            ans = n
            if i > 0:
                ans += i*ta[i - 1][j][k]
            if j > 0:
                ans += j*ta[i + 1][j - 1][k]
            if k > 0:
                ans += k * ta[i][j + 1][k - 1]
            ta[i][j][k] = ans/(i+j+k)


print(ta[x][y][z])

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int, input().split())
x = y = z = 0
for i in a:
    if i == 1:
        x += 1
    elif i == 2:
        y += 1
    else:
        z += 1

ta = [[[-1]*(z+1) for i in range(n+1)]for j in range(n+1)]


def d(i, j, k):
    if ta[i][j][k] != -1:
        return ta[i][j][k]
    if i+j+k == 0:
        return 0
    ans = n
    if i != 0:
        ans += i*d(i-1, j, k)
    if j != 0:
        ans += j*d(i+1, j-1, k)
    if k != 0:
        ans += k*d(i, j+1, k-1)
    ans /= i+j+k
    ta[i][j][k] = ans
    return ans


print(d(x, y, z))

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int,input().split())
x=y=z=0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    else:
        z+=1

ta = [[[-1]*302 for i in range(302)]for j in range(302)]
def d(i,j,k):
    if ta[i][j][k] !=-1:
        return ta[i][j][k]
    if i+j+k==0:
        return 0
    ans = n
    if i!=0:
        ans += i*d(i-1,j,k)
    if j!=0:
        ans += j*d(i+1,j-1,k)
    if k!=0:
        ans += k*d(i,j+1,k-1)
    ans /= i+j+k
    ta[i][j][k] = ans
    return ans
print(d(x,y,z))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))
c1 = 0
c2 = 0 
c3 = 0
for i in range(N):
    if a[i] == 1:
        c1 += 1
    if a[i] == 2:
        c2 += 1
    if a[i] == 3:
        c3 += 1
dp= [[[-1] * (N+1) for i in range(N+1)] for j in range(N+1)]
dp[c1][c2][c3] = 0
def solve(c1, c2, c3):
    if dp[c1][c2][c3] > 0:
        return dp[c1][c2][c3]
    if c1 == c2 == c3 == 0:
        return 0
    res = 1/(1-(N-c1-c2-c3)/N)
    if c1 > 0:
        res += solve(c1-1,c2,c3)*(c1/N)/(1-(N-c1-c2-c3)/N)
    if c2 > 0:
        res += solve(c1+1,c2-1,c3)*(c2/N)/(1-(N-c1-c2-c3)/N)
    if c3 > 0:
        res += solve(c1,c2+1,c3-1)*(c3/N)/(1-(N-c1-c2-c3)/N)
    dp[c1][c2][c3] = res
    return dp[c1][c2][c3]
print(solve(c1, c2, c3))

Submission status: Time Limit Exceeded

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

n = int(input())
a = map(int,input().split())
x=y=z=0
for i in a:
    if i==1:
        x+=1
    elif i==2:
        y+=1
    else:
        z+=1

ta = [[[-1]*302 for i in range(302)]for j in range(302)]
def d(i,j,k):
    if ta[i][j][k] !=-1:
        return ta[i][j][k]
    if i+j+k==0:
        return 0
    ans = n
    if i!=0:
        ans += i*d(i-1,j,k)
    if j!=0:
        ans += j*d(i+1,j-1,k)
    if k!=0:
        ans += k*d(i,j+1,k-1)
    ans /= i+j+k
    ta[i][j][k] = ans
    return ans
print(d(x,y,z))

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

# 再起回数上限変更
sys.setrecursionlimit(1000000)

N = int(input())
A = [int(i) for i in input().split()]
c = collections.Counter(A)
I, J, K = c[1], c[2], c[3]

L = I+J+K
M = J+K

dp = [[[-1]*(K+1) for i in range(M+1)] for i in range(L+1)]
dp[0][0][0] = 0


def calc(i, j, k):
    global dp

    if dp[i][j][k] > -1:
        return dp[i][j][k]

    ret = N / (i + j + k)

    if i > 0:
        ret += calc(i - 1, j, k) * (i / (i + j + k))

    if j > 0:
        ret += calc(i + 1, j - 1, k) * (j / (i + j + k))

    if k > 0:
        ret += calc(i, j + 1, k - 1) * (k / (i + j + k))

    dp[i][j][k] = ret

    return ret


ret = calc(I, J, K)
print(ret)

Submission status: Time Limit Exceeded

Solution code:
N = 305
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
c = Counter(a)

memo = [[[-1]*N for _ in range(N)] for __ in range(N)]
memo[0][0][0] = 0

def dp(a,b,c):
    if memo[a][b][c]>-0.5:
        return memo[a][b][c]

    z = n - (a+b+c)
    nz = n-z
    aux1, aux2, aux3 = 0, 0, 0
    if a:
        aux1 = a/(a+b+c)*dp(a - 1, b, c)
    if b:
        aux2 = b/(a+b+c)*dp(a + 1, b-1, c)
    if c:
        aux3 = c/(a+b+c)*dp(a, b+1, c-1)


    ans = nz/n*(aux1+aux2+aux3+1) + z/n
    ans *= n/nz
    memo[a][b][c] = ans
    return ans



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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
c = Counter(a)

memo = {(0,0,0): 0}

def dp(state):
    if state in memo:
        return memo[state]

    z = n - sum(state)
    nz = n-z
    aux1, aux2, aux3 = 0, 0, 0
    a,b,c = state
    if a:
        aux1 = a/(a+b+c)*dp((a - 1, state[1], state[2]))
    if b:
        aux2 = b/(a+b+c)*dp((a + 1, b-1, c))
    if c:
        aux3 = c/(a+b+c)*dp((a, b+1, c-1))


    ans = nz/n*(aux1+aux2+aux3+1) + z/n
    ans *= n/nz
    memo[state] = ans
    return ans



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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
memo = {}

for i in range(n):
    memo[tuple([0]*(n-1) + [1])] = n

def dp(state):
    if state in memo:
        return memo[state]
    l = list(state)
    ans = 0
    nc = 0
    for i in range(n):
        if l[i]:
            nc += 1
            l[i] -= 1
            ans += (1 + dp(tuple(sorted(l)))) / n
            l[i] += 1
    if nc == n:
        x = ans
    else:
        x = ans + (n - nc) / n
        x *= n/nc
    memo[state] = x
    return x

dp(tuple(a))
print(memo[tuple(a)])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
memo = {}

for i in range(n):
    memo[tuple([0]*(n-1) + [1])] = n

def dp(state):
    if state in memo:
        return memo[state]
    l = list(state)
    ans = 0
    nc = 0
    for i in range(n):
        if l[i]:
            nc += 1
            ll = l[:]
            ll[i] -= 1
            ll.sort()            
            ans += (1+dp(tuple(ll)))/n
    if nc == n:
        x = ans
    else:
        x = ans + (n - nc) / n
        x *= n/nc
    memo[state] = x
    return x

dp(tuple(a))
print(memo[tuple(a)])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(x) for x in input().split()]

memo = {}

for i in range(n):
    memo[tuple([0] * i + [1] + [0] * (n - 1 - i))] = n

def dp(state):
    if state in memo:
        return memo[state]
    l = list(state)
    ans = 0
    nc = 0
    for i in range(n):
        if l[i]:
            nc += 1
            l[i]-=1
            ans += (1+dp(tuple(l)))/n
            l[i] += 1
    if nc == n:
        x = ans
    else:
        x = ans + (n - nc) / n
        x *= n/nc

    memo[state] = x
    return x
        
dp(tuple(a))
print(memo[tuple(a)])

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()))
table = [0] * 4
for x in a: table[x] += 1

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

def dfs(x, y, z):
  global dp
  if dp[x][y][z]: return dp[x][y][z]
  res = 0
  if x: res += dfs(x - 1, y, z) * x / (x + y + z)
  if y: res += dfs(x + 1, y - 1, z) * y / (x + y + z)
  if z: res += dfs(x, y + 1, z - 1) * z / (x + y + z)
  if (x + y + z): res += N / (x + y + z)
  dp[x][y][z] = res
  return res
print(dfs(table[1], table[2], table[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

start_plate = [0] * 3
for n in range(N):
    if A[n] > 0:
        start_plate[A[n] - 1] += 1

max_N = 301
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if i1 == 0 and i2 == 0 and i3 == 0:
        return 0
    else:
        i_sum = i1 + i2 + i3
        tmp = N
        if i3-1 >= 0:
            if memo[i1][i2+1][i3-1] == 0:
                tmp += dp(i1, i2 + 1, i3 - 1) * i3
            else:
                tmp += memo[i1][i2+1][i3-1]*i3
        if i2-1 >= 0:
            if memo[i1+1][i2-1][i3] == 0:
                tmp += dp(i1 + 1, i2 - 1, i3) * i2
            else:
                tmp += memo[i1+1][i2-1][i3]*i2
        if i1-1 >= 0:
            if memo[i1-1][i2][i3] == 0:
                tmp += dp(i1 - 1, i2, i3) * i1
            else:
                tmp += memo[i1-1][i2][i3]*i1
        tmp /= i_sum
        memo[i1][i2][i3] = tmp
        return tmp


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

start_plate = [0] * 3
for n in range(N):
    if A[n] > 0:
        start_plate[A[n] - 1] += 1

max_N = 301
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if memo[i1][i2][i3] != 0:
        return memo[i1][i2][i3]
    elif i1 == 0 and i2 == 0 and i3 == 0:
        return 0
    else:
        i_sum = i1 + i2 + i3
        tmp = N
        if i3-1 >= 0:
            tmp += dp(i1, i2 + 1, i3 - 1) * i3
        if i2-1 >= 0:
            tmp += dp(i1 + 1, i2 - 1, i3) * i2
        if i1-1 >= 0:
            tmp += dp(i1 - 1, i2, i3) * i1
        tmp /= i_sum
        memo[i1][i2][i3] = tmp
        return tmp


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

start_plate = [0] * 3
for n in range(N):
    if A[n] > 0:
        start_plate[A[n] - 1] += 1

max_N = 301
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]


def dp(i1, i2, i3):
    if memo[i1][i2][i3] != 0:
        return memo[i1][i2][i3]
    elif i1 == 0 and i2 == 0 and i3 == 0:
        return 0
    else:
        i_sum = i1 + i2 + i3
        tmp = N / i_sum
        if i3-1 >= 0:
            tmp += dp(i1, i2 + 1, i3 - 1) * (i3 / i_sum)
        if i2-1 >= 0:
            tmp += dp(i1 + 1, i2 - 1, i3) * (i2 / i_sum)
        if i1-1 >= 0:
            tmp += dp(i1 - 1, i2, i3) * (i1 / i_sum)
        memo[i1][i2][i3] = tmp
        return tmp


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
 
N = int(input())
A = list(map(int, input().split()))
 
start_plate = [0] * 3
for n in range(N):
    if A[n] > 0:
        start_plate[A[n] - 1] += 1
 
max_N = 301
dp_calculated = [[[False] * max_N for _ in range(max_N)] for __ in range(max_N)]
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]
dp_calculated[0][0][0] = True
 
def dp(i1, i2, i3):
    if dp_calculated[i1][i2][i3]:
        return memo[i1][i2][i3]
    else:
        memo[i1][i2][i3] = N / (i1 + i2 + i3)
        if i3-1 >= 0:
            memo[i1][i2][i3] += dp(i1, i2 + 1, i3 - 1) * (i3 / (i1 + i2 + i3))
        if i2-1 >= 0:
            memo[i1][i2][i3] += dp(i1 + 1, i2 - 1, i3) * (i2 / (i1 + i2 + i3))
        if i1-1 >= 0:
            memo[i1][i2][i3] += dp(i1 - 1, i2, i3) * (i1 / (i1 + i2 + i3))
        dp_calculated[i1][i2][i3] = True
        return memo[i1][i2][i3]
 
 
print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

start_plate = [0] * 3
for n in range(N):
    if A[n] > 0:
        start_plate[A[n] - 1] += 1

max_N = 301
dp_calculated = [[[False] * max_N for _ in range(max_N)] for __ in range(max_N)]
memo = [[[0] * max_N for _ in range(max_N)] for __ in range(max_N)]
dp_calculated[0][0][0] = True

def dp(i1, i2, i3):
    if dp_calculated[i1][i2][i3]:
        return memo[i1][i2][i3]
    else:
        memo[i1][i2][i3] = N / (i1 + i2 + i3)
        if i3-1 >= 0:
            memo[i1][i2][i3] += dp(i1, i2 + 1, i3 - 1) * (i3 / (i1 + i2 + i3))
        if i2-1 >= 0:
            memo[i1][i2][i3] += dp(i1 + 1, i2 - 1, i3) * (i2 / (i1 + i2 + i3))
        if i1-1 >= 0:
            memo[i1][i2][i3] += dp(i1 - 1, i2, i3) * (i1 / (i1 + i2 + i3))
        dp_calculated[i1][i2][i3] = True
        return memo[i1][i2][i3]


print(dp(start_plate[0], start_plate[1], start_plate[2]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

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

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c3+1):
        for j in range(c3+c2-k+1):
            for i in range(N-j-k+1):
                if i == j == k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    from collections import Counter
    import sys
    input = sys.stdin.buffer.readline

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

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

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c3+1):
        for j in range(c3+c2-k+1):
            for i in range(N-j-k+1):
                if i == j == k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c3+1):
        for j in range(c3+c2-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

    c = [0]*4
    for aa in a:
        c[aa] += 1

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

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
a = list(map(float, input().split()))

dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
for k in range(c3+1):
    for j in range(c3+c2-k+1):
        for i in range(N-j-k+1):
            if i+j+k == 0:
                continue
            else:
                tmp = N
                if i > 0: # IndexError防止
                    tmp += dp[i-1][j][k]*i
                if j > 0:
                    tmp += dp[i+1][j-1][k]*j
                if k > 0:
                    tmp += dp[i][j+1][k-1]*k
                dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

print(dp[c1][c2][c3])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
a = list(map(float, input().split()))

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

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
for k in range(c[3]+1):
    for j in range(c[3]+c[2]-k+1):
        for i in range(N-j-k+1):
            if i+j+k == 0:
                continue
            else:
                tmp = N
                if i > 0: # IndexError防止
                    tmp += dp[i-1][j][k]*i
                if j > 0:
                    tmp += dp[i+1][j-1][k]*j
                if k > 0:
                    tmp += dp[i][j+1][k-1]*k
                dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

N = int(input())
a = list(map(float, input().split()))

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

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
for k in range(c[3]+1):
    for j in range(c[3]+c[2]-k+1):
        for i in range(N-j-k+1):
            if i+j+k == 0:
                continue
            else:
                tmp = N/(i+j+k)
                if i > 0: # IndexError防止
                    tmp += dp[i-1][j][k]*(i/(i+j+k))
                if j > 0:
                    tmp += dp[i+1][j-1][k]*(j/(i+j+k))
                if k > 0:
                    tmp += dp[i][j+1][k-1]*(k/(i+j+k))
                dp[i][j][k] = tmp

print(dp[c[1]][c[2]][c[3]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

from collections import Counter

N = int(input())
a = list(map(float, input().split()))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

from collections import Counter

N = int(input())
a = list(map(float, input().split()))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

a_cnt = Counter(a)
num_1 = a_cnt[1]
num_2 = a_cnt[2]
num_3 = a_cnt[3]

dp = [[[0]*(302) for _ in range(302)] for _ in range(302)]

@lru_cache(maxsize=None)
def rec(i, j, k):
	if i==0 and j==0 and k==0: return 0.0
	if dp[i][j][k]: return dp[i][j][k]

	res = 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 /= (i+j+k)
	dp[i][j][k] = res
	return res

print(rec(num_1, num_2, num_3))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
a = LIST()

a_cnt = Counter(a)
num_1 = a_cnt[1]
num_2 = a_cnt[2]
num_3 = a_cnt[3]

dp = [[[0]*(302) for _ in range(302)] for _ in range(302)]

@lru_cache(maxsize=None)
def rec(i, j, k):
	if i==0 and j==0 and k==0: return 0.0

	res = 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 /= (i+j+k)
	dp[i][j][k] = res
	return res

print(rec(num_1, num_2, num_3))

Submission status: Time Limit Exceeded

Solution code:

n = int(input())
l1 = l2 = l3 = 0
l = [int(i) for i in input().split()]
for i in l:
    if i == 1:
        l1 += 1
    elif i == 2:
        l2 += 1
    else:
        l3 += 1
a = l2+l3
dp = [[[0]*(l3+1) for i in range(a+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(min(i,a)+1):
        for k in range(min(j,l3)+1):
            s = i-j
            t = j-k
            count = n/(s+t+k)
            if s > 0:
                count += dp[s-1][t][k]*(s/(s+t+k))     
            if t > 0 :
                count += dp[s+1][t-1][k]*(t/(s+t+k))
            if k > 0 :
                count += dp[s][t+1][k-1]*(k/(s+t+k))

            dp[s][t][k] = count

print(dp[l1][l2][l3])