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:
# ref https://qiita.com/drken/items/03c7db44ccd27820ea0d#j-%E5%95%8F%E9%A1%8C---sushi

N = int(input())
a = tuple(int(i) for i in input().split())

"""
i: 寿司が残り3個の皿の枚数
j: 寿司が残り2個の皿の枚数
k: 寿司が残り1個の皿の枚数

dp[i][j][k]: 必要な操作回数の期待値
"""
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

# 初期条件
dp[0][0][0] = 0.0

C_1 = a.count(1)
C_2 = a.count(2)
C_3 = a.count(3)

for i in range(C_3+1):
    for j in range(C_2+C_3-i+1):
        for k in range(N-i-j+1):
            if i == j == k == 0:
                continue

            tmp = N
            if i > 0:
                tmp += dp[i-1][j+1][k] * i
            if j > 0:
                tmp += dp[i][j-1][k+1] * j
            if k > 0:
                tmp += dp[i][j][k-1] * k

            dp[i][j][k] = tmp / (i+j+k)

print(dp[C_3][C_2][C_1])

Submission status: Accepted

Solution code:
def main():
	n = int(input())
	dp = [[[0] * (n - k - j + 1) for j in range(n - k + 1)] for k in range(n + 1)]
	for thr in range(n + 1):
		for two in range(n + 1):
			for one in range(n + 1):
				su = thr + two + one
				if su > n or su == 0:
					continue
				dp[thr][two][one] += n / su
				if thr:
					dp[thr][two][one] += dp[thr - 1][two + 1][one] * thr / su
				if two:
					dp[thr][two][one] += dp[thr][two - 1][one + 1] * two / su
				if one:
					dp[thr][two][one] += dp[thr][two][one - 1] * one / su
	a = b = c = 0
	for x in map(int, input().split()):
		if x == 3:
			a += 1
		elif x == 2:
			b += 1
		elif x == 1:
			c += 1
	print(dp[a][b][c])

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for thr in range(n + 1):
	for two in range(n + 1):
		for one in range(n + 1):
			su = thr + two + one
			if su > n or su == 0:
				continue
			#変更が起こるのに必要な回数の期待値
			dp[thr][two][one] += n / su
			#（各遷移先の期待値）×重み
			if thr:
				dp[thr][two][one] += dp[thr - 1][two + 1][one] * thr / su
			if two:
				dp[thr][two][one] += dp[thr][two - 1][one + 1] * two / su
			if one:
				dp[thr][two][one] += dp[thr][two][one - 1] * one / su
a = b = c = 0
for x in map(int, input().split()):
	if x == 3:
		a += 1
	elif x == 2:
		b += 1
	elif x == 1:
		c += 1
print(dp[a][b][c])

