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:
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):
        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] = 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):
        for k in range(N+1):
            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]])

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    a = list(map(int, input().split()))
    c1, c2, c3 = 0, 0, 0
    for ai in a:
        if ai == 1:
            c1+=1
        elif ai == 2:
            c2 += 1
        else:
            c3 += 1
    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(c3+1)]

    for i in range(c3+1):
        for j in range(N+1):
            for k in range(N+1):
                try:
                    dp[i][j][k] = ((i/N)*dp[i-1][j+1][k]+(j/N)*dp[i][j-1][k+1]+(k/N)*dp[i][j][k-1]+1)*N / (i+j+k)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue
    print(dp[c3][c2][c1])
main()

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import Counter

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

S = sum(A)

dp = [[[0]*((S-one-two-two)//3+1) for two in range((S-one)//2+1)] for one in range(S+1)]

for one in range(S+1):
    for two in range((S-one)//2+1):
        for thr in range((S-one-two-two)//3+1):
            if one==two==thr==0:
                continue
            x = 1
            if one:
                x += one/N*dp[one-1][two][thr]
            if two:
                x += two/N*dp[one+1][two-1][thr]
            if thr:
                x += thr/N*dp[one][two+1][thr-1]
            x *= N; x /= (one+two+thr)
            dp[one][two][thr] = x

counter = Counter(A)
a,b,c = [counter[n] for n in [1,2,3]]

answer = dp[a][b][c]
print(answer)

Submission status: Wrong Answer

Solution code:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
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 = [[[0 for _ in range(n+1)] for __ in range(n+1)] for ___ in range(n+1)]

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

for x in range(n,cnt[1]+cnt[2]-2,-1):## -2?
    for y in range(x,cnt[1]-2,-1):##
        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,a=int(input()),list(map(int,input().split()))
count=[0]*3
for i in a:count[i-1]+=1
#dp[i][j][k]...寿司が1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の時の期待値
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for i in range(n+1):
  for j in range(n+1):
    for k in range(n+1):
      if i+j+k==0:continue
      #競プロフレンズ解説参照
      p=1
      if i>0:p+=dp[i-1][j][k]*(i/n)
      if j>0:p+=dp[i+1][j-1][k]*(j/n)
      if k>0:p+=dp[i][j+1][k-1]*(k/n)
      dp[i][j][k]=p/(1-((n-i-j-k)/n))
print(dp[count[0]][count[1]][count[2]])

Submission status: Wrong Answer

Solution code:
import sys

def tami(i,j,k):
  if (i == j == k == 0):
    return 0
  else:
    res = N
    if (i > 0):
      res += dp[i-1][j][k] * i
    if (j > 0):
      res += dp[i+1][j-1][k] * j
    if (k > 0):
      res += dp[i][j+1][k-1] * k
    res *= divTable[i + j + k]
    dp[i][j][k] = res
    return res
  
N = int(input())
a = list(map(float,input().split()))

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

N = 300
one = two = 0
three = N

num = max(one,two,three)

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

divTable = [1]
for i in range(1, 10000):
  divTable.append(1.0 / i)

for k in range(0, N + 1):
  for j in range(0, N - k + 1):
    for i in range(0, N - k - j + 1):
      tami(i, j, k)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#dp9 #Sushi

import sys
import bisect
input = sys.stdin.readline
def LI(): return list(map(int,input().split()))
def LIR(n): return [LI() for _ in range(n)]

def J():
    n = int(input())
    a = LI()
    a.sort()
    one = bisect.bisect_right(a,1)
    two = bisect.bisect_right(a,2) - one
    three = n - one - two

    #dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から
    #               寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[0.0]*(n+1)]*(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):
                l = i+j+k
                if l == 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/l
    print(dp[one][two][three])
if __name__ == '__main__':
    J()

Submission status: Wrong Answer

Solution code:
import sys

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))

#実家DPと気合い遷移式

def main():
    N = I()
    a = LI()
    t = [0, 0, 0]
    for ai in a:
        t[ai-1] += 1
    A, B, C = t
    E = B+C

    dp = [[0 if (not i|j) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for j in range(E+1-k):
            for i in range(N+1-k-j):
                z = i+j+k
                if (not z):
                    continue
                d = dp[i][j]
                if (i<N):
                    dp[i+1][j] += (i+1)*d/(z+1)
                if (i>0)&(j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0)&(k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
N=int(input())
A=list(map(int,raw_input().strip().split(' ')))
dic=defaultdict(int)
for i in range(4):
    dic[i]=0
for x in A:
    dic[x]+=1
start=tuple([dic[x] for x in range(4)])
    
Ans={}
def findans(a,b,c,d):
    #print(a,b,c,d)
    if (a,b,c,d) in Ans:
        return Ans[(a,b,c,d)]
    
    if a==len(A):
        return 0
    
    if a<0 or b<0 or c<0 or d<0:
        return 0
    N=len(A)
    temp1=findans(a+1,b-1,c,d)
    temp2=findans(a,b+1,c-1,d)
    temp3=findans(a,b,c+1,d-1)
    
    temp=(temp1*b+temp2*c+temp3*d)/N+1
    temp=temp/(1-a/N)
    Ans[(a,b,c,d)]=temp
    return temp
    
a,b,c,d=start
print(findans(a,b,c,d))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
#dp[i3][i2][i1]...皿を寿司の数が多い順に並べたとき、i1, i2, i3 はそれぞれ寿司の数が1, 2, 3個の皿が終わる点(スライス)。dpはそのときの期待値。
i3, i2, i1 = 0, 0, 0

for i in range(N):
	if a[i] == 3:
		i3 = i + 1
		i2 = i3
		i1 = i3
	elif a[i] == 2:
		i2 = i + 1
		i1 = i2
	elif a[i] == 1:
		i1 = i + 1
		
c1, c2, c3 = 0, 0, 0

for j3 in range(0, i3 + 1):
	for j2 in range(j3, i2 + 1):
		for j1 in range(j2, i1 + 1):
			#サイコロで3貫の皿が出たときの処理
			if j3 > 0:
				c3 = dp[j3 - 1][j2][j1]
				p3 = j3 / N
			else:
				p3 = 0
			
			#2貫
			if j2 > j3:
				c2 = dp[j3][j2 - 1][j1] 
				p2 = (j2 - j3) / N
			else:
				p2 = 0
			
			#1貫
			if j1 > j2:
				c1 = dp[j3][j2][j1 - 1]
				p1 = (j1 - j2) / N
			else:
				p1 = 0
			
			p = p3 + p2 + p1
			if p > 0 and p <= 1:
				dp[j3][j2][j1] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[i3][i2][i1])

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
I = 0
J = 0
K = 0
for i in range(N):
    if a[i] == 3:
        I += 1
    elif a[i] == 2:
        J += 1
    elif a[i] == 1:
        K += 1

dp = [[[-1 for i in range(N+1)] for i in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0

def cal(i,j,k):
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    else:
        res = 0
        if i != 0:
            res += i*cal(i-1,j+1,k)
        if j != 0:
            res += j*cal(i,j-1,k+1)
        if k != 0:
            res += k*cal(i,j,k-1)
        res += N
        res /= i+j+k
        dp[i][j][k] = res
        return res

print(cal(I,J,K))
print(-1)

Submission status: Wrong Answer

Solution code:
import fileinput

class Cache():
    def __init__(self, n_1, n_2, n_3):
        self._n_1 = n_1 + n_2 + n_3 + 1
        self._n_2 = n_2 + n_3 + 1
        self._n_3 = n_3 + 1
 
        self._arr = [-1] * (self._n_1 * self._n_2 * self._n_3)
 
    def get(self, n_1, n_2, n_3):
        return self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2]
 
    def add(self, n_1, n_2, n_3, val):
        self._arr[n_1 + n_2 * self._n_1 + n_3 * self._n_1 * self._n_2] = val


def num_turns(total, n_1, n_2, n_3, cache):
    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3):
                with_sushi = i_1 + i_2 + i_3 
                if with_sushi == 0:
                    cache.add(i_1, i_2, i_3, 0)
                    continue
                expectation = total / with_sushi
                if n_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * cache.get(i_1 - 1, i_2, i_3)
                
                if n_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * cache.get(i_1 + 1, i_2 - 1, i_3)
            
                if n_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * cache.get(i_1, i_2 + 1, i_3 - 1)
                cache.add(i_1, i_2, i_3, expectation)       
    return cache.get(n_1, n_2, n_3)

inp = fileinput.FileInput()
total = int(inp.readline())

n_1 = 0
n_2 = 0
n_3 = 0

for v in inp.readline().split(" "):
    v = int(v)
    if v == 1:
        n_1 += 1
    if v == 2:
        n_2 += 1
    if v == 3:
        n_3 += 1

print(num_turns(total, n_1, n_2, n_3, Cache(n_1, n_2, n_3)))

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import os
import sys
from collections import Counter
from io import BytesIO, IOBase

sys.stdout, stream = IOBase(), BytesIO()
sys.stdout.flush = lambda: os.write(1, stream.getvalue()) and not stream.truncate(0) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())

input = BytesIO(os.read(0, os.fstat(0).st_size)).readline


def main():
    n = int(input())
    a = Counter(int(ai) for ai in input().split())

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(input().split())
C=Counter(A)
c1,c2,c3=[C[s] for s in ('1','2','3')]
DP=[[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)] 
DP[0][0][0]=0
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i>0:
                tmp+=i*DP[k][j+1][i-1]*i
            if j>0:
                tmp+=j*DP[k+1][j-1][i]*j
            if k>0:
                tmp+=k*DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from collections import Counter
n=int(input())
A=tuple(map(int,input().split()))
C=Counter(A)
c1,c2,c3=[C[i] for i in (1,2,3)]
DP=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)] 
DP[0][0][0]=0
for i in range(c3+1):
    for j in range(c3+c2-i+1):
        for k in range(n-i-j+1):
            if i==j==k==0:
                continue
            tmp=n
            if i:
                tmp+=i*DP[k][j+1][i-1]
            if j:
                tmp+=j+DP[k+1][j-1][i]
            if k:
                tmp+=k*DP[k-1][j][i]
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    n = I()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n-2):
        dp[i+1] = min(dp[i+1],dp[i]+abs(h[i+1]-h[i]))
        dp[i+2] = min(dp[i+2],dp[i]+abs(h[i+2]-h[i]))
    dp[n-1] = min(dp[n-1],dp[n-2]+abs(h[n-1]-h[n-2]))
    print(dp[n-1])
#B
def B():
    n,k = LI()
    h = LI()
    dp = [float("inf") for i in range(n)]
    dp[0] = 0
    for i in range(n):
        for j in range(1,min(n-i,k+1)):
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
    print(dp[n-1])

#C
def C():
    n = I()
    v = LIR(n)
    dp = [[0,0,0] for i in range(n+1)]
    for i in range(n):
        dp[i+1][0] = max(dp[i+1][0],dp[i][1]+v[i][0],dp[i][2]+v[i][0])
        dp[i+1][1] = max(dp[i+1][1],dp[i][2]+v[i][1],dp[i][0]+v[i][1])
        dp[i+1][2] = max(dp[i+1][2],dp[i][0]+v[i][2],dp[i][1]+v[i][2])
    print(max(dp[n]))

#D
def D():
    n,W = LI()
    g = LIR(n)
    dp = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(W+1)[::-1]:
            w,v = g[i]
            if j >= w:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w]+v)
            else:
                dp[i+1][j] = max(dp[i+1][j],dp[i][j])
    print(max(dp[n]))
