Problem:


Score : 100 points

Problem Statement

There are N dishes, numbered 1, 2, \ldots, N.
Initially, for each i (1 \leq i \leq N), Dish i has a_i (1 \leq a_i \leq 3) pieces of sushi on it.

Taro will perform the following operation repeatedly until all the pieces of sushi are eaten:

Roll a die that shows the numbers 1, 2, \ldots, N with equal probabilities, and let i be the outcome. If there are some pieces of sushi on Dish i, eat one of them; if there is none, do nothing.

Find the expected number of times the operation is performed before all the pieces of sushi are eaten.

Constraints

All values in input are integers.

1 \leq N \leq 300

1 \leq a_i \leq 3

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \ldots a_N

Output

Print the expected number of times the operation is performed before all the pieces of sushi are eaten.
The output is considered correct when the relative difference is not greater than 10^{-9}.

Sample Input 1

3
1 1 1

Sample Output 1

5.5

The expected number of operations before the first piece of sushi is eaten, is 1.
After that, the expected number of operations before the second sushi is eaten, is 1.5.
After that, the expected number of operations before the third sushi is eaten, is 3.
Thus, the expected total number of operations is 1 + 1.5 + 3 = 5.5.

Sample Input 2

1
3

Sample Output 2

3

Outputs such as 3.00, 3.000000003 and 2.999999997 will also be accepted.

Sample Input 3

2
1 2

Sample Output 3

4.5

Sample Input 4

10
1 3 2 3 3 2 3 2 1 3

Sample Output 4

54.48064457488221



Sample input:
3
1 1 1


Sample output:
5.5

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
N = int(input())

sushi = np.bincount(np.array(input().split(), dtype=np.int8),minlength=4)
total = (sushi * np.arange(4)).sum()

# a,b,c = 1個、2個、3個
# S = a + 2b + 3c：total スシ
# S の小さい方から求めていく
# S ごとには、b,c だけ持てば a が分かる

b = np.arange(N+1)[:,None]
c = np.arange(N+1)[None,:]
S_bc = 2 * b + 3 * c
dp = np.zeros((N+1,N+1))
for S in range(1,total+1):
    prev = dp
    a = S - S_bc
    dp = prev * a + N
    dp[1:] += prev[:-1] * b[1:]
    dp[:-1,1:] += prev[1:,:-1] * c[:,1:]
    dp /= (a+b+c)
    dp[a < 0] = 0

answer = dp[sushi[2],sushi[3]]
print(answer)

Submission status: Accepted

Solution code:
n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if 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[x][y][z])

Submission status: Accepted

Solution code:
def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    n = len(a)
    count_1 = a.count(1)
    count_2 = a.count(2)
    count_3 = a.count(3)

    # dp[count_1][count_2][count_3] = expectation of attempts for all dishes are cleared
    expectation_of_attempts = [[[0.0 for num_dishes_3 in range(n + 1)] for num_dishes_2 in range(n + 1)] for num_dishes_1 in range(n + 1)]

    for k in range(count_3 + 1):
        for j in range(count_2 + count_3 + 1):
            if j + k > n:
                continue
            for i in range(n + 1):
                if i + j + k > n:
                    continue
                if i == 0 and j == 0 and k == 0:
                    continue
                if expectation_of_attempts[i][j][k] > 0.0:
                    return expectation_of_attempts[i][j][k]
                a = 0.0 if i == 0 else expectation_of_attempts[i - 1][j][k]
                b = 0.0 if j == 0 else expectation_of_attempts[i + 1][j - 1][k]
                c = 0.0 if k == 0 else expectation_of_attempts[i][j + 1][k - 1]

                expectation_of_attempts[i][j][k] = (i * a + j * b + k * c + n) / (i + j + k)

    return expectation_of_attempts[count_1][count_2][count_3]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n=int(input())
