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: Wrong Answer

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))

def f(d):
    ans = 0
    if sum(d)==0:
        return 0
    try:
        return stored[(d[0],d[1],d[2])]
    except:
        pass
    ans += n/(d[0]+d[1]+d[2])
    if d[0]:
        x = d[0]/(d[0]+d[1]+d[2])
        ans += x*f([d[0]-1,d[1],d[2]])
    if d[1]:
        x = d[1]/(d[0]+d[1]+d[2])
        ans += x*f([d[0]+1,d[1]-1,d[2]])
    if d[2]:
        x = d[2]/(d[0]+d[1]+d[2])
        ans += x*f([d[0],d[1]+1,d[2]-1])
    stored[(d[0],d[1],d[2])] = ans
    return ans
 
 
n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
stored = {}

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter as cc
from numba import njit
import numpy as np

def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())

# sys.setrecursionlimit(10**4)
n = ii()
a = li()
c = cc(a)
N = sum(c.values())
cache = np.full((N+1, N+1, N+1), -1, dtype=int)
cache[0][0][0] = 0
@njit(cache=True)
def dfs(x, y, z, N, cache):
    if x+y+z==0:
        return 0
    if cache[x][y][z]>=0:
        return cache[x][y][z]
    tmp = 1
    if x > 0:
        tmp += dfs(x-1, y, z,N, cache)*x/N
    if y > 0:
        tmp += dfs(x+1, y-1, z, N, cache)*y/N
    if z > 0:
        tmp += dfs(x, y+1, z-1, N, cache)*z/N
    tmp *= N/(x+y+z)
    cache[x][y][z] = tmp
    return tmp

print(dfs(c[1], c[2], c[3], N, cache))

Submission status: Wrong Answer

Solution code:
n = int(input())

cnt = [0 for _ in range(4)]

sl = input().split()
for x in sl:
    dish = int(x)
    cnt[dish] += 1

ev = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]
p = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]
dp = [[[0 for _ in range(n+5)] for _ in range(n+5)] for _ in range(n+5)]

p[cnt[1]][cnt[2]][cnt[3]] = 1

print(cnt[3], cnt[2], cnt[1])

for three in reversed(range(n+1)):
    for two in reversed(range(n+1)):
        for one in reversed(range(n+1)):
            if one == 0 and two == 0 and three == 0:
                continue
            
            p_waste = (n - one - two - three) / n
            ev_waste = p_waste / (1-p_waste)
            ev[one][two][three] += ev_waste * p[one][two][three]
            if one != 0:
                p_go = one / (one+two+three)
                p[one-1][two][three] += p[one][two][three] * p_go
                ev[one-1][two][three] += ev[one][two][three] * p_go
            if two != 0:
                p_go = two / (one+two+three)
                p[one+1][two-1][three] += p[one][two][three] * p_go
                ev[one+1][two-1][three] += ev[one][two][three] * p_go
            if three != 0:
                p_go = three / (one+two+three)
                p[one][two+1][three-1] += p[one][two][three] * p_go
                ev[one][two+1][three-1] += ev[one][two][three] * p_go

#print(ev)
#print(p[0][0][0])
#for row in ev:
#    print(row)
print(ev[0][0][0] + cnt[1] + cnt[2]*2 + cnt[3]*3)

Submission status: Wrong Answer

Solution code:
from collections import Counter

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

Submission status: Wrong Answer

Solution code:
import numpy as np


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

print(rec(one,two,three))
print(dp)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]

dp = []
for _ in range(n + 1):
    dp.append([[0] * (r + 1) for _ in range(r + q + 1)])
dp[0][0][0] = 0



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

Submission status: Wrong Answer

Solution code:
#input
N = int(input())
n1 = 0
n2 = 0
n3 = 0
for s in input().split():
    if s == "1":
        n1 += 1
    elif s == "3":
        n2 += 1
    else:
        n3 += 1
#output

#experiment
import numpy as np

def sushi(dp, N):
    for l in range(1, N+1):
        for i in range(l, -1, -1):
            for j in range(l-i, -1, -1):
                k = l-i-j

                my_sum = 0
                all = (i+j+k)/N
                loop = 1/all

                if i != 0:
                    my_sum += dp[i-1, j, k] * (i/N)
                if j != 0:
                    my_sum += dp[i+1, j-1, k] * (j/N)
                if k != 0:
                    my_sum += dp[i, j+1, k-1] * (k/N)

                dp[i, j, k] = my_sum/all + loop 

dp = np.zeros((N+1, N+1, N+1))
sushi(dp, N)

print(dp[n1, n2, n3])

Submission status: Wrong Answer