#E
def E():
    n,W = LI()
    g = LIR(n)
    V = 100000
    dp = [[float("inf") for i in range(V+1)] for j in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        for j in range(V+1)[::-1]:
            w,v = g[i]
            if j >= v:
                dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)
            else:
                dp[i+1][j] = min(dp[i+1][j],dp[i][j])

    for i in range(V+1)[::-1]:
        if dp[n][i] <= W:
            print(i)
            quit()

#F
def F():
    s = S()
    t = S()
    dp = [[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i][j]+1,dp[i+1][j],dp[i][j+1])
            else:
                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

    i = len(s)
    j = len(t)
    ans = ""
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:i -= 1
        elif dp[i][j] == dp[i][j-1]:j -= 1
        else:
            i -= 1
            j -= 1
            ans = s[i]+ans
    print(ans)
#G
def G():
    def dfs(x):
        if dp[x] != None:
            return dp[x]
        if len(v[x]) == 0:
            dp[x] = 0
            return 0
        else:
            res = 0
            for y in v[x]:
                res = max(res,dfs(y)+1)
            dp[x] = res
            return dp[x]
    n,m = LI()
    dp = [None for i in range(n)]
    v = [[] for i in range(n)]
    for i in range(m):
        x,y = LI()
        v[x-1].append(y-1)
    for i in range(n):
        dfs(i)
    print(max(dp))

