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:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap



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

@mt
def slv(N, A):
    ca = Counter(A)


    return f(ca[1], ca[2], ca[3])



N = read_int()
A = read_int_n()
memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
memo[0][0][0] = 0

print(slv(N, A))

Submission status: Time Limit Exceeded

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


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = INF
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    g[i][j] = 0

    return d


@mt
def slv(N, A):
    ca = Counter(A)

    memo = defaultdict(lambda: defaultdict(lambda: dict()))
    def f(c1, c2, c3):
        if c1 in memo and c2 in memo[c1] and c3 in memo[c1][c2]:
            return memo[c1][c2][c3]
        if min(c1, c2, c3) < 0:
            return 0
        if c1 == c2 == c3 == 0:
            return 0

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        memo[c1][c2][c3] = ret
        return ret
    return f(ca[1], ca[2], ca[3])


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

from functools import lru_cache
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap



def slv(N, A):
    ca = Counter(A)
    s = [
        (ca[1], ca[2], ca[3]),
        (ca[1], ca[2], ca[3])
        ]
    o = []
    done = set()
    v = set()
    while s:
        k = s.pop()
        if k not in done:
            done.add(k)
            c1, c2, c3 = k
            if c3 > 0:
                kk = (c1, c2+1, c3-1)
                if kk not in v:
                    v.add(kk)
                    s.append(kk)
                    s.append(kk)
            if c2 > 0:
                kk = (c1+1, c2-1, c3)
                if kk not in v:
                    v.add(kk)
                    s.append(kk)
                    s.append(kk)
            if c1 > 0:
                kk = (c1-1, c2, c3)
                if kk not in v:
                    v.add(kk)
                    s.append(kk)
                    s.append(kk)

        else:
            o.append(k)

    memo = defaultdict(lambda: defaultdict(dict))
    memo[0][0][0] = 0
    o.reverse()
    while o:
        c1, c2, c3 = o.pop()
        if c1 == c2 == c3 == 0:
            continue
        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        if c1 >0:
            ret += memo[c1-1][c2][c3] * p1 / ip0
        if c2 > 0:
            ret += memo[c1+1][c2-1][c3] * p2 / ip0
        if c3 > 0:
            ret += memo[c1][c2+1][c3-1] * p3 / ip0
        memo[c1][c2][c3] = ret


    return memo[ca[1]][ca[2]][ca[3]]

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from functools import lru_cache
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap



def slv(N, A):
    ca = Counter(A)
    s = [[ca[1], ca[2], ca[3]]]
    o = []
    while s:
        c1, c2, c3 = s.pop()
        o.append((c1, c2, c3))
        if c1 > 0:
            s.append((c1-1, c2, c3))
        if c2 > 0:
            s.append((c1+1, c2-1, c3))
        if c3 > 0:
            s.append((c1, c2+1, c3-1))

    memo = defaultdict(lambda: defaultdict(dict))
    memo[0][0][0] = 0
    while o:
        c1, c2, c3 = o.pop()
        if c1 == c2 == c3 == 0:
            continue
        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        if c1 >0:
            ret += memo[c1-1][c2][c3] * p1 / ip0
        if c2 > 0:
            ret += memo[c1+1][c2-1][c3] * p2 / ip0
        if c3 > 0:
            ret += memo[c1][c2+1][c3-1] * p3 / ip0
        memo[c1][c2][c3] = ret


    return memo[ca[1]][ca[2]][ca[3]]

def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

from functools import lru_cache
from collections import Counter
import sys
sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        return ret


