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

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

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)

# memo[i][j][k] := 1個残りがi個、2個残りがj個、3個残りがk個である状態にするまでの操作回数の期待値
memo = list3d(N+1, N+1, N+1, -1)
def rec(i, j, k):
    if memo[i][j][k] != -1:
        return memo[i][j][k]
    # 全て残0なら残り回数は0
    if i == j == k == 0:
        return 0
    # 今現在残っている皿を取る確率
    tmp = (i + j + k) / N
    # そのために必要な回数
    res = 1 / tmp
    # それ以降に必要な回数
    if i: res += (i/N) / tmp * rec(i-1, j, k)
    if j: res += (j/N) / tmp * rec(i+1, j-1, k)
    if k: res += (k/N) / tmp * rec(i, j+1, k-1)
    memo[i][j][k] = res
    return res

print(rec(C[1], C[2], C[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)


def solve(x1, x2, x3):
    if seen[x1][x2][x3]:
        return dp[x1][x2][x3]
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = solve(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = solve(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = solve(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    dp[x1][x2][x3] = (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))
    seen[x1][x2][x3] = 1
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))


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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1

seen = [[[0 for _ in range(cnt[3]+1)] for _ in range(cnt[3] + cnt[2]+1)] for _ in range(cnt[3] + cnt[2] + cnt[1]+1)]
dp = [[[0 for _ in range(cnt[3]+1)] for _ in range(cnt[3] + cnt[2]+1)] for _ in range(cnt[3] + cnt[2] + cnt[1]+1)]
print(solve(cnt[1], cnt[2], cnt[3]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)


@lru_cache(maxsize=None)
def dp(x1, x2, x3):
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = dp(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = dp(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = dp(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))


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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1
# print(dp(cnt[1], cnt[2], cnt[3]))
print(dp(0, 0, 300))

Submission status: Time Limit Exceeded

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

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

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

dp = [[[0 for k in range(N+2)] for j in range(N+2)] for i in range(N+2)]
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(N+1):
    for j in range(N+1):
        for i in range(N+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: Time Limit Exceeded

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    cnt_aa = Counter(aa)
    nc3 = cnt_aa[3]
    nc2 = cnt_aa[2]
    nc1 = cnt_aa[1]
    dp = [[[0] * (n + 1) for _ in range(nc3 + nc2 + 1)] for _ in range(nc3 + 1)]
    for c3 in range(nc3 + 1):
        for c2 in range(nc2 + nc3 - c3 + 1):
            if c3 + c2 > n: break
            for c1 in range(n + 1):
                s = c1 + c2 + c3
                if s > n: break
                if c1 > 0: dp[c3][c2][c1] += (dp[c3][c2][c1 - 1] + n / s) * c1 / s
                if c2 > 0: dp[c3][c2][c1] += (dp[c3][c2 - 1][c1 + 1] + n / s) * c2 / s
                if c3 > 0: dp[c3][c2][c1] += (dp[c3 - 1][c2 + 1][c1] + n / s) * c3 / s
    print(dp[nc3][nc2][nc1])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def main():
    N = int(input())
    a = Counter(map(int, input().split()))
    a1, a2, a3 = a.get(1, 0), a.get(2, 0), a.get(3, 0)
    a123 = a1 + a2 + a3 + 1
    u = [[0.0] * (a123 - c2) for c2 in range(a123)]
    v = [[0.0] * (a123 - c2) for c2 in range(a123)]
    t1 = 0.0
    v2 = v[0]
    for c1 in range(1, a123):
        v2[c1] = t1 = N / c1 + t1
    for c2 in range(1, a123):
        v2 = v[c2]
        for c1, t2 in zip(range(301 - c2), v[c2 - 1][1:]):
            v2[c1] = t1 = (N + c1 * t1 + c2 * t2) / (c1 + c2)

    for c3 in range(1, a3 + 1):
        u, v = v, u
        v2 = v[0]
        for c1, t3 in zip(range(a123 - c3), u[1]):
            v2[c1] = t1 = (N + c1 * t1 + c3 * t3) / (c1 + c3)
        for c2 in range(1, a123 - c3):
            v2 = v[c2]
            c23 = c2 + c3
            for c1, t2, t3 in zip(range(a123 - c3 - c2), v[c2 - 1][1:], u[c2 + 1]):
                v2[c1] = t1 = (N + c1 * t1 + c2 * t2 + c3 * t3) / (c1 + c23)

    print(v[a2][a1])
main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(100000000)
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
    print(dfs(d[1],d[2],d[3]))
@lru_cache(maxsize=None)
def dfs(a, b, c):
    if a + b + c == 0:
        return 0
    t1 = t2 = t3 = 0
    total = a + b + c
    if a > 0:
        t1 = (a/total) * dfs(a-1, b, c)
    if b > 0:
        t2 = (b/total) * dfs(a+1, b-1, c)
    if c > 0:
        t3 = (c/total) * dfs(a, b+1, c-1)
    return N/total + t1 + t2 + t3
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 7)

@lru_cache(maxsize=None)
def dp(N, c1, c2, c3):
    if c1 + c2 + c3 == 0:
        return 0
    r = N
    if c1:
        r += c1 * dp(N, c1 - 1, c2, c3)
    if c2:
        r += c2 * dp(N, c1 + 1, c2 - 1, c3)
    if c3:
        r += c3 * dp(N, c1, c2 + 1, c3 - 1)
    return r / (c1 + c2 + c3)

def main():
    N = int(input())
    a = list(map(int, input().split()))
    a = Counter(a)
    print(dp(N, a.get(1, 0), a.get(2, 0), a.get(3, 0)))


main()

Submission status: Time Limit Exceeded

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))/N
p3 = np.tile(np.arange(C+1)[None,:],(B+1,1))/N
p_rest = 1-p2-p3

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/N)
    dp = np.ones_like(prev)
    dp += p1*prev
    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: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_ls)
