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: Time Limit Exceeded

Solution code:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
n = int(input())
a = list(map(int, input().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[-1 for _ in range(n+2)] for __ in range(n+2)] for ___ in range(n+2)]
"""

for i in range(n,-1,-1):
    for j in range(n,i-1,-1):
        for k in range(n,j-1,-1):
            dp[k][j][i] = (dp[k-1][j+1][i] + 1) * k/n +(dp[k][j-1][i+1] + 1) * i/n +  (dp[k][j][i] + 1) * j/n
こういうインデックスが面倒なことになるから1枚、2枚、3枚でなく1枚以上、2枚以上、3枚以上食べた種類の数で管理する
"""
"""
for i in range(n-1,-1,-1):
    for j in range(n-1,i-1,-1):
        for k in range(n-1,j-1,-1):
            
            ???
            dp[k][j][i] = (dp[k+1][j+1][i] + 1) * k/n +(dp[k+1][j+1][i+1] + 1) * j/n +  (dp[k][j][i] + 1) * i/n
            → dp[k][j][i] = ((dp[k+1][j+1][i] + 1) * k/(n-i) +(dp[k+1][j+1][i+1] + 1) * j/(n-i)) +   n/i
            """


#上の方針だと追えないのでやり直し。
dp[n][n][n] = 0
def solve(x, y, z):
    if dp[x][y][z] != -1:
        return dp[x][y][z]
    else:
        delta = n/(n-z)#3枚以上ある皿以外を引くまで
        dp[x][y][z] = 0
        if x != n:
            dp[x][y][z] += (solve(x+1,y,z) + delta) * (n-x)/(n-z)
        if y != x:
                dp[x][y][z] += (solve(x,y+1,z) + delta) * (x-y)/(n-z)#x+1,y+1ではない
        if z != y:
            dp[x][y][z] += (solve(x,y,z+1) + delta) * (y-z)/(n-z)#x+1,y+1,z+1ではない

        return dp[x][y][z]


print(solve(cnt[1]+cnt[2], cnt[2] ,0))

Submission status: Time Limit Exceeded

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

count = [0, 0, 0]
for item in dishes:
    count[3-item] += 1
    
dp = {}

dp = [[[None for i in range(301)] for j in range(301)] for k in range(301)]

dp[0][0][0] = 0

def recurse(a, b, c):
    if dp[a][b][c] != None:
        return dp[a][b][c]

    expected = 0
    
    if a != 0:
        expected += a * recurse(a-1, b+1, c)
    if b != 0:
        expected += b * recurse(a, b-1, c+1)
    if c != 0:
        expected += c * recurse(a, b, c-1)
        

    expected /= a + b + c
    
    dp[a][b][c] = (N/(a+b+c)) + expected
    return dp[a][b][c]

print(recurse(count[0], count[1], count[2]))

Submission status: Time Limit Exceeded

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

count = [0, 0, 0]
for item in dishes:
    count[3-item] += 1
    
dp = {}

dp[(0, 0, 0)] = 0

def recurse(plates):    
    if plates in dp:
        return dp[plates]

    hits = 0
    expected = 0
    for i, num in enumerate(plates):
        if num == 0: continue
        hits += num

        if i == 0:
            newP = (plates[0]-1, plates[1]+1, plates[2])
        elif i == 1:
            newP = (plates[0], plates[1]-1, plates[2]+1)
        else:
            newP = (plates[0], plates[1], plates[2]-1)
            
        expected += num * recurse(newP)
        
    expected /= hits
    
    dp[plates] = (N/hits) + expected
    return dp[plates]