N = read_int()
A = read_int_n()
ca = Counter(A)
print(f(ca[1], ca[2], ca[3]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


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

INF = 1 << 60


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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


def warshall_floyd(g):
    d = defaultdict(dict)
    V = list(g.keys())
    for v in g.values():
        V.extend(list(v))
    V = set(V)
    for i in V:
        for j in V:
            if i in g and j in g[i]:
                d[i][j] = g[i][j]
            else:
                d[i][j] = INF
    for k in g:
        for i in g:
            for j in g:
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    g[i][j] = 0

    return d


@mt
def slv(N, A):
    ca = Counter(A)

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

        c0 = N - (c1 + c2 + c3)
        p0 = c0 / N
        p1 = c1 / N
        p2 = c2 / N
        p3 = c3 / N
        ip0 = 1 - p0
        ret = 1 / ip0
        ret += f(c1-1, c2, c3) * p1 / ip0
        ret += f(c1+1, c2-1, c3) * p2 / ip0
        ret += f(c1, c2+1, c3-1) * p3 / ip0
        return ret
    return f(ca[1], ca[2], ca[3])



def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
from functools import lru_cache
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


N = int(input())
a = li()
I = a.count(1)
J = a.count(2)
K = a.count(3)

# dp[i][j][k]: 寿司が残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚ある状態から寿司を全てなくすのに必要な操作回数の期待値
# E(i,j,k) = E(i-1,j,k) * i / N + E(i+1,j-1,k) * j / N + E(i,j+1,k-1) * k / N + E(i,j,k) * (N-i-j-k) / N + 1
# E(i,j,k) = (E(i-1,j,k) * i + E(i+1,j-1,k) * j + E(i,j+1,k-1) * k + N) / (i+j+k)
dp = [[[-1] * (N+2) for _ in range(N+2)] for _ in range(N+2)]
dp[0][0][0] = 0
# for i in range(I+1):
#     for j in range(J+1):
#         for k in range(K+1):
#             if i > 0:
#                 dp[i][j][k] += dp[i-1][j][k] * i
#             if j > 0:
#                 dp[i][j][k] += dp[i+1][j-1][k] * j
#             if k > 0:
#                 print(i, j, k, N/k)
#                 dp[i][j][k] += dp[i][j+1][k-1] * k
#             if i + j + k > 0:
#                 dp[i][j][k] += N
#                 dp[i][j][k] /= (i + j + k)

# @lru_cache()
def E(i, j, k):
    if dp[i][j][k] != -1:
        return dp[i][j][k]
    # if i == 0 and j == 0 and k == 0:
    #     return 0
    ret = 0
    if i > 0:
        ret += E(i-1, j, k) * i
    if j > 0:
        ret += E(i+1, j-1, k) * j
    if k > 0:
        ret += E(i, j+1, k-1) * k
    ret += N
    ret /= (i + j + k)
    dp[i][j][k] = ret
    return ret

print(E(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
from functools import lru_cache
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


N = int(input())
a = li()
I = a.count(1)
J = a.count(2)
K = a.count(3)

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

# for i in range(I+1):
#     for j in range(J+1):
#         for k in range(K+1):
#             if i > 0:
#                 dp[i][j][k] += dp[i-1][j][k] * i
#             if j > 0:
#                 dp[i][j][k] += dp[i+1][j-1][k] * j
#             if k > 0:
#                 print(i, j, k, N/k)
#                 dp[i][j][k] += dp[i][j+1][k-1] * k
#             if i + j + k > 0:
#                 dp[i][j][k] += N
#                 dp[i][j][k] /= (i + j + k)

@lru_cache()
def E(i, j, k):
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i > 0:
        ret += E(i-1, j, k) * i
    if j > 0:
        ret += E(i+1, j-1, k) * j
    if k > 0:
        ret += E(i, j+1, k-1) * k
    ret += N
    ret /= (i + j + k)
    return ret

print(E(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
from functools import lru_cache
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


N = int(input())
a = li()
I = a.count(1)
J = a.count(2)
K = a.count(3)

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

# for i in range(I+1):
#     for j in range(J+1):
#         for k in range(K+1):
#             if i > 0:
#                 dp[i][j][k] += dp[i-1][j][k] * i
#             if j > 0:
#                 dp[i][j][k] += dp[i+1][j-1][k] * j
#             if k > 0:
#                 print(i, j, k, N/k)
#                 dp[i][j][k] += dp[i][j+1][k-1] * k
#             if i + j + k > 0:
#                 dp[i][j][k] += N
#                 dp[i][j][k] /= (i + j + k)

@lru_cache()
def E(i, j, k):
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i > 0:
        ret += E(i-1, j, k) * i
    if j > 0:
        ret += E(i+1, j-1, k) * j
    if k > 0:
        ret += E(i, j+1, k-1) * k
    ret += N
    ret /= (i + j + k)
    return ret

print(E(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18
sys.setrecursionlimit(10**6)
import itertools as it
import collections as cl
from collections import deque
import math
from functools import reduce
from collections import defaultdict
MOD = 10 ** 9 + 7

def li():
    return [int(x) for x in input().split()]


N = int(input())
a = li()
I = a.count(1)
J = a.count(2)
K = a.count(3)

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

# for i in range(I+1):
#     for j in range(J+1):
#         for k in range(K+1):
#             if i > 0:
#                 dp[i][j][k] += dp[i-1][j][k] * i
#             if j > 0:
#                 dp[i][j][k] += dp[i+1][j-1][k] * j
#             if k > 0:
#                 print(i, j, k, N/k)
#                 dp[i][j][k] += dp[i][j+1][k-1] * k
#             if i + j + k > 0:
#                 dp[i][j][k] += N
#                 dp[i][j][k] /= (i + j + k)

def E(i, j, k):
    if dp[i][j][k] != -INF:
        return dp[i][j][k]
    ret = 0
    if i > 0:
        ret += E(i-1, j, k) * i
    if j > 0:
        ret += E(i+1, j-1, k) * j
    if k > 0:
        ret += E(i, j+1, k-1) * k
    ret += N
    ret /= (i + j + k)
    dp[i][j][k] = ret
    return ret

print(E(I,J,K))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(float, input().split()))
dp=[[[0.0] *(N+2) for _ in range(N+2)] for _ in range(N+2)]
one,two,three=a.count(1),a.count(2),a.count(3)
for k in range(three+1):
    for j in range(N+1):
        for i in range(N+1):
            if k==0 and j==0 and i==0:
                continue
            num=N
            if i>0:
                num+=dp[i-1][j][k]*i
            if j>0:
                num+=dp[i+1][j-1][k]*j
            if k>0:
                num+=dp[i][j+1][k-1]*k
            dp[i][j][k]=num/(k+j+i)
print(dp[one][two][three])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(float, input().split()))
dp=[[[0.0] *(N+2) for _ in range(N+2)] for _ in range(N+2)]
one,two,three=a.count(1),a.count(2),a.count(3)
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if k==0 and j==0 and i==0:
                continue
            num=N
            if i>0:
                num+=dp[i-1][j][k]*i
            if j>0:
                num+=dp[i+1][j-1][k]*j
            if k>0:
                num+=dp[i][j+1][k-1]*k
            dp[i][j][k]=num/(k+j+i)
print(dp[one][two][three])

Submission status: Time Limit Exceeded

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

def main():
    n = int(input())
    alst = list(map(float, input().split()))
    dp = [[[0 for _ in range(n + 1)] for _ in range(n + 1)] for _ in range(n + 1)]
    one = alst.count(1)
    two = alst.count(2)
    three = alst.count(3)
    for k in range(n + 1):
        for j in range(n + 1):
            for i in range(n + 1):
                ijk = i + j + k
                if ijk == 0:
                    continue
                dp[i][j][k] = n / ijk
                if i != 0:
                    dp[i][j][k] += dp[i - 1][j][k] * i / ijk
                if j != 0 and i != n:
                    dp[i][j][k] += dp[i + 1][j - 1][k] * j / ijk
                if k != 0 and j != n:
                    dp[i][j][k] += dp[i][j + 1][k - 1] * k / ijk
    
    print(dp[one][two][three])


main()

Submission status: Time Limit Exceeded

Solution code:
# 期待値自体が苦手なので厳しい
# 解説AC
def main():
    import sys
    sys.setrecursionlimit(10**6)
    N = int(input())
    A = [int(i) for i in input().split()]
    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = [0]*4
    for a in A:
        c[a] += 1

    def rec(c1, c2, c3):
        if c1 == c2 == c3 == 0:
            return 0
        if dp[c1][c2][c3] != 0:
            return dp[c1][c2][c3]
        ret = N
        if c1 > 0:
            ret += rec(c1-1, c2, c3) * c1
        if c2 > 0:
            ret += rec(c1 + 1, c2-1, c3) * c2
        if c3 > 0:
            ret += rec(c1, c2 + 1, c3-1) * c3
        ret /= c1 + c2 + c3
        dp[c1][c2][c3] = ret
        return ret

    print(rec(*c[1:]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import Counter
from functools import lru_cache 

def main():
    _ = input()
    dishes = Counter(map(int, input().split()))

    @lru_cache(maxsize=None)
    def e(c_0, c_1, c_2, c_3):
        if c_1 == 0 and c_2 == 0 and c_3 == 0:
            return 0

        c_tot = c_0 + c_1 + c_2 + c_3
        div = 1 - c_0 / c_tot
        etot = 0
        etot += c_1 / c_tot * e(c_0 + 1, c_1 - 1, c_2, c_3) if c_1 > 0 else 0
        etot += c_2 / c_tot * e(c_0, c_1 + 1, c_2 - 1, c_3) if c_2 > 0 else 0
        etot += c_3 / c_tot * e(c_0, c_1, c_2 + 1, c_3 - 1) if c_3 > 0 else 0
        return (1 + etot) / div
    print(e(dishes[0], dishes[1], dishes[2], dishes[3]))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
"""
dp[i][j][k] = 寿司が1個、2個、3個残っている皿の数がそれぞれi皿、j皿、k皿であるような状態に
なるまでに必要な操作回数の期待値
dp[c_1][c_2][c_3] = 0として、dp[0][0][0]が答え
"""

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit as srl
from threading import stack_size, Thread
srl(int(1e9)+7)
stack_size(int(1e8))
 
def f(d):
    ans = 0
    if sum(d)==0:
        return 0
    try:
        return stored[(d[0],d[1],d[2])]
    except:
        pass
    ans += n/(d[0]+d[1]+d[2])
    x = d[0]/(d[0]+d[1]+d[2])
    ans += x*f([d[0]-1,d[1],d[2]])
    x = d[1]/(d[0]+d[1]+d[2])
    ans += x*f([d[0]+1,d[1]-1,d[2]])
    x = d[2]/(d[0]+d[1]+d[2])
    ans += x*f([d[0],d[1]+1,d[2]-1])
    stored[(d[0],d[1],d[2])] = ans
    return ans
 
 
n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(3)]
stored = {}
 
for i in a:
    d[i-1] +=1
 
print(f(d))

Submission status: Time Limit Exceeded

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

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

print(f(d))

Submission status: Time Limit Exceeded

Solution code:
def f(d):
    ans = 0
    if d[1]==0 and d[2]==0 and d[3]==0:
        return ans
    try:
        return stored[(d[1],d[2],d[3])]
    except:
        pass
    ans += (d[0]+d[1]+d[2]+d[3])/(d[1]+d[2]+d[3])
    if d[1]:
        x = d[1]/(d[1]+d[2]+d[3])
        ans += x*f([d[0]+1,d[1]-1,d[2],d[3]])
    if d[2]:
        x = d[2]/(d[1]+d[2]+d[3])
        ans += x*f([d[0],d[1]+1,d[2]-1,d[3]])
    if d[3]:
        x = d[3]/(d[1]+d[2]+d[3])
        ans += x*f([d[0],d[1],d[2]+1,d[3]-1])
    stored[(d[1],d[2],d[3])] = ans
    return ans


n = int(input())
a = list(map(int,input().split()))
d = [0 for i in range(4)]
stored = {}

for i in a:
    d[i] +=1

ans = 0
print(f(d))