A = max(a_ls)
INF = 1e10
memo_ls = {k : {j : {i:0 for i in range(n+2)} for j in range(n+2)} for k in range(n+2)}
# memo_ls[i][j][k] : 1枚の皿がi,2枚がj,3枚がkの時の期待値
memo_ls[0][0][0] = 0
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i == 0 and j == 0 and k == 0:
                continue
            memo_ls[i][j][k] = ((i / n) * memo_ls[max(0, i-1)][j][k] + (j / n) * memo_ls[i+1][max(0, j-1)][k] +
                                (k / n) * memo_ls[i][j + 1][max(0, k - 1)] + 1) * (n / (i + j + k))
ct_1 = ct[1] if ct.get(1) is not None else 0
ct_2 = ct[2] if ct.get(2) is not None else 0
ct_3 = ct[3] if ct.get(3) is not None else 0
print(memo_ls[ct_1][ct_2][ct_3])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_ls)
A = max(a_ls)
INF = 1e10
memo_ls = [[[0 for i in range(n+2)] for j in range(n+2)] for k in range(n+2)]
# memo_ls[i][j][k] : 1枚の皿がi,2枚がj,3枚がkの時の期待値
memo_ls[0][0][0] = 0
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i == 0 and j == 0 and k == 0:
                continue
            memo_ls[i][j][k] = ((i / n) * memo_ls[i-1][j][k] + (j / n) * memo_ls[i+1][j-1][k] +
                                (k / n) * memo_ls[i][j + 1][k - 1] + 1) * (n / (i + j + k))
ct_1 = ct[1] if ct.get(1) is not None else 0
ct_2 = ct[2] if ct.get(2) is not None else 0
ct_3 = ct[3] if ct.get(3) is not None else 0
print(memo_ls[ct_1][ct_2][ct_3])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_ls)
A = max(a_ls)
INF = 1e10
memo_ls = [[[0 for i in range(n+2)] for j in range(n+2)] for k in range(n+2)]
# memo_ls[i][j][k] : 1枚の皿がi,2枚がj,3枚がkの時の期待値
memo_ls[0][0][0] = 0
for k in range(n+1):
    for j in range(n+1):
        for i in range(n+1):
            if i == 0 and j == 0 and k == 0:
                continue
            if k > 0:
                memo_ls[i][j][k] += (k / n) * memo_ls[i][j+1][k-1]
            if j > 0:
                memo_ls[i][j][k] += (j / n) * memo_ls[i+1][j-1][k]
            if i > 0:
                memo_ls[i][j][k] += (i / n) * memo_ls[i-1][j][k]
            memo_ls[i][j][k] = (memo_ls[i][j][k] + 1) * (n / (i + j + k))
ct_1 = ct[1] if ct.get(1) is not None else 0
ct_2 = ct[2] if ct.get(2) is not None else 0
ct_3 = ct[3] if ct.get(3) is not None else 0
print(memo_ls[ct_1][ct_2][ct_3])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1
#print(sushi)