Solution code:
from collections import Counter
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]+1):
            for i in range(a[1]+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: Wrong Answer

Solution code:
n=300
A=[3]*n
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: Wrong Answer

Solution code:
from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.buffer.readline().strip().decode()
def mdata(): return map(float, data().split())
out=sys.stdout.write
#sys.setrecursionlimit(100000)
INF=int(1e9)
mod=int(1e9)+7


n=int(data())
P=list(mdata())
dp=[0]*(n//2+2)
dp[1]=1
for i in range(n):
    for j in range(len(dp)-1,0,-1):
        dp[j]=dp[j-1]*(1-P[i])+dp[j]*(P[i])
print(sum(dp))

Submission status: Wrong Answer

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(max(n-k, z+y) + 1):
        for i in range(n-k-j + 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: Wrong Answer

Solution code:

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

ones,twos,threes=0,0,0

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

#dp[i][j][k] // i ones j twoes k threes
max_ones=ones+twos+threes
max_twos=twos+threes
max_three=threes

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

for k in range(max_three+1):
    for j in range(max_twos-k+1):
        for i in range(max_ones-k-j+1):
            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+1][j+1][k-1]*k)/(i+j+k)

print(dp[i][j][k])

Submission status: Wrong Answer

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]
        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]
        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]
        tmp /= i_sum
        memo[i1][i2][i3] = tmp
        return tmp


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

Submission status: Wrong Answer

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 = 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: Wrong Answer

Solution code:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf

#numpy使ってみる
import sys,numpy
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = numpy.array([[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)])

dp[n][n][n] = 0
divT = numpy.array([1/i for i in range(1,n+1)])

for x in range(n,cnt[1]+cnt[2]-1,-1):## -2だったのを-1に
    for y in range(x,cnt[2]-1,-1):##cnt[2]
        for z in range(y,-1,-1):
            delta = n*divT[n-z-1]#2枚以下を引くまで
            if x != n:
                dp[x][y][z] += (dp[x+1][y][z] + delta) * (n-x)
            if y != x:
                dp[x][y][z] += (dp[x][y+1][z] + delta) * (x-y)#x+1,y+1ではない
            if z != y:
                dp[x][y][z] += (dp[x][y][z+1] + delta)* (y-z)#x+1,y+1,z+1ではない
            dp[x][y][z] *=divT[n-z-1]

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

Submission status: Wrong Answer

Solution code:
n=300#int(input())
A=[3]*300#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: Wrong Answer

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=0
dp=[[[0]*(n+3) for i in range(n+3)] for j in range(n+3)]
for k in range(1,c+2):
  for j in range(1,n-k-i+4):
    for i in range(1,n-k-j+4):
      if (i-1)*(j-1)*(k-1)!=0:
        dp[i][j][k]=(dp[i-1][j][k]*(i-1)+dp[i+1][j-1][k]*(j-1)+dp[i][j+1][k-1]*(k-1)+n)/(i+j+k-3)
print(dp[a+1][b+1][c+1])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
N = int(input())
a = list(map(int,input().split()))
dp = [[[0.0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
def rec(i,j,k):
    #global res
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0.0
    res = 0.0

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

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

#print(dp)
print(rec(one,two,three))
#print(dp)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
c = Counter(a)
c1,c2,c3 = c[1],c[2],c[3]
print(c1,c2,c3)
dp = [[[0 for i in range(c3+1)] for j in range(c2+c3+1)] for k in range(c1+c2+c3+1)]
#dp[i][j][k] := 1個×i皿、2個×j皿、3個×k皿における期待値
for k in range(c3+1):
  for j in range(c2+c3+1):
    for i in range(n+1):
      if i+j+k > n or i == j == k == 0:
        continue
      x = (n-i-j-k)/n
      dp[i][j][k] = 1
      if 0<i :
        dp[i][j][k] += dp[i-1][j][k]*(i/n)
      if 0<j and i+1<=n:
        dp[i][j][k] += dp[i+1][j-1][k]*(j/n)
      if 0<k and j+1<=c2+c3:
        dp[i][j][k] += dp[i][j+1][k-1]*(k/n)
      dp[i][j][k] /= 1-x
print(dp[c1][c2][c3])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(float, input().split()))
# 参考
# https://qiita.com/drken/items/03c7db44ccd27820ea0d

N123 = [0,0,0]
for a in A:
  if a == 1:
    N123[0] += 1
  elif a == 2:
    N123[1] += 1
  elif a == 3:
    N123[2] += 1

dp = [[[-1]*(N123[2]+1) for _ in range(N123[1]+1)] for _ in range(N123[0]+1)]
dp[0][0][0] = 0

def rec(i,j,k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  #elif all([i==0, j==0, k==0]):
  #  return 0
  else:
    n = 0
    if i > 0:
      n += rec(i-1,j,k) * i
    if j > 0:
      n += rec(i,j-1,k) * j
    if k > 0:
      n += rec(i,j,k-1) * k
    n += N 
    n /= (i+k+j)
    dp[i][j][k] = n
    return n
  
print(rec(N123[0], N123[1], N123[2]))

Submission status: Wrong Answer

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)
    print(d[c3][c2][c1])
    return


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

Submission status: Wrong Answer

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()
    d = defaultdict(int)
    c = LI()
    c1, c2, c3 = [c.count(i) for i in range(1, 4)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                l = i + j + k
                if l == 0: continue
                res = n
                if i: res += i * d[(k, j + 1, i - 1)]
                if j: res += j * d[(k + 1, j - 1, i)]
                if k: res += k * d[(k - 1, j, i)]
                d[(k, j, i)] = res / l
    
    print(d[(c1, c2, c3)])
    return


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

Submission status: Wrong Answer

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=[[[-1] * (302) for i in range(302)] for i in range(302)]

for c in range(C+1):
  for b in range(B+C+1):
    for a in range(A+B+C+1):
      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: Wrong Answer

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=[[[-1] * (302) for i in range(302)] for i in range(302)]

for a in range(A+1):
  for b in range(A+B+1-a):
    for c in range(A+B+C+1-a-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])

Submission status: Wrong Answer

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[-1][-1][-1])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
N = int(input())
A = [int(a) for a in input().split()]

f = A.count(1)
s = A.count(2)
t = A.count(3)

dp = [[["0"]*(t+1) for _ in range(s+t+1)] for _ in range(N+1)]
dp[0][0][0] = 0
def P(i, j, k):
    if dp[i][j][k] != "0":
        return dp[i][j][k]
    res = N
    if i > 0:
        res += P(i-1, j, k)*i
    if j > 0:
        res += P(i+1, j-1, k)*j
    if k > 0:
        res += P(i, j+1, k-1)*k
    res //= (i+j+k)
    dp[i][j][k] = res
    return res

print(P(f, s, t))

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
d = [0]*((N+1)**3)
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)
d[0] = 0
for k in range(N+1):
    for j in range(N+1-k):
        for i in range(1,N+1-k-j):
            E = 0
            x = encode(i,j,k)
            s0 = i+j+k
            E += (i*N)/(s0**2) + d[x-1]*(i/s0)
            E += (j*N)/(s0**2) + d[x-N]*(j/s0)
            E += (k*N)/(s0**2) + d[x-N**2-N]*(k/s0)
            d[x] = E