#H
def H():
    h,w = LI()
    s = SR(h)
    dp = [[0 for i in range(w)] for j in range(h)]
    dp[0][0] = 1
    for i in range(h-1):
        for j in range(w-1):
            if s[i+1][j] == ".":
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= mod
            if s[i][j+1] == ".":
                dp[i][j+1] += dp[i][j]
                dp[i][j+1] %= mod
    for j in range(w-1):
        if s[h-1][j+1] == ".":
            dp[h-1][j+1] += dp[h-1][j]
            dp[h-1][j+1] %= mod
    for i in range(h-1):
        if s[i+1][w-1] == ".":
            dp[i+1][w-1] += dp[i][w-1]
            dp[i+1][w-1] %= mod
    print(dp[h-1][w-1])

#I
def J():
    n = I()
    p = list(map(float, input().split()))
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        for j in range(n+1):
            dp[i+1][j] = p[i]*dp[i][j-1]+(1-p[i])*dp[i][j]

    ans = 0
    m = math.floor(n/2)
    for i in range(m+1,n+1):
        ans += dp[n][i]
    print(ans)

#J
def K():
    n = I()
    a = LI()
    d1 = a.count(1)
    d2 = a.count(2)
    d3 = a.count(3)
    dp = [[[0 for i in range(d3+1)] for j in range(d2+d3+1)] for k in range(n+1)]
    for k in range(d3+1):
        for j in range(d2+d3+1):
            for i in range(n):
                if i+j+k:
                    l = i+j+k
                    dp[i][j][k] = n/l
                    if i:
                        dp[i][j][k] += i/l*dp[i-1][j][k]
                    if j and i < n:
                        dp[i][j][k] += j/l*dp[i+1][j-1][k]
                    if k and j < d2+d3:
                        dp[i][j][k] += k/l*dp[i][j+1][k-1]

    print(dp[d1][d2][d3])