dp=[[[0.0]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
a=[float(i) for i in input().split()]

p=a.count(1)
q=a.count(2)
r=a.count(3)

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

for k in range(r+1):
    for j in range(q+r-k+1):
        for i in range(n-k-j+1):
            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*=1/(i+j+k)
            dp[i][j][k]=res

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

Submission status: Accepted

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)

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

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1
    
M = t + d + m
D = [[[0] * (M + 1) for i in range(d + t + 1)] for j in range(t + 1)]

su = 0
D[t][d][m] = 1

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


for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(M - i - j, -1, -1):
      y = D[i][j][k]
      if y != 0:
        div = y * divTable[i + j + k]
        if i + j + k != 0:
          su += N * div
        if i >= 1:
          D[i - 1][j + 1][k] += i * div
        if j >= 1: 
          D[i][j - 1][k + 1] += j * div
        if k >= 1:
          D[i][j][k - 1] += k * div

print(su)

Submission status: Accepted

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      y = D[i][j][k]
      if i + j + k != 0:
        su += y * N /(i + j + k)
      if i >= 1:
        D[i - 1][j + 1][k] += y * i / (i + j + k)
      if j >= 1: 
        D[i][j - 1][k + 1] += y * j / (i + j + k)
      if k >= 1:
        D[i][j][k - 1] += y * k / (i + j + k)

print(su)

Submission status: Accepted

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) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(three+1):
        for j in range(two+three+1 - k):
            for i in range(one+two+three+1-k-j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = n*1.0
                if i > 0:
                    tmp += i*dp[i-1][j][k]
                if j > 0:
                    tmp += j*dp[i+1][j-1][k]
                if k > 0:
                    tmp += k*dp[i][j+1][k-1]
                dp[i][j][k] = tmp/(i+j+k)
    print(dp[one][two][three])
if __name__ == '__main__':
    J()

Submission status: Accepted

Solution code:
import sys

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

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 (i+j==0) else N/(i+j) for j in range(E+1)] for i in range(N+1)]

    for k in range(C+1):
        for i in range(N+1):
            dp[i][E] = 0 if (i+E+k==0) else N/(i+E+k)
        for j in range(E+1):
            for i in range(N+1):
                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) and (j<E):
                    dp[i-1][j+1] += (j+1)*d/z
                if (j>0) and (k<C):
                    dp[i][j-1] = (k+1)*d/z + N/z

    print(dp[A][B])

if __name__ == "__main__":
    main()

Submission status: Accepted

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:
				dp[j3][j2][j1] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[i3][i2][i1])

Submission status: Accepted

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] == 1:
        I += 1
    if a[i] == 2:
        J += 1
    if a[i] == 3:
        K += 1

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
for k in range(K+1):
    for j in range(J+K+1):
        if j+k > N:
            break
        for i in range(N+1):
            S = i+j+k
            if S > N:
                break
            if S == 0:
                continue
            dp[i][j][k] = (i*dp[i-1][j][k]+j*dp[i+1][j-1][k]+k*dp[i][j+1][k-1]+N)/S
print(dp[I][J][K])

Submission status: Accepted

Solution code:
import fileinput


def num_turns(total, n_1, n_2, n_3):
    _n_1 = n_1 + n_2 + n_3 + 1
    _n_2 = n_2 + n_3 + 1
    _n_3 = n_3 + 1

    _arr = [0.0] * (_n_1 * _n_2 * _n_3)

    for i_3 in range(n_3 + 1):
        for i_2 in range(n_2 + 1 + n_3 - i_3):
            for i_1 in range(n_1 + 1 + n_2 + n_3 - i_3 - i_2):
                with_sushi = i_1 + i_2 + i_3
                if with_sushi == 0:
                    continue
                expectation = total / with_sushi
                if i_1 > 0:
                    p = i_1 / with_sushi
                    expectation += p * _arr[(i_1 - 1) + i_2 * _n_1 + i_3 * _n_1 * _n_2]

                if i_2 > 0:
                    p = i_2 / with_sushi
                    expectation += p * _arr[i_1 + 1 + (i_2 - 1) * _n_1 + i_3 * _n_1 * _n_2]

                if i_3 > 0:
                    p = i_3 / with_sushi
                    expectation += p * _arr[i_1 + (i_2 + 1) * _n_1 + (i_3 - 1) * _n_1 * _n_2]
                _arr[i_1 + i_2 * _n_1 + i_3 * _n_1 * _n_2] = expectation

    return _arr[n_1 + n_2 * _n_1 + n_3 * _n_1 * _n_2]


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

Submission status: Accepted

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