print(recurse(tuple(count)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
dishes = int(input().replace(" ", ""))

dp = {}

dp[0] = 0

def sortPlates(plates):
    string = list(str(plates))
    string.sort(reverse=True)
    return int("".join(string))

def recurse(plates):
    plates = sortPlates(plates)
    
    if plates in dp:
        return dp[plates]

    hits = 0
    expected = 0
    for i in range(N):
        sushi = plates // pow(10, i) % 10
        if sushi == 0: continue
        hits += 1
        expected += recurse(plates - pow(10, i))
    expected /= hits
    
    dp[plates] = (N/hits) + expected
    return dp[plates]

print(recurse(dishes))

Submission status: Time Limit Exceeded

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

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        ind = c1 * x1 + c2 * x2 + c3
        if dp[ind] != -1.0:
            return dp[ind]

        res = n
        if c1 > 0:
            res += f(c1 - 1, c2, c3) * c1
        if c2 > 0:
            res += f(c1 + 1, c2 - 1, c3) * c2
        if c3 > 0:
            res += f(c1, c2 + 1, c3 - 1) * c3
        res /= c1 + c2 + c3

        dp[ind] = res
        return res

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

    print(f(c1, c2, 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: Time Limit Exceeded

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

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        ind = c1 * x1 + c2 * x2 + c3
        if dp[ind] != -1.0:
            return dp[ind]

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 > 0 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 > 0 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 > 0 else 0)) \
              / (c1 + c2 + c3)

        dp[ind] = res
        return res

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

    print(f(c1, c2, 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次元にした

Submission status: Time Limit Exceeded

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

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        ind = c1 * x1 + c2 * x2 + c3
        if dp[ind] != -1.0:
            return dp[ind]

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

        dp[ind] = res
        return res

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

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

    x1 = 310 ** 2
    x2 = 310

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

    print(f(c1, c2, 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次元にした

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

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

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

        dp[c1][c2][c3] = res
        return res

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

    dp = tuple(
        tuple(
            [-1.0] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    dp[0][0][0] = 0.0
    # dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, 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と一致するかの比較にした

# カウントの仕方を簡素にした

Submission status: Time Limit Exceeded

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

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

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

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

        dp[c1][c2][c3] = res
        return res

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

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

    dp = tuple(
        tuple(
            [-1.0] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    dp[0][0][0] = 0.0
    # dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, 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と一致するかの比較にした

Submission status: Time Limit Exceeded

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

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        if checked[c1][c2][c3]:
            return dp[c1][c2][c3]
        checked[c1][c2][c3] = True

        res = (n \
               + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
               + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
               + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
              / (c1 + c2 + c3)

        dp[c1][c2][c3] = res
        return res

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

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

    dp = tuple(
        tuple(
            [0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    dp[0][0][0] = 0
    # dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

    checked = tuple(
        tuple(
            [False] * (c3 + 1) for _ in range(c2 + c3 + 1)
        ) for _ in range(c1 + c2 + c3 + 1))
    checked[0][0][0] = True

    print(f(c1, c2, c3))


if __name__ == '__main__':
    main()

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

# if mainの追加
# 初期値None->0.0にした
# フラグ配列checkedを追加した

Submission status: Time Limit Exceeded

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

p = [0] * 3
for i in a:
    p[3-i] += 1

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


@lru_cache(maxsize=None)
def f(c1, c2, c3):
    if c1 is 0 and c2 is 0 and c3 is 0:
        return 0

    res = (n \
           + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
           + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
           + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
          / (c1 + c2 + c3)
    return res


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

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

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = (n \
           + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
           + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
           + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
          / (c1 + c2 + c3)
    dp[c1][c2][c3] = res
    return res


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

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

dp = tuple(
    tuple(
        [None] * (c3 + 1) for _ in range(c2 + c3 + 1)
    ) for _ in range(c1 + c2 + c3 + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = (n \
           + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
           + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
           + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
          / (c1 + c2 + c3)
    dp[c1][c2][c3] = res
    return res


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

dp = tuple(
    tuple(
        [None] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

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

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = n
    if c1 != 0:
        res += f(c1 - 1, c2, c3) * c1
    if c2 != 0:
        res += f(c1 + 1, c2 - 1, c3) * c2
    if c3 != 0:
        res += f(c1, c2 + 1, c3 - 1) * c3
    res /= c1 + c2 + c3
    dp[c1][c2][c3] = res
    return res


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

dp = tuple(
    tuple(
        [None] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

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

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3, s):
    if dp[c1][c2][c3] is not None:
        return dp[c1][c2][c3]

    res = n
    if c1 != 0:
        res += f(c1 - 1, c2, c3, s - 1) * c1
    if c2 != 0:
        res += f(c1 + 1, c2 - 1, c3, s) * c2
    if c3 != 0:
        res += f(c1, c2 + 1, c3 - 1, s) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


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

dp = tuple(
    tuple(
        [None] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

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

print(f(c1, c2, c3, c1 + c2 + c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3, s):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    res = n
    if c1 != 0:
        res += f(c1 - 1, c2, c3, s - 1) * c1
    if c2 != 0:
        res += f(c1 + 1, c2 - 1, c3, s) * c2
    if c3 != 0:
        res += f(c1, c2 + 1, c3 - 1, s) * c3
    res /= s
    dp[c1][c2][c3] = res
    return res


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

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

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

print(f(c1, c2, c3, c1 + c2 + c3))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    s = c1 + c2 + c3

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


n = int(input())
a = tuple(map(int, input().split()))
c = Counter(a)

c1 = c[1]
c2 = c[2]
c3 = c[3]

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


def f(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    s = c1 + c2 + c3

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


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

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

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

Solution code:
def f(c1, c2, c3):
    if dp[c1][c2][c3] != -1:
        return dp[c1][c2][c3]

    s = c1 + c2 + c3

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


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

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

dp = tuple(
    tuple(
        [-1] * (n + 1) for _ in range(n + 1)
    ) for _ in range(n + 1))
dp[0][0][0] = 0
# dp[x][y][z]:=1,2,3個の皿がx,y,z残っているときの期待値

print(f(c1, c2, c3))

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

Submission status: Time Limit Exceeded

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]

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

def calc(i1, i2, i3):
  if i1 == i2 == i3 == 0:
    return 0
  if memo[i1][i2][i3] > 0:
    return memo[i1][i2][i3]

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  memo[i1][i2][i3] = ex
  return ex

print(calc(n1, n2, n3))

Submission status: Time Limit Exceeded

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]

memo = {(0,0,0): 0}

def calc(i1, i2, i3):
  i = (i1,i2,i3)
  if i in memo:
    return memo[i]

  ex = n/(i1+i2+i3)
  if i1 > 0:
    ex += calc(i1-1, i2, i3) * (i1/(i1+i2+i3))
  if i2 > 0:
    ex += calc(i1+1, i2-1, i3) * (i2/(i1+i2+i3))
  if i3 > 0:
    ex += calc(i1, i2+1, i3-1) * (i3/(i1+i2+i3))

  memo[(i1,i2,i3)] = ex
  return ex

print(calc(n1, n2, n3))

Submission status: Time Limit Exceeded

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]*(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)

ans = dp[one][two][three]

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[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
    
    res /= (c1 + c2 + c3)
    dp[c1][c2][c3] = res

for k in range(D[3]+1) :
    for j in range(D[2]+D[3]+1 - k) :
        for i in range(D[1]+D[2]+D[3]+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

ans = dp[D[1]][D[2]][D[3]]

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[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
    
    res /= (c1 + c2 + c3)
    dp[c1][c2][c3] = res

for k in range(D[3]+1) :
    for j in range(D[2]+D[3]+1 - k) :
        for i in range(D[1]+D[2]+D[3]+1 - (j+k)) :
            if i+j+k == 0 :
                continue
            f(i, j, k)

ans = dp[D[1]][D[2]][D[3]]

print(ans)

Submission status: Time Limit Exceeded

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

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

flag = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    if flag[c1][c2][c3] :
        return dp[c1][c2][c3]
    elif c1 + c2 + c3 == 0 :
        return 0
    else :
        flag[c1][c2][c3] = 1
        res = N / (c1 + c2 + c3)

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

ans = f(D[1], D[2], D[3])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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

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

flag = [[[0]*(N+1) for j in range(N+1)] for i in range(N+1)]

def f(c1, c2, c3) :
    if flag[c1][c2][c3] :
        return dp[c1][c2][c3]
    elif c1 + c2 + c3 == 0 :
        return 0
    else :
        flag[c1][c2][c3] = 1
        res = N / (c1 + c2 + c3)

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

ans = f(D[1], D[2], D[3])

print(ans)

Submission status: Time Limit Exceeded

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):
                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: Time Limit Exceeded

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):
                for i in range(n + 1):
                    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: Time Limit Exceeded

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

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


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

solver.solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = [int(q) for q in input().split()]
#a = list(map(int, input().split()))
On = 0
Tw = 0
Th = 0
for p in a:
	if p == 1:
		On += 1
	elif p == 2:
		Tw += 1
	else:
		Th += 1

dp = [[[0] * (n+1) for _ in [0]*(n+1)] for _ in [0]*(n+1)]
dp[0][0][0] = 0
for l in range(1, n+1):
	for k in range(Th+1):
		for j in range(min(l-k, Tw+Th)+1):
			i = l-k-j
			dp[i][j][k] += dp[i-1][j][k]*i
			if i < n:
				dp[i][j][k] += dp[i+1][j-1][k]*j
			if j < n:
				dp[i][j][k] += dp[i][j+1][k-1]*k
			dp[i][j][k] += n
			dp[i][j][k] /= l

#print(dp)
print(dp[On][Tw][Th])

Submission status: Time Limit Exceeded

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

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

def solve(one, two, three):
    if (one<0 or two<0 or three<0):
        return 0
    if (one+two+three==0):
        return 0

    if (dp[one][two][three]!=-1):
        return dp[one][two][three]

    zero = n-one-two-three

    alpha = one/n*(1+solve(one-1, two, three))+two/n*(1+solve(one+1, two-1, three))+three/n*(1+solve(one, two+1, three-1))

    #print(alpha)
    dp[one][two][three]=(alpha*n+zero)/(n-zero)
    return dp[one][two][three]

one=0
two=0
three=0
for i in range(n):
    if a[i]==1:
        one+=1
    elif a[i]==2:
        two+=1
    else:
        three+=1

print(solve(one, two, three))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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


for k in range(c[3] + 1):
    for j in range(c[2]+c[3]-k + 1):
        for i in range(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]])

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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


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

Submission status: Time Limit Exceeded

Solution code:
# 入力
N = int(input())
c = [0]*4
for a in input().split():
    c[int(a)] += 1

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


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