Submission status: Accepted

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==0:
            dp[0][j][0] = N/j+dp[0][j-1][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>=0 and k-1>=0:
                dp[i][j][k] = N/(i+j+k)+i/(i+j+k)*dp[i-1][j+1][k]+j/(i+j+k)*dp[i][j-1][k+1]+k/(i+j+k)*dp[i][j][k-1]
            elif j==0 and k-1>=0:
                dp[i][0][k] = N/(i+k)+i/(i+k)*dp[i-1][1][k]+k/(i+k)*dp[i][0][k-1]
            elif j-1>=0 and k==0:
                dp[i][j][0] = N/(i+j)+i/(i+j)*dp[i-1][j+1][0]+j/(i+j)*dp[i][j-1][1]
            elif j==0 and k==0:
                dp[i][j][0] = N/i+dp[i-1][1][0]
print(dp[C[3]][C[2]][C[1]])

Submission status: Accepted

Solution code:

N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

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

Submission status: Accepted

Solution code:
def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0.0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()

Submission status: Accepted

Solution code:
def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
A = LIST()
C = Counter(A)

# dp[i][j][k] := 3個残りがi個、2個残りがj個、1個残りがk個である状態にするまでの操作回数の期待値
dp = list3d(N+1, N+1, N+1, INF)
# 全て残0なら残り回数は0
dp[0][0][0] = 0.0
for i in range(N+1):
    for j in range(N+1):
        # 枝刈り
        if i+j > N:
            break
        for k in range(N+1):
            # 枝刈り
            if i+j+k > N:
                break
            if i == j == k == 0:
                continue
            # 今現在残っている皿を取る確率
            tmp = (i + j + k) / N
            # そのために必要な回数
            res = 1 / tmp
            # それ以降に必要な回数
            if i and j < N: 
                res += (i/N) / tmp * dp[i-1][j+1][k]
            if j and k < N: 
                res += (j/N) / tmp * dp[i][j-1][k+1]
            if k: 
                res += (k/N) / tmp * dp[i][j][k-1]
            dp[i][j][k] = res
print(dp[C[3]][C[2]][C[1]])

Submission status: Accepted

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

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

a,b,c = 0,0,0
for i in range(N):
    if A[i] == 1:
        a += 1
    elif A[i] == 2:
        b += 1
    else:
        c += 1

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

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

Submission status: Accepted

Solution code:
N = int(input())
def main():
    a = list(map(int, input().split()))
    d = {0:0, 1:0, 2:0, 3:0}
    for i in a:
        d[i] += 1
    d1 = d[1]
    d123 = d[1] + d[2] + d[3]
    d23 = d[2] + d[3]
    d3 = d[3]
    d2 = d[2]
    l = [[[0] * (d123 + 1) for _ in range(d23 + 1)] for _ in range(d3 + 1)]
    for i in range(d3 + 1):
        for j in range(d23 + 1):
            for k in range(d123 + 1):
                if i + j + k == 0:
                    continue
                if i + j + k > d123:
                    continue
                if i + j > d23:
                    continue
                total = i + j + k
                a = b = c = 0
                if k > 0:
                    a = k * l[i][j][k-1]
                if j > 0:
                    b = j * l[i][j-1][k + 1]
                if i > 0:
                    c = i * l[i-1][j + 1][k]
                l[i][j][k] = (a + b + c + N)/total
    print(l[d3][d2][d1])
main()

Submission status: Accepted

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

import numpy as np

N = int(readline())
A = np.array(read().split(), np.int8)

counter = np.bincount(A,minlength=4)
S = A.sum()

B = (counter[2]+counter[3])
C = counter[3]

dp = np.zeros((B+1,C+1),np.float64)

p2 = np.tile(np.arange(B+1)[:,None],(1,C+1))
p3 = np.tile(np.arange(C+1)[None,:],(B+1,1))

bc = np.arange(B+1)[:,None]*2+np.arange(C+1)[None,:]*3

for n in range(1,S+1):
    prev = dp
    one = n-bc
    p1 = np.maximum(0,one)
    dp = p1*prev + N
    dp[1:] += p2[1:]*prev[:-1]
    dp[:-1,1:] += p3[:-1,1:]*prev[1:,:-1]
    dp /= (p1+p2+p3)

answer = dp[B-C,C]
print(answer)

Submission status: Accepted

Solution code:
# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

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

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# 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]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      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] += N
      dp[i][j][k] /= (i+j+k)

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

Submission status: Accepted

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

N = int(input())
# dp[i][j][k] := 寿司が 1 つある皿が i 皿、2 つが j 皿、
# 3 つが k 皿の状態から全て食べ終えるまでの操作回数の期待値
dp = [[[float(0)] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

a = list(map(int, input().split()))
I, J, K = a.count(1), a.count(2), a.count(3)

# 小さい方から dp を埋める
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if (i+j+k) <= N:
                # 式変形はググった…
                if (i+j+k) != 0:
                    dp[i][j][k] = float(N) / float(i+j+k)
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * float(i) / float(i+j+k)
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * float(j) / float(i+j+k)
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * float(k) / float(i+j+k)
print(dp[I][J][K])

Submission status: Accepted

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

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

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

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]*1.0
            if j>0: tmp += j*dp[i+1][j-1][k]*1.0
            if k>0: tmp += k*dp[i][j+1][k-1]*1.0
            dp[i][j][k] = tmp/float(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+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[IJK[0]][IJK[1]][IJK[2]])

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
dp = [[[float(0)] * (N+1) for _ in range(N+1)] for _ in range(N+2)]
ans = float(0)
count = [0]*3
for i in a:
    count[i-1] +=1

#print(count)

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if (i+j+k)<=N:
                if (i+j+k)!=0:
                    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))