dp = [[[0.0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])

Submission status: Accepted

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

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
CA = Counter(A)
SA = CA[1]
SB = CA[2]
SC = CA[3]
for c in range(SC+1):
    for b in range(SB+SC+1):
        if b + c > N:
            break
        for a in range(N+1):
            if a + b + c > N:
                break
            S = a + b + c
            if S == 0:
                continue
            dp[a][b][c] = N/S + a/S*dp[a-1][b][c]\
            +b/S*dp[a+1][b-1][c]\
            +c/S*dp[a][b+1][c - 1]

print(dp[SA][SB][SC])

Submission status: Accepted

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]
            dp[i][j][k] = (n/(i+k+j)) * res

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
a = [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**7)

ko = [0]*4
for i in a:
    ko[i] += 1

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

cc=ko[1]+ko[2]+ko[3]
ccc=ko[2]+ko[3]
for k in range(ko[3]+1):
    for j in range(ccc+1-k):
        for i in range(cc+1-k-j):
            t=i+j+k
#            print(i,j,k)
            if i != 0:
                dp[i][j][k] += (dp[i-1][j][k] + n/t)*i/t
            if j != 0 and i < n:
                dp[i][j][k] += (dp[i+1][j-1][k] + n/t)*j/t
            if k != 0 and j < n:
                dp[i][j][k] += (dp[i][j+1][k-1] + n/t)*k/t
#print(dp)
print(dp[ko[1]][ko[2]][ko[3]])

Submission status: Accepted

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

def main():
    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)]


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

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N * 1.0
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

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

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

main()

Submission status: Accepted

Solution code:
import sys

# input処理を高速化する
input = sys.stdin.readline

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

    # dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から、
    # 寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

    for k in range(three + 1):
        for j in range(two + three + 1  - k):
            for i in range(one + two + three + 1 - k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = N * 1.0
                if i > 0:
                    tmp += i * dp[i -1][j][k]
                if j > 0:
                    tmp += j * dp[i + 1][j - 1][k]
                if k > 0:
                    tmp += k * dp[i][j + 1][k -1]
                dp[i][j][k] = tmp / (i + j + k)

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


main()

Submission status: Accepted

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)]
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+=DP[k][j+1][i-1]*i
            if j>0:
                tmp+=DP[k+1][j-1][i]*j
            if k>0:
                tmp+=DP[k-1][j][i]*k
            DP[k][j][i]=tmp/(i+j+k)
print(DP[c1][c2][c3])

Submission status: Accepted

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.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-k):
            for i in range(n+1-k-j):
                l = i+j+k
                if l == 0:continue
                res = n
                if i:
                    res += i*dp[i-1][j][k]
                if j:
                    res += j*dp[i+1][j-1][k]
                if k:
                    res += k*dp[i][j+1][k-1]
                dp[i][j][k] = res/l
    print(dp[d1][d2][d3])
#Solve
if __name__ == "__main__":
    K()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = tuple(map(int,input().split()))
c1 = a.count(1)
c2 = a.count(2)
c3 = a.count(3)

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

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[0] * (a + b + c - i - j + 1) for j in range(a + b - i + 1)] for i in range(a + 1)]

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

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
a, b, c = [C[i] for i in range(3, 0, -1)]

DP = [[[-1] * (a + b + c + 1) for i in range(a + b + 1)] for j in range(a + 1)]
DP[0][0][0] = 0

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

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

Submission status: Accepted

Solution code:
N = int(input())
b = [0, 0, 0]
for i in map(int, input().split()):
    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)]
dp[0][0][0] = 0

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

