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:
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K
dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):#n=i+j+k
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

Submission status: Accepted

Solution code:
n = int(input())

dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
# 1-index

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

a = list(map(int,input().split()))
q = [0,0,0,0]
for i in a:
    q[i] += 1

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

Submission status: Accepted

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

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

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

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ones , twos, threes = 0,0,0

for i in a:
  if i ==1:
    ones+=1
  elif i ==2:
    twos+=1
  else:
    threes+=1

max_ones = ones+twos+threes
max_twos = twos+threes
max_threes = threes
# dp[n][n][n]
dp = [[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]

for k in range(max_threes+1):
  for j in range(max_twos+1-k):
    for i in range(max_ones+1-j-k):
      if i+j+k==0:
        continue
      else:
        dp[i][j][k] = n/(i+j+k)
        if i>0:
          dp[i][j][k] += (dp[i-1][j][k]*i)/(i+j+k)
        if j>0:
          dp[i][j][k] += (dp[i+1][j-1][k]*j)/(i+j+k)
        if k>0:
          dp[i][j][k] += (dp[i][j+1][k-1]*k)/(i+j+k)
          
          
print(dp[i][j][k])

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(float,input().split()))
a,b,c=0,0,0
for i in range(N):
  if A[i]==1:
    a+=1
  elif A[i]==2:
    b+=1
c=N-a-b
i=1
dp=[[[0]*(N+2) for i in range(N+2)] for j in range(N+2)]
for k in range(c+1):
  for j in range(N-k-a+1):
    for i in range(N-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+N)/(i+j+k)
print(dp[c][b][a])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    N = int(input())
    a = tuple(map(int, input().split()))
    c1 = a.count(1) #i
    c2 = a.count(2) #j
    c3 = a.count(3) #k

    dp = [[[0.0]*(N+1) for _ in range(N+1)] for __ in range(N+1)]
    for i in range(c3+1):
        for j in range(c2+c3-i+1):
            for k in range(N-i-j+1):
                if i == j == k == 0:
                    continue
                tmp = N
                if k != 0:
                    tmp += k*dp[k-1][j][i]
                if j != 0:
                    tmp += j*dp[k+1][j-1][i]
                if i != 0:
                    tmp += i*dp[k][j+1][i-1]
                dp[k][j][i] = tmp/(i+j+k)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

# i, j, kを全通り回す
for k in range(three + 1):
    # 3個の皿がk個のとき
    for j in range(two + three - k + 1):
        # 2枚の皿は
        # 初期のtwo
        # 3個の皿がk枚のとき、three-k枚が2枚になっている
        for i in range(one + two + three - k - j + 1):
            # 1枚の皿は
            # 初期のone
            # 3枚の皿がk枚、2枚の皿がj枚のとき、two+three-k-j枚が1枚になっている
            if i == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0*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[one][two][three])

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
a=0
b=0
c=0
d=sum(A)
for i in range(n):
  if A[i]==1:
    a=a+1
  elif A[i]==2:
    b=b+1