#Solve
if __name__ == "__main__":
    K()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
a = list(map(int,input().split()))
cnt = [0,0,0] #1個の個数、二個の個数、三個の個数
for i in range(n):
    cnt[a[i]-1] += 1
    
def f(i,j,k):
    if [i,j,k] == [0,0,0]:
        return 0.0
    if dp[i][j][k] != 0.0:
        return dp[i][j][k]
    tmp = 0.0
    if i>0:
        tmp += f(i-1,j,k)*(i)/(i+j+k)
    if j>0:
        tmp += f(i+1,j-1,k)*(j)/(i+j+k)
    if k>0:
        tmp += f(i,j+1,k-1)*k/(i+j+k)
    tmp += (n)/(i+j+k)
    dp[i][j][k] = tmp
    return tmp

dp = [[[0.0 for i in range(n+1)] for j in range(n+1)] for k in range(n+1)]
 
print(f(cnt[0],cnt[1],cnt[2])-1)

Submission status: Wrong Answer

Solution code:
import sys,bisect
input = sys.stdin.readline
n = int(input())
a = tuple(map(float,input().split()))
 
c1 = a.count(1)
c2 = a.count(2)
c3 = a.count(3)
dp = [[[0.0]*(c3+1) for i in range(c2+1)] for j in range(c1+1)]
for i in range(c1,-1,-1):
    for j in range(c2,-1,-1):
        for k in range(c3,-1,-1):
            if i != c1:
                dp[i][j][k] += dp[i+1][j][k]+float(n)/float(i+1)
            if j != c2:
                dp[i][j][k] += dp[i][j+1][k]+float(n)/float(j+1)
            if k != c3:
                dp[i][j][k] += dp[i][j][k+1]+float(n)/float(k+1)
print(dp[0][0][0])

Submission status: Wrong Answer

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

memo = [ [ [-1]*(N+1)  for i in range(N+1)] for j in range(N+1) ]
memo[0][0][0] = 0
def dfs(state):
    if memo[state[0]][state[1]][state[2]] != -1:
        return memo[state[0]][state[1]][state[2]]
    ret = 0
    if state[0] > 0:
        ret += (dfs((state[0]-1,state[1],state[2]))*state[0])
    if state[1] > 0:
        ret += (dfs((state[0]+1,state[1]-1,state[2])*state[1]))
    if state[2] > 0:
        ret += (dfs((state[0],state[1]+1,state[2]-1))*state[2])
    memo[state[0]][state[1]][state[2]] = (ret + N) / sum(state)
    return memo[state[0]][state[1]][state[2]]

cur = ( a.count(1) , a.count(2) , a.count(3) )
print(dfs(cur))

Submission status: Wrong Answer

Solution code:
import numpy as np
n=int(input())

b=np.array(list(map(int,input().split())))
k1,k2,k3=n+3,np.sum(b>=2)+3,np.sum(b==3)+3
dp = np.zeros((k1,k2,k3))