Solution code:
def main():
    N = int(input())
    c = [0] * 4
    for num in map(int, input().split()):
        c[num] += 1
    dp = [[[0] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
    for i3 in range(c[3]+1):
        for i2 in range(c[2]+c[3]-i3+1):
            for i1 in range(c[1]+c[2]+c[3]-i2-i3+1):
                try:
                    dp[i1][i2][i3] = (i1 * dp[i1-1][i2][i3] +
                                      i2 * dp[i1+1][i2-1][i3] +
                                      i3 * dp[i1][i2+1][i3-1] +
                                      N) / (i1+i2+i3)
                except IndexError:
                    continue
                except ZeroDivisionError:
                    continue

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


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

n1 = 0
n2 = 0
n3 = 0
for ai in a:
    if ai == 1:
        n1 += 1
    elif ai == 2:
        n2 += 1
    else:
        n3 += 1

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

            nr = float(n - i - j - k)
            dp[i][j][k] = nr / n
            if i > 0:
                dp[i][j][k] += (1.0 + dp[i - 1][j + 1][k]) * i / n
            if j > 0:
                dp[i][j][k] += (1.0 + dp[i][j - 1][k + 1]) * j / n
            if k > 0:
                dp[i][j][k] += (1.0 + dp[i][j][k - 1]) * k / n
            if n > i + j + k:
                dp[i][j][k] /= (1 - nr / n)
print(dp[n3][n2][n1])

Submission status: Accepted

Solution code:
from __future__ import division

n = input()
a = map(int, raw_input().strip().split())

dp = [[[0 for i in xrange(n + 1)] for j in xrange(n + 1)] for k in xrange(n + 1)]

r = [0, 0, 0, 0]
for ai in a: r[ai] += 1

for r3 in xrange(n + 1):
    for r2 in xrange(n + 1):
        for r1 in xrange(n + 1):
            if r1 == r2 and r2 == r3 and r3 == 0: continue
            if r1 + r2 + r3 > n: break
            s = r1 + r2 + r3
            dp[r1][r2][r3] = n / s
            if r1 >= 1: dp[r1][r2][r3] += ((r1 * dp[r1 - 1][r2][r3]) / s)
            if r2 >= 1: dp[r1][r2][r3] += ((r2 * dp[r1 + 1][r2 - 1][r3]) / (s))
            if r3 >= 1: dp[r1][r2][r3] += ((r3 * dp[r1][r2 + 1][r3 - 1]) / (s))
            
ans = dp[r[1]][r[2]][r[3]]
print "{0:.10f}".format(ans)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/dp/tasks/dp_j
"""
from sys import stdin
input = stdin.readline

n = int(input())
c = [0] * 4
l = list(map(int, input().split()))

for i in l:
    c[i] += 1

dp = [[[0.0] * (n + 1) for i in range(n + 1)] for j in range(n + 1)]
dp[0][0][0] = 0
for n3 in range(0, c[3] + 1):
    for n2 in range(0, c[2] + c[3] - n3 + 1):
        for n1 in range(0, n-c[0]- n3 - n2 + 1):
            if n1 == n2 == n3 == 0:
                continue
            temp = n
            if n1 != 0:
                # temp += n1 * dp[(n1 - 1, n2, n3)]
                temp += n1*dp[n1 - 1][n2][n3]
            if n2 != 0:
                # temp += n2 * dp[(n1 + 1, n2 - 1, n3)]
                temp += n2*dp[n1 + 1][n2 - 1][n3]
            if n3 != 0:
                # temp += n3 * dp[(n1, n2 + 1, n3 - 1)]
                temp += n3*dp[n1][n2 + 1][n3 - 1]
            dp[n1][n2][n3] = temp / (n1 + n2 + n3)

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

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
# FROM : https://atcoder.jp/contests/dp/submissions/4017206
# N,M = map(int, input().split())
N = int(input())
from collections import Counter
a = Counter( map(int, input().split()))


#1,2,3
A,B,C = (a[i] for i in range(1,4))

# dpA,B,C

# dp = [ [ [0] * (C+1) 
#            for _ in range(B+C+1)
#        ]
#            for _ in range(A+B+C+1) 
#      ]

dp = [ [ [0]*(A+B+C+1) for _ in range(B+C+1)]
        for _ in range(C+1) ] 

for c in range(C+1):
    for b in range(B+C+1-c):
        for a in range(A+B+C+1-b-c):
            # if a == b == c == 0:
            #     continue

            try: 
                dp[c][b][a] = (
                        ( a * ( dp[c][b][a-1]   if a else 0)  ) + 
                        ( b * ( dp[c][b-1][a+1] if b else 0)  ) +
                        ( c * ( dp[c-1][b+1][a] if c else 0)  ) + N 
                       ) / ( a+b+c ) 
                # dp[a][b][c] = (
                #         ( a * ( dp[a-1][b][c]   if a else 0)  ) + 
                #         ( b * ( dp[a+1][b-1][c] if b else 0)  ) +
                #         ( c * ( dp[a][b+1][c-1] if c else 0)  ) + N 
                #        ) / ( a+b+c ) 
            except:
                continue

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])