c=n-a-b
i=1
dp=[[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]
for k in range(c+1):
  for j in range(n-k-a+1):
    for i in range(n-k-j+1):
      if i==0 and j==0 and k==0:
        continue
      dp[k][j][i]=(dp[k][j][i-1]*i+dp[k][j-1][i+1]*j+dp[k-1][j+1][i]*k+n)/(i+j+k)
print(dp[c][b][a])

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
I,J,K=0,0,0
for a in A:
    if a==1:
        I+=1
    if a==2:
        J+=1
    if a==3:
        K+=1
L=I+J+K
M=J+K



dp=[[[0.0]*(K+1) for i in range(M+1)] for i in range(L+1)]
for n in range(1,L+1):
    for m in range(min(n,M)+1):#m=j+k
        for k in range(min(m,K)+1):
            j=m-k
            i=n-m
            #print(i,j,k)
            ret=N/(i+j+k)
            if i>0:
                ret+=dp[i-1][j][k]*(i/(i+j+k))
            if j>0:
                ret+=dp[i+1][j-1][k]*(j/(i+j+k))
            if k>0:
                ret+=dp[i][j+1][k-1]*(k/(i+j+k))
            dp[i][j][k]=ret
print(dp[I][J][K])

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[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
 
# 先にiについて更新することで、dp[i""+1""][j-1][k]を可能にしている。
# 先にjについて更新することで、dp[i][j""+1""][k-1]を可能にしている。
for k in range(c + 1):
    for j in range(b + c + 1 - k): # ２貫の皿の数の最大値(a = 0のとき) - 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:
N = int(input())
A = list(map(int, input().split()))
a = A.count(1)
b = A.count(2)
c = A.count(3)
"""
dp[i][j][k]: 残り１貫の皿がi, ２貫j, ３貫kの状態から全部食べ切るまでの期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

# 先にiについて更新することで、dp[i""+1""][j-1][k]を可能にしている。
# 先にjについて更新することで、dp[i][j""+1""][k-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:
#!/usr/bin/env python3
from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_j
J - Sushi / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 枚の皿があります。 皿には 1,2,…,N と番号が振られています。 
最初、各 i (1≤i≤N) について、皿 i には ai (1≤ai≤3) 個の
    寿司が置かれています。
すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。
1,2,…,N の目が等確率で出るサイコロを振り、出目を i とする。 
皿 i に寿司がある場合、皿 i の寿司を 1 個食べる。 
皿 i に寿司が無い場合、何も行わない。
すべての寿司が無くなるまでの操作回数の期待値を求めてください。

解説 :
「皿1に寿司が2個、皿2に寿司が1個」という状態と 
    「皿1に寿司が1個、皿2に寿司が2個」という状態だと、
        操作回数の期待値は同じ。
よく考えると、「どの皿に何個あるか」という
    ところまでわかる必要はなくて、
        「1個の皿がいくつ(c1)、2個の皿がいくつ(c2)、
            3個の皿がいくつ(c3)」だけで期待値は決まることがわかる。
すると結局

dp[c3][c2][c1] = 1 + 
    dp[c3][c2][c1 - 1] * (1の皿が選ばれる確率) + 
        dp[c3][c2 - 1][c1 + 1] * (2の皿が選ばれる確率) + 
            dp[c3 - 1][c2 + 1][c1] * (1の皿が選ばれる確率) + 
                dp[c3][c2][c1] * (0の皿が選ばれる確率) 

この確率漸化式になる
あとはdp[c3][c2][c1]を左辺に移行してごにょごにょして
dp[c3][c2][c1] = (n + 
    dp[c3][c2][c1 - 1] * c1 + 
        dp[c3][c2 - 1][c1 + 1] * c2 + 
            dp[c3 - 1][c2 + 1][c1] * c3) / (c1 + c2 + c3)
という遷移式を完成
メモ化再帰でもできるという噂があるがPythonはカスなので 
    いろいろと工夫する必要があります。
知見的には 
    ====================================
    | 期待値 = Σ ワンステップ前の期待値 * |
    |    そのステップになるための確率)    |
    ====================================
です。
"""
#solve
def solve():
    n = II()
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    d = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
    for i in range(c3 + 1):
        di = d[i]
        dim1 = d[i - 1]
        for j in range(c3 + c2 + 1 - i):
            dim1jp1 = dim1[j + 1]
            dijm1 = di[j - 1]
            dij = di[j]
            for k in range(c3 + c2 + c1 - i - j + 1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * dim1jp1[k]
                if j: res += j * dijm1[k + 1]
                if k: res += k * dij[k-1]
                dij[k] = res / l
    print(d[c3][c2][c1])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from functools import lru_cache
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10
#solve
def solve():
    n = II()
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    d = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]
    for i in range(c3 + 1):
        di = d[i]
        dim1 = d[i - 1]
        for j in range(c3 + c2 + 1 - i):
            dim1jp1 = dim1[j + 1]
            dijm1 = di[j - 1]
            dij = di[j]
            for k in range(c3 + c2 + c1 - i - j + 1):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * dim1jp1[k]
                if j: res += j * dijm1[k + 1]
                if k: res += k * dij[k-1]
                dij[k] = res / l
    print(d[c3][c2][c1])
    return


#main
if __name__ == '__main__':
    solve()

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

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

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

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

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

Submission status: Accepted

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

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

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

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

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
aaa=cnt[1]
bbb=cnt[2]
ccc=cnt[3]

dp=[[[0]*(N+1) for j in range(bbb+ccc+1)] for i in range(ccc+1)]

for k in range(ccc+1):
    for j in range(bbb+ccc-k+1):
        for i in range(N-k-j+1):
            tmp=i+j+k
            if tmp==0:
                continue
            else:
                dp[k][j][i]=N/tmp
                if i>0:
                    dp[k][j][i]+=i*dp[k][j][i-1]/tmp
                if j>0:
                    dp[k][j][i]+=j*dp[k][j-1][i+1]/tmp
                if k>0:
                    dp[k][j][i]+=k*dp[k-1][j+1][i]/tmp
                
print(dp[ccc][bbb][aaa])

Submission status: Accepted

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

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

        ret = n
        if c1 > 0:
            ret += c1 * memo[c1 - 1][c2][c3]
        if c2 > 0:
            ret += c2 * memo[c1 + 1][c2 - 1][c3]
        if c3 > 0:
            ret += c3 * memo[c1][c2 + 1][c3 - 1]
        ret /= c1 + c2 + c3

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

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

    ctr = Counter(a)

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

    for c3 in range(n + 1):
        for c2 in range(n - c3 + 1):
            for c1 in range(n - c2 - c3 + 1):
                prob(c1, c2, c3)

    print(memo[ctr[1]][ctr[2]][ctr[3]])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
a,b,c = c[1],c[2],c[3]
DP = [[[0]*(n+2) for i in range(n+2)] for j in range(n+2)]

for i in range(c+1):
    for j in range(n-a-i+1):
        for k in range(n-i-j+1):
            if i+j+k:
                DP[i][j][k] = (i*DP[i-1][j+1][k] + j*DP[i][j-1][k+1] + k*DP[i][j][k-1] + n)/(i+j+k)
print(DP[c][b][a])

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    A=[0]*3
    for i in map(int,input().split()):
        A[i-1]+=1
    dp=[[[0]*(n+2)for _ in range(n+2)]for __ in range(n+2)]
    for i in range(A[2]+1):
        for j in range(n-A[0]-i+1):
            for k in range(n-i-j+1):
                if i+j+k!=0:
                    dp[i][j][k]=(dp[i-1][j+1][k]*i+dp[i][j-1][k+1]*j+dp[i][j][k-1]*k+n)/(i+j+k)
    i,j,k=A
    print(dp[k][j][i])
main()

Submission status: Accepted

Solution code:
n=int(input())
A=[0]*3
for i in map(int,input().split()):
    A[i-1]+=1
dp=[[[0]*(n+2)for _ in range(n+2)]for __ in range(n+2)]
for i in range(A[2]+1):
    for j in range(n-A[0]-i+1):
        for k in range(n-i-j+1):
            if i+j+k!=0:
                dp[i][j][k]=(dp[i-1][j+1][k]*i+dp[i][j-1][k+1]*j+dp[i][j][k-1]*k+n)/(i+j+k)
i,j,k=A
print(dp[k][j][i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()
    
I = arr.count(3)
J = arr.count(2)
K = arr.count(1)
    
dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
        for ___ in range(I+1)]
    
for i in range(I+1):
    for j in range(I+J+1-i):
        for k in range(I+J+K+1-i-j):
            if i + j + k == 0:
                continue
            tmp = 0
            if k > 0:
                tmp += (k/n)*dp[i][j][k-1]
            if j > 0:
                tmp += (j/n)*dp[i][j-1][k+1]
            if i > 0:
                tmp += (i/n)*dp[i-1][j+1][k]
            dp[i][j][k] += (n/(i+j+k))*(1 + tmp)
    
print(dp[I][J][K])

Submission status: Accepted

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

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

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

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

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
abc=[0,0,0]#1,2,3個の寿司が載っている皿の枚数
for i in A:
    abc[i-1]+=1
    
total=sum(A)

#1,2,3個の寿司が載っている皿の枚数がi,j,kから全てを取るのに必要な期待値
dp=[[[0.0]*(N+1) for _ in range(N+1)] for i in range(N+1)]



for k in range(abc[2]+1):#3枚の皿は初期枚数から増えない
    for j in range(abc[2]+abc[1]+1-k):#2枚の皿の枚数は，3枚の皿が減った枚数に依存
        for i in range(sum(abc)+1-j-k):
            if i==0 and j==0 and k==0:
                continue
            if i-1>=0:
                dp[i][j][k]+=dp[i-1][j][k]*i
            if j-1>=0:
                dp[i][j][k]+=dp[i+1][j-1][k]*j
            if k-1>=0:
                dp[i][j][k]+=dp[i][j+1][k-1]*k
            dp[i][j][k]+=N
            dp[i][j][k]/=(i+j+k)

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

Submission status: Accepted

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

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

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

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 == 0 and j == 0 and k == 0:
                continue
            tmp = 1.0 * 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[one][two][three])

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
d =dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
B = 0
for a in As:
    B += (N+1)**(a-1)
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            if i:
                E += (i*N)/(s0**2) + d[x-1]*(i/s0)
            if j:
                E += (j*N)/(s0**2) + d[x-N]*(j/s0)
            if k:
                E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
d = dict()
def encode(i,j,k):
    return i+j*(N+1)+k*((N+1)**2)
def decode(x):
    return [(x // ((N+1)**i))%(N+1) for  i in range(3)]
B = 0
for a in As:
    B += (N+1)**(a-1)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = N-i-j-k
            if i:
                E += (i*N)/((N-s0)**2) + d[x-1]*(i/(N-s0))
            if j:
                E += (j*N)/((N-s0)**2) + d[x-N]*(j/(N-s0))
            if k:
                E += (k*N)/((N-s0)**2) + d[x-N**2-N]*(k/(N-s0))
            d[x] = E
print(d[B])

Submission status: Accepted

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

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

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

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

Submission status: Accepted

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

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

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

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

Submission status: Accepted

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

I = a.count(3)
J = a.count(2)
K = a.count(1)

dp = [[[0 for _ in range(I+J+K+1)] for __ in range(I+J+1)]
      for ___ in range(I+1)]

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

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

Submission status: Accepted

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

c1 = a.count('1')
c2 = a.count('2')
c3 = a.count('3')

dp =[ [[0] * (n+1) for _ in range(c3+c2+1)] for __ in range(c3+1)]
# dp[0][0][0] = 0

for i in range(c3+1):
    for j in range(c3+c2+1-i):
        for k in range(n+1-i-j):
            if(i+j+k == 0):
                dp[i][j][k]=0
            else:
                temp = 0
                if(i > 0):
                    temp += dp[i-1][j+1][k] * i/(k+j+i)
                if(j > 0):
                    temp += dp[i][j-1][k+1] * j/(k+j+i)
                if(k > 0):
                    temp += dp[i][j][k-1] * k/(k+j+i)
                dp[i][j][k] = temp + n/(k+j+i)

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

Submission status: Accepted

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

cnt1 = a.count(1)
cnt2 = a.count(2)
cnt3 = a.count(3)

dp = [[[-1]*(cnt1 + cnt2 + cnt3 + 1) for _ in range(cnt2 + cnt3 + 1)] for _ in range(cnt3 + 1)]
dp[0][0][0] = 0
 
for c3 in range(cnt3 + 1):
    for c2 in range(cnt2 + cnt3 + 1 - c3):
        for c1 in range(cnt1 + cnt2 + cnt3 + 1 - c2 - c3):
            if c1 + c2 + c3 == 0:
                continue
            tmp = 0
            num = c1 + c2 + c3
            # c3を選ぶ
            if c3 != 0:
                tmp += (c3 / n) * dp[c3-1][c2+1][c1]
            # c2を選ぶ
            if c2 != 0:
                tmp += (c2 / n) * dp[c3][c2-1][c1+1]
            # c1を選ぶ
            if c1 != 0:
                tmp += (c1 / n) * dp[c3][c2][c1-1]
            dp[c3][c2][c1] = n / num * (tmp + 1)

print(dp[cnt3][cnt2][cnt1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, a: "List[int]"):

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

    J = min(c[2]+c[3]+1, N+1)
    I = min(c[1]+c[2]+c[3]+1, N+1)
    kitai = [[[0]*(I+1) for _ in range(J+1)]
             for _ in range(c[3]+1)]
    for k in range(c[3]+1):
        for j in range(J):
            for i in range(I):
                tot = i+j+k
                if tot == 0 or tot > N:
                    continue
                res = N + kitai[k][j][i-1]*i + \
                    kitai[k][j-1][i+1]*j + kitai[k-1][j+1][i]*k
                kitai[k][j][i] = res/tot
    print(kitai[c[3]][c[2]][c[1]])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()