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: Accepted

Solution code:
import collections
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = [int(x) for x in readline().split()]
ac = collections.Counter(A)
assert set(ac.keys()).issubset({1, 2, 3})


def solve(c1, c2, c3):
    K = c1 + c2 + c3
    L = K + 1
    L2 = L ** 2
    dp = [0.0] * L ** 3
    for i3 in range(c3 + 1):
        for i2 in range(c2 + c3 + 1):
            for i1 in range(N - i2 - i3 + 1):
                isum = i1 + i2 + i3
                if isum == 0:
                    continue
                i0 = N - i1 - i2 - i3
                if i0 < 0:
                    continue
                e = i0
                if i1 > 0:
                    e += i1 * (1.0 + dp[(i1 - 1) * L2 + i2 * L + i3])
                if i2 > 0 and i1 <= K:
                    e += i2 * (1.0 + dp[(i1 + 1) * L2 + (i2 - 1) * L + i3])
                if i3 > 0 and i2 + 1 <= c2 + c3:
                    e += i3 * (1.0 + dp[i1 * L2 + (i2 + 1) * L + i3 - 1])
                dp[i1 * L2 + i2 * L + i3] = e / isum
    return dp[c1 * L2 + c2 * L + c3]


if __name__ == "__main__":
    print(solve(ac[1], ac[2], ac[3]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    m = float(n)
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = m
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
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: Accepted

Solution code:
from collections import Counter

N = int(input())
A = Counter(map(int, input().split()))
S = [None, A[3] + A[2] + A[1], A[3] + A[2], A[3]]

dp = [[[0] * (S[3] + 1) for _ in range(S[2] + 1)] for __ in range(S[1] + 1)]

for l in range(1, S[1] + 1):
    for m in range(S[2] + 1):
        if l < m:
            break
        for k in range(S[3] + 1):
            if m < k:
                break
            dp[l][m][k] = (dp[l - 1][m][k] * (l - m) + dp[l][m - 1][k] * (m - k) + dp[l][m][k - 1] * k + N) / l
print(dp[S[1]][S[2]][S[3]])

Submission status: Accepted

Solution code:
n=int(input())
a= list(map(int, input().split()))
# 寿司の皿を乗ってる寿司の数で分ける
x=[0,0,0]
for i in range(n):
    x[a[i]-1]+=1

# dp[k][i][j]:k3個、i2個、j1個の寿司が乗ってる皿の数。そこからの全部0になる回数の期待値
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            v=k+i+j
            if 0<v<=n:
                dp[k][i][j]+=(dp[k][i][j-1]*j+dp[k][i-1][j+1]*i+dp[k-1][i+1][j]*k+n)/v

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

Submission status: Accepted

Solution code:
n=int(input())
a= list(map(int, input().split()))
# 寿司の皿を乗ってる寿司の数で分ける
x=[0,0,0]
for i in range(n):
    x[a[i]-1]+=1

# dp[k][i][j]:k3個、i2個、j1個の寿司が乗ってる皿の数。そこからの全部0になる回数の期待値
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for k in range(n+1):
    for i in range(n+1):
        for j in range(n+1):
            v=k+i+j
            if 0<v<=n:
                dp[k][i][j]+=dp[k][i][j-1]*(j/v)+dp[k][i-1][j+1]*(i/v)+dp[k-1][i+1][j]*(k/v)+n/v

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Apr 24 22:56:49 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
def input():
    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

#N, *A = map(int, open(0).read().split())

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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 = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1, 1:] += prev[1:, :-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a<0] = 0
#    print(s,dp)

ans = dp[count[2],count[3]]
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Apr 24 22:56:49 2020
"""

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

N, *A = map(int, open(0).read().split())

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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 = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1, 1:] += prev[1:, :-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a<0] = 0
#    print(s,dp)

ans = dp[count[2],count[3]]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                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)
print(DP[a][b][c])

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

count = np.bincount(A, minlength=4)
total = np.sum(count * np.arange(4, dtype=int))

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 = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1, 1:] += prev[1:, :-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a<0] = 0
#    print(s,dp)

ans = dp[count[2],count[3]]
print(ans)

Submission status: Accepted

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
a = list(map(float, input().split()))
one = a.count(1)
two = a.count(2)
three = a.count(3)

#dp[i][j][k]は残1がi枚、残2がj枚、残3がk枚のときの残り回数の期待値
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 0.0

def rec(i, j, k):
    if dp[i][j][k] > -1:
        return dp[i][j][k]

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

for k in range(three + 1):
    for j in range(two + three + 1 - k):
        for i in range(one + two + three + 1 - k - j):
            if i + j + k == 0:
                continue

            res = 0
            if i > 0:
                res += dp[i - 1][j][k] * i / (i + j + k)
            if j > 0:
                res += dp[i + 1][j - 1][k] * j / (i + j + k)
            if k > 0:
                res += dp[i][j + 1][k - 1] * k / (i + j + k)
            res += N / (i + j + k)
            dp[i][j][k] = res

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

Submission status: Accepted

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

dp = [[[0 for _ in range(301)]for __ in range(301)]for ___ in range(301)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            cnt = i + j + k
            if cnt == 0 or cnt > n :continue
            if i == 0 and j ==0 and k ==1:
                dp[i][j][k] = 1
                continue
            if k > 0:
                dp[i][j][k] += (1+dp[i][j][k-1] * cnt/(cnt-1))*k/cnt
            if j > 0:
                dp[i][j][k] += (1+dp[i][j-1][k+1])*j/cnt
            if i > 0:
                dp[i][j][k] += (1+dp[i-1][j+1][k])*i/cnt 
            
print(dp[a.count(3)][a.count(2)][a.count(1)])

Submission status: Accepted

Solution code:
n=int(input())
k=[0,0,0]
a,s,d=0,0,0
for i in input().split():
  if i=="1":a+=1
  elif i=="2":s+=1
  else:d+=1
dp=[[ [0]*(n+1) for j in range(n+1)] for i in range(n+1)]
for i in range(d+1):
  for j in range(d+s+1):
    for k in range(n+1-i-j):
      su=i+j+k
      ret=0
      if su:
        ret+=n/su
        if i>=1:
          ret+=dp[i-1][j+1][k]*i/su
        if j>=1 :
          ret+=dp[i][j-1][k+1]*j/su
        if k>=1:
          ret+=dp[i][j][k-1]*k/su
      dp[i][j][k]=ret
print(dp[d][s][a])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(c + 1):
    for j in range(b + c + 1 - k): # ２貫の皿の数の最大値 - 3枚の皿の数
        for i in range(a + b + c + 1 - k - j):
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = N * 1.0
            if i > 0:
                tmp += i * dp[i-1][j][k]
            if j > 0:
                tmp += j * dp[i+1][j-1][k]
            if k > 0:
                tmp += k * dp[i][j+1][k-1]
            dp[i][j][k] = tmp / (i + j + k)
print(dp[i][j][k])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

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

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
c = Counter(map(int, input().split()))
dp = [[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]

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

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

Submission status: Accepted

Solution code:
n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                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)
print(DP[a][b][c])

Submission status: Accepted

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

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

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

#dp = dp3(0.0, cnt[2]+1, cnt[1]+cnt[2]+1, N+1)
#dp = dp3(0.0, N+1, N+1, N+1)
dp = dp3(0.0, 301, 301, 301)
dp[0][0][0] = 0

for k in range(cnt[2]+1):
    for j in range(cnt[1]+cnt[2]+1-k):
        for i in range(N+1-j-k):
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

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

Submission status: Accepted

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

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

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

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

for k in range(cnt[2]+1):
    for j in range(cnt[1]+cnt[2]+1-k):
        for i in range(N+1-j-k):
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

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

Submission status: Accepted

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

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 = dp3(0.0, N+1, N+1, N+1)
#dp = dp3(0.0, 301, 301, 301)
dp[0][0][0] = 0

for k in range(cnt[2]+1):
#for i in range(N+1):
    for j in range(cnt[1]+cnt[2]+1-k):
    #for j in range(N+1):
        #for k in range(cnt[2]+1):
        #for k in range(N+1):
        for i in range(N+1-j-k):
            #print(i, j, k)
            if i+j+k == 0:
                continue
            num = i+j+k
            dp[i][j][k] = N_f
            if i > 0:
                dp[i][j][k] += dp[i-1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i+1][j-1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j+1][k-1] * k
            dp[i][j][k] /= num

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

Submission status: Accepted

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= [[[0] * (N+1) for i in range(N+1)] for j in range(N+1)]
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:
                res = N
                if i > 0:
                    res += dp[k][j][i-1]*i
                if j > 0:
                    res += dp[k][j-1][i+1]*j
                if k > 0:
                    res += dp[k-1][j+1][i]*k
                dp[k][j][i] = res/(i+j+k)
print(dp[c3][c2][c1])

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(a)

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

# メモ化再帰ではpypy3でもTLEするのでforループを使う
# j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
# dp[i][j][k]の順だとTLEなのでdp[k][j][i]の順で
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[k][j][i-1]*i
                if j > 0:
                    tmp += dp[k][j-1][i+1]*j
                if k > 0:
                    tmp += dp[k-1][j+1][i]*k
                dp[k][j][i] = tmp/(i+j+k) # 割り算をまとめた方が速い

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

Submission status: Accepted

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[k][j][i-1]*i
                    if j > 0:
                        tmp += dp[k][j-1][i+1]*j
                    if k > 0:
                        tmp += dp[k-1][j+1][i]*k
                    dp[k][j][i] = tmp/(i+j+k) # 割り算をまとめないとTLE

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = tuple(map(int, input().split()))

    # I = A.count(1)
    # J = A.count(2)
    # K = A.count(3)

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

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

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

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

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

    # output(dp)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

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

    N = int(input())
    a = list(map(int, 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]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

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

    N = int(input())
    a = list(map(int, 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]])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():

    from collections import Counter

    N = int(input())
    a = list(map(int, 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]])

if __name__ == '__main__':
    main()

Submission status: Accepted

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)

    # メモ化再帰では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: Accepted

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.0]*(301) for i in range(301)] for j in range(301)]
 
for i in range(1, N+1):
    for j in range(min(i, num_2+num_3)+1):
        for k in range(min(j, num_3)+1):
            s = i-j
            t = j-k
            res = 0
            if s > 0:
                res += dp[s-1][t][k]*s  
            if t > 0:
                res += dp[s+1][t-1][k]*t
            if k > 0:
                res += dp[s][t+1][k-1]*k
            res += N
            res /= (s+t+k)

            dp[s][t][k] = res

print(dp[num_1][num_2][num_3])

Submission status: Accepted

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

    n = int(input())

    l1 = l2 = l3 = 0
    for i in map(int,input().split()):
        if i == 1:
            l1 += 1
        elif i == 2:
            l2 += 1
        else:
            l3 += 1

    a = l2+l3
    dp = [[[0.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])
if __name__ == "__main__":
    main()

Submission status: Accepted

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.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])