Problem p03169 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


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


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


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


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(f(A.count(1), A.count(2), A.count(3)))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


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


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



@lru_cache(maxsize=None)
def f(c1, c2, c3):
    # if memo[c1][c2][c3] != -1:
    #     return memo[c1][c2][c3]
    c0 = N - (c1 + c2 + c3)
    p0 = c0 / N
    ip0 = 1 - p0
    ret = 1 / ip0
    if c1 > 0:
        p1 = c1 / N
        ret += f(c1-1, c2, c3) * p1 / ip0
    if c2 > 0:
        p2 = c2 / N
        ret += f(c1+1, c2-1, c3) * p2 / ip0
    if c3 > 0:
        p3 = c3 / N
        ret += f(c1, c2+1, c3-1) * p3 / ip0
    # memo[c1][c2][c3] = ret
    return ret


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(f(A.count(1), A.count(2), A.count(3)))

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.buffer.readline


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


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


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


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(f(A.count(1), A.count(2), A.count(3)))

Buggy submission (verdict: Runtime Error):
# -*- 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
    o.pop()
    while o:
        c1, c2, c3 = o.pop()
        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()

Buggy submission (verdict: Runtime Error):
# -*- 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


@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

@mt
def slv(N, A):
    ca = Counter(A)
    return f(ca[1], ca[2], ca[3])


N = read_int()
A = read_int_n()
print(slv(N, A))

Buggy submission (verdict: Runtime Error):
# -*- 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
    return d


@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

@mt
def slv(N, A):
    ca = Counter(A)
    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()