# 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 = [[[-1.0 for _ in range(N+1)] for _ in range(sushi[2]+sushi[1]+1)] for _ in range(sushi[2]+1)] # 型推論で時間がかからないように-1ではなく-1.0とする。

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(sushi[2],sushi[1],sushi[0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1
#print(sushi)

# 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 = [[[-1.0 for _ in range(N+1)] for _ in range(sushi[2]+sushi[1]+1)] for _ in range(sushi[2]+1)] # 型推論で時間がかからないように-1ではなく-1.0とする。

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(sushi[2],sushi[1],sushi[0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# 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 = [[[-1.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(susicount[2],susicount[1],susicount[0]))

Submission status: Time Limit Exceeded

Solution code:
# Pypy3だとTLEになる。
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# 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 = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return dp[i][j][k]

print(rec(susicount[2],susicount[1],susicount[0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# 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 = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return dp[i][j][k]

print(rec(susicount[2],susicount[1],susicount[0]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)

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

susicount = [0,0,0]
for a in A:
  susicount[a-1] += 1
#print(susicount)

# 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 = [[[-1 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)]

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

print(rec(susicount[2],susicount[1],susicount[0]))

Submission status: Time Limit Exceeded

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


def main():
    N = int(input())
    # 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)]

    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):
                s = i + j + k
                if s != 0 and s <= N:
                    # 式変形はググった…
                    dp[i][j][k] = N
                    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:
                        dp[i][j][k] += dp[i][j+1][k-1] * k
                    dp[i][j][k] /= s

    print(dp[I][J][K])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N = int(input())
    S = list(map(int, input().split()))
    tmp = [0, 0, 0]  # 皿パターン: 1,2,3個の寿司が置かれている皿の数
    for s in S:
        tmp[s-1] += 1

    d = defaultdict(float)
    d[tuple(tmp)] = 1.0

    e = 0.0  # 求める期待値
    X = sum(S)  # 残りの寿司の数
    while X > 0:
        A = d.items()
        d = defaultdict(float)
        for k, v in A:
            if k == (0, 0, 0):
                continue

            x = v / sum(k)
            e += x * N

            if k[0] > 0:
                d[(k[0]-1, k[1], k[2])] += k[0] * x
            if k[1] > 0:
                d[(k[0]+1, k[1]-1, k[2])] += k[1] * x
            if k[2] > 0:
                d[(k[0], k[1]+1, k[2]-1)] += k[2] * x
        X -= 1

    print(e)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N = int(input())
    S = list(map(int, input().split()))
    tmp = [0, 0, 0]  # 皿パターン: 1,2,3個の寿司が置かれている皿の数
    for s in S:
        tmp[s-1] += 1
    d = defaultdict(int)
    d[tuple(tmp)] = 1

    e = 0  # 求める期待値
    X = sum(S)  # 残りの寿司の数
    while X > 0:
        A = d.items()
        d = defaultdict(int)
        for k, v in A:
            if k == (0, 0, 0):
                continue
            
            e += v / (sum(k)/N)  # 皿パターン数 * (寿司を食べられる期待値 := 寿司がある確率の逆数)

            if k[0] > 0:
                d[(k[0]-1, k[1], k[2])] += k[0] * v / sum(k)
            if k[1] > 0:
                d[(k[0]+1, k[1]-1, k[2])] += k[1] * v / sum(k)
            if k[2] > 0:
                d[(k[0], k[1]+1, k[2]-1)] += k[2] * v / sum(k)
        X -= 1

    print(e)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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]*(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 = 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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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]*(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 == 0: continue
            dp[i][j][k] += N
            if i>0: dp[i][j][k] += i*dp[i-1][j][k]
            if j>0: dp[i][j][k] += j*dp[i+1][j-1][k]
            if k>0: dp[i][j][k] += k*dp[i][j+1][k-1]
            dp[i][j][k]/=(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])

Submission status: Time Limit Exceeded

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]*(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 == 0: continue
            dp[i][j][k] += N
            if i-1>=0: dp[i][j][k] += i*dp[i-1][j][k]
            if j-1>=0: dp[i][j][k] += j*dp[i+1][j-1][k]
            if k-1>=0: dp[i][j][k] += k*dp[i][j+1][k-1]
            dp[i][j][k]/=(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    cnt=[0]*3
    for a in map(int,input().split()):
        cnt[a-1]+=1

    dp=[[[0]*303 for _ in range(303)] for _ in range(303)]
    def calc(i,j,k):
        if dp[i][j][k]: return dp[i][j][k]
        l=i+j+k
        if l==0: return 0
        s=n/l
        if i: s+=calc(i-1,j,k)*i/l
        if j: s+=calc(i+1,j-1,k)*j/l
        if k: s+=calc(i,j+1,k-1)*k/l
        dp[i][j][k]=s
        return dp[i][j][k]
    print(calc(*cnt))
resolve()

Submission status: Time Limit Exceeded

Solution code:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[-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
divT = [1/i for i in range(1,n+1)]
def solve(x, y, z):
    if dp[x][y][z] != -1:
        return dp[x][y][z]
    else:
        delta = n*divT[n-z-1]#3枚以上ある皿以外を引くまで
        dp[x][y][z] = 0
        if x != n:
            dp[x][y][z] += (solve(x+1,y,z) + delta) * (n-x)*divT[n-z-1]
        if y != x:
            dp[x][y][z] += (solve(x,y+1,z) + delta) * (x-y)*divT[n-z-1]#x+1,y+1ではない
        if z != y:
            dp[x][y][z] += (solve(x,y,z+1) + delta) * (y-z)*divT[n-z-1]#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:
#http://compro.tsutajiro.com/archive/180220_probability_dp.pdf
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split( )))
cnt =[0,0,0]
for i in range(n):
    cnt[3-a[i]] += 1
dp = [[[-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:
        
        hoge = 1.0 / (n - z)
        delta = n*hoge#3枚以上ある皿以外を引くまで
        dp[x][y][z] = 0
        try:
            if x != n:
                dp[x][y][z] += (solve(x+1,y,z) + delta) * (n-x)*hoge
            if y != x:
                dp[x][y][z] += (solve(x,y+1,z) + delta) * (x-y)*hoge#x+1,y+1ではない
            if z != y:
                dp[x][y][z] += (solve(x,y,z+1) + delta) * (y-z)*hoge#x+1,y+1,z+1ではない
        except:
            print(x,y,z)

        return dp[x][y][z]


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