print(d[B])

Submission status: Wrong Answer

Solution code:
def solve(ones, twos, threes, n):
    dp = [[[-1 for _ in range(n+1)] for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0

    stack = [(ones, twos, threes, False)]

    while stack:
        a, b, c, proc = stack.pop()

        if dp[a][b][c] >= 0:
            continue

        if not proc:
            stack.append((a, b, c, True))

            if a >= 1:
                stack.append((a-1, b, c, False))

            if a+1 < n and b >= 1:
                stack.append((a+1, b-1, c, False))

            if b+1 < n and c >= 1:
                stack.append((a, b+1, c-1, False))
        else:
            den = a + b + c
            ans = n / den
            if a > 0:
                ans += a / den * dp[a-1][b][c]
            if b > 0:
                ans += b / den * dp[a+1][b-1][c]
            if c > 0:
                ans += c / den * dp[a][b+1][c-1]

            dp[a][b][c] = ans

    return dp[ones][twos][threes]


def main():
    n = int(input())
    dishes = [int(c) for c in input().split()]
    
    abc = [0] * 4
    for d in dishes:
        abc[d] += 1

    _, ones, twos, threes = abc
    ans = solve(ones, twos, threes, n)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
C = {1:0,2:0,3:0}
for i in range(N):
    C[A[i]] += 1
dp = [[[0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]
for k in range(1,N+1):
    dp[0][0][k] = N/k+dp[0][0][k-1]
for j in range(1,N+1):
    for k in range(N+1-j):
        if k+1<=N and k>=1:
            dp[0][j][k] = N/(j+k)+j/(j+k)*dp[0][j-1][k+1]+k/(j+k)*dp[0][j][k-1]
        elif k==N:
            dp[0][j][k] = N/(j+k)+k/(j+k)*dp[0][j][k-1]
        elif k==0:
            dp[0][j][k] = N/(j+k)+j/(j+k)*dp[0][j-1][k+1]
for i in range(1,N+1):
    for j in range(N+1-i):
        for k in range(N+1-i-j):
            if j+1<=N and j-1>=0 and k+1<=N and k-1>=0:
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]+j/N*dp[i][j-1][k+1]+k/N*dp[i][j][k-1]
            elif j==N and j-1>=0 and k+1<=N and k-1>=0:
                dp[0][j][k] = j/N*dp[i][j-1][k+1]+k/N*dp[i][j][k-1]
            elif j==N and not(j-1>=0 and k+1<=N) and k-1>=0:
                dp[0][j][k] = k/N*dp[i][j][k-1]
            elif j==N and j-1>=0 and k+1<=N and not(k-1>=0):
                dp[0][j][k] = j/N*dp[i][j-1][k+1]
            elif j+1<=N and not(j-1>=0 and k+1<=N) and k-1>=0:
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]+k/N*dp[i][j][k-1]
            elif j+1<=N and j-1>=0 and k+1<=N and not(k-1>=0):
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]+j/N*dp[i][j-1][k+1]
            elif j+1<=N and not(j-1>=0 and k+1<=N) and not(k-1>=0):
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]
print(dp[C[3]][C[2]][C[1]])