for k in range(1,k3):
    for j in range(1,k2-k):
        for i in range(1,k1-j-k):
            if i+j+k>3:
                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(i,j,k,dp[i][j][k])    
        
print(dp[i][j][k])

Submission status: Wrong Answer

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

b=[0,0,0]
for i in a:
    b[i-1]+=1
k1,k2,k3=b
dp=[[[0]*(k3+1) for _ in range(k2+k3+1)] for _ in range(k1+k2+k3+1)]

for k in range(k3+1):
    for j in range(k2+k3+1-k):
        for i in range(k1+k2+k3+1-j-k):
            if not i+j+k:continue
            print(i,j,k)
            dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)

print(dp[k1][k2][k3])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())

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

dp = defaultdict(float)
dp[tuple(counts)] = 1
res = 1
increment = 1

while increment > res*10**-10:
  ndp = defaultdict(float)
  for (a,b,c,d),p in dp.items():
    ndp[(a,b,c,d)] += p*a/N
    if b > 0:
      ndp[(a+1,b-1,c,d)] += p*b/N
    if c > 0:
      ndp[(a,b+1,c-1,d)] += p*c/N
    if d > 0:
      ndp[(a,b,c+1,d-1)] += p*d/N
  dp = ndp
  increment = 1-dp[(N,0,0,0)]
  res += increment

print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**8)

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

    dp = [[[-1] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    dp[0][0][0] = 0.0

    def search(i, j, k):
        if dp[i][j][k] != -1:
            return dp[i][j][k]

        num = n
        if i > 0:
            num += search(i-1, j, k) * i
        if j > 0:
            num += search(i+1, j-1, k) * j
        if k > 0:
            num += search(i, j+1, k-1) * k
        num /= i + j + k

        dp[i][j][k] = num
        return num

    print(search(a.count(1), a.count(2), a.count(3)))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys


def main():
    sys.setrecursionlimit(10**7)
    readline = sys.stdin.buffer.readline
    N = int(readline())
    A = list(map(int, readline().split()))
    C = Counter(A)

    l, m, n = C[3], C[2], C[1]
    dp = [[[0]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
    seen = [[[False]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
    seen[0][0][0] = True

    def exval(i, j, k):
        if seen[i][j][k]:
            return dp[i][j][k]
        s = N
        if i > 0:
            s += i*exval(i-1, j+1, k)
        if j > 0:
            s += j*exval(i, j-1, k+1)
        if k > 0:
            s += k*exval(i, j, k-1)
        dp[i][j][k] = s / (i+j+k)
        seen[i][j][k] = True
        return dp[i][j][k]


    print(exval(l, m, n))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

l, m, n = C[3], C[2], C[1]
dp = [[[0]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
seen = [[[False]*(l+m+n+1) for _ in range(l+m+1)] for _ in range(l+1)]
seen[0][0][0] = True


def exval(i, j, k):
    if seen[i][j][k]:
        return dp[i][j][k]
    s = N/(i+j+k)
    if i > 0:
        s += i*exval(i-1, j+1, k)/(i+j+k)
    if j > 0:
        s += j*exval(i, j-1, k+1)/(i+j+k)
    if k > 0:
        s += k*exval(i, j, k-1)/(i+j+k)
    dp[i][j][k] = s
    seen[i][j][k] = True
    return s


print(exval(l, m, n))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



@lru_cache(maxsize=None)
def f(c1, c2, c3):
    if c1 == c2 == c3 == 0:
        return 0
    # if memo[c1][c2][c3] != -1:
    #     return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    # memo[c1][c2][c3] = ret
    return ret


N = read_int()
A = read_int_n()
# memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
# memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))



def f(c1, c2, c3):
    if min(c1, c2, c3) < 0:
        return 0
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    p1 = c1 / N
    ret += f(c1-1, c2, c3) * p1 / ip0
    p2 = c2 / N
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    p3 = c3 / N
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret

N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
print(f(A.count(1), A.count(2), A.count(3)))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap



def f(c1, c2, c3):
    if min(c1, c2, c3) < 0:
        return 0
    if memo[c1][c2][c3] != -1:
        return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    p1 = c1 / N
    p2 = c2 / N
    p3 = c3 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    ret += f(c1-1, c2, c3) * p1 / ip0
    ret += f(c1+1, c2-1, c3) * p2 / ip0
    ret += f(c1, c2+1, c3-1) * p3 / ip0
    memo[c1][c2][c3] = ret
    return ret

N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0
ca = Counter(A)
print(f(ca[1], ca[2], ca[3]))