ans = dp[count[0]][count[1]][count[2]]

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#EDPC J

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
dp = [[[0.0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
x,y,z = 0,0,0
for i in range(n):
    if a[i] == 1:
        x += 1
    elif a[i] == 2:
        y += 1
    else:
        z += 1
s = x + y + z
for k in range(z+1):
    for j in range(y+z+1-k):
        for i in range(s+1-k-j):
            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(x,y,z)
print(dp[x][y][z])

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/dp/submissions/6401166
# 私が再帰関数でTLEした計算方法だが、
# 3重ループを使うと、間に合うらしい

def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        if i is 0:
            pass
        else:
            res += dp[i - 1][j][k] * i
        if j is 0:
            pass
        else:
            res += dp[i + 1][j - 1][k] * j
        if k is 0:
            pass
        else:
            res += dp[i][j + 1][k - 1] * k
        res *= divTable[i + j + k]

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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/dp/submissions/6401166
# 私が再帰関数でTLEした計算方法だが、
# 3重ループを使うと、間に合うらしい

def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        if i is not 0:
            res += dp[i - 1][j][k] * i
        if j is not 0:
            res += dp[i + 1][j - 1][k] * j
        if k is not 0:
            res += dp[i][j + 1][k - 1] * k
        res *= divTable[i + j + k]

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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/dp/submissions/6401166
# 私が再帰関数でTLEした計算方法だが、
# 3重ループを使うと、間に合うらしい

def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        res = fN
        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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/dp/submissions/6401166
# 私が再帰関数でTLEした計算方法だが、
# 3重ループを使うと、間に合うらしい

def main():
    from collections import Counter

    def tami(i, j, k):
        if i is 0 and j is 0 and k is 0:
            return

        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

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

    c = Counter(a)
    one = c[1]
    two = c[2]
    three = c[3]

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

    divTable = [1]
    for i in range(1, N * 3 + 1):
        divTable.append(1.0 / i)

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    div_tbl = [1]
    div_tbl.extend([1 / i for i in range(1, 300 * 3 + 1)])

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              * div_tbl[r1 + r2 + r3]

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
# 割り算を先に計算しておく

Submission status: Accepted

Solution code:
def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた

Submission status: Accepted

Solution code:
import collections

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

d = collections.Counter(a)
s = sum(a)
n1, n2, n3 = d[1], d[2], d[3]

dp = [[0]*(n2+n3+1) for _ in range(n3+1)]
dp[n3][n2] = 1.0
ans = 0

for i in range(s, 0, -1):
  dp2 = [[0]*(n2+n3+1) for _ in range(n3+1)]
  for i3 in range(n3, -1, -1):
    for i2 in range(min(n2+n3, (i-i3*3)//2), -1, -1):
      i1 = i-i3*3-i2*2
      i0 = n-i1-i2-i3
      if i2 < 0 or i1 < 0 or i0 < 0: continue
      e0 = n/(i1+i2+i3)
      dp2[i3][i2] += dp[i3][i2] * i1/(i1+i2+i3)
      ans += dp[i3][i2] * e0*(i1/(i1+i2+i3))
      if i2 > 0:
        dp2[i3][i2-1] += dp[i3][i2] * i2/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i2/(i1+i2+i3))
      if i3 > 0 and i2 < n2+n3:
        dp2[i3-1][i2+1] += dp[i3][i2] * i3/(i1+i2+i3)
        ans += dp[i3][i2] * e0*(i3/(i1+i2+i3))
  dp = dp2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
D = {0:0,1:0,2:0,3:0}
for a in A :
    D[a] += 1

one = D[1]
two = D[2]
three = D[3]

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

def f(c1, c2, c3) :
    res = N
    if (c1 > 0) :
        res += dp[c1-1][c2][c3] * c1
    if (c2 > 0) :
        res += dp[c1+1][c2-1][c3] * c2
    if (c3 > 0) :
        res += dp[c1][c2+1][c3-1] * c3
    
    dp[c1][c2][c3] = res/(c1 + c2 + c3)

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

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

Submission status: Accepted

Solution code:
# @author 

import sys

class JSushi:
    def solve(self):
        n = int(input())
        a = [int(_) for _ in input().split()]

        u, v, w = a.count(1), a.count(2), a.count(3)

        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 - k):
                for i in range(n + 1 - j - k):
                    if i == j == k == 0:
                        continue
                    s = i + j + k
                    x = 0
                    x += dp[i][j + 1][k - 1] * k
                    x += dp[i + 1][j - 1][k] * j
                    x += dp[i - 1][j][k] * i
                    x += n
                    x /= s
                    dp[i][j][k] = x

        print(dp[u][v][w])


solver = JSushi()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import decimal,math
from collections import Counter,defaultdict
from fractions import gcd
from bisect import bisect_right,bisect_left
decimal.getcontext().prec = 10
N=int(raw_input())
f=map(int,raw_input().split())
cc=Counter(f)
dp=[]
for i in range(N+2):
	x=[]
	for j in range(N+2):
		y=[]
		for k in range(N+2):
			y.append(0)
		x.append(y)
	dp.append(x)

# print dp[0][0]	
for k in range(0,N+1):			
	for j in range(0,N+1):			
		for i in range(0,N+1):
			if(i==0 and j==0 and k==0):
				dp[i][j][k]=0			
			elif(i+j+k<=N):
				# print (i+j+k)
				dp[i][j][k] = N
				if(i>=1):
					dp[i][j][k]+=dp[i-1][j][k]*(i)
				if(j>=1):	
					 dp[i][j][k]+=dp[i+1][j-1][k]*(j)
				if(k>=1):	 
					 dp[i][j][k]+=dp[i][j+1][k-1]*(k)
				# print dp[i][j][k],	 
				dp[i][j][k]=dp[i][j][k]/float(i+j+k)
				# print dp[i][j][k]
# print dp
print dp[cc[1]][cc[2]][cc[3]]

Submission status: Accepted

Solution code:
import collections

# 入力
N = int(input())
c = collections.Counter(list(map(int, input().split())))

# DPテーブルを初期化
dp = [[[0.0 for k in range(310)] for j in range(310)] for i in range(310)]


for k in range(0, c[3] + 1):
    for j in range(0, c[2]+c[3]-k + 1):
        for i in range(0, c[1]+c[2]+c[3]-j-k + 1):
            if i == j == k == 0:
                continue
            dp[i][j][k] = (N+i*dp[i - 1][j][k]+j *
                           dp[i + 1][j - 1][k]+k*dp[i][j + 1][k - 1])/(i+j+k)


# 答えを得て出力
print(dp[c[1]][c[2]][c[3]])