Fill at Coder

Introduction

This is a log for beginners in competitive programming to fill in atcoder problems. The main purpose is to encourage continuation by publishing logs. Since there are official problem settings and explanations, I will omit them. I will post the impressions (comments) I solved, the sites and codes that I referred to in the coating. In addition, since it will be left as a beginner log, codes other than the correct answer will also be posted. Specifically, I will post a code that matches the policy but becomes TLE as a reference.

ABC

C problem

147 - HonestOrUnkind2

Code 1. bit full search

time: O(2^N) space: O(N)

def solve(N, A, X, Y):
    ret = 0
    for i in range(2 ** N):
        tmp = []
        for j in range(N):
            if i >> j & 1:
                tmp.append(j)
        if not tmp:
            continue

        is_valid = True
        for a_idx in tmp:
            for idx in range(A[a_idx]):
                if (Y[a_idx][idx] and X[a_idx][idx] - 1 not in tmp) \
                        or (not Y[a_idx][idx] and X[a_idx][idx] - 1 in tmp):
                    is_valid = False
                    break
        ret = max(ret, len(tmp)) if is_valid else ret
    return ret

if __name__ == "__main__":
    N = int(input())
    A = []
    X, Y = [], []
    for _ in range(N):
        A.append(int(input()))
        tmp_x, tmp_y = [], []
        for _ in range(A[-1]):
            x, y = map(int, input().split())
            tmp_x.append(x)
            tmp_y.append(y)
        X.append(tmp_x)
        Y.append(tmp_y)
    print(solve(N, A, X, Y))

165 - Many Requirements

Code 1. DFS

time: O(Q_{M}H_{N})

def solve(cur_index):
    global ret
    if cur_index == N:
        tmp_sum = 0
        for i in range(Q):
            if A[b[i]] - A[a[i]] == c[i]:
                tmp_sum += d[i]
        ret = max(ret, tmp_sum)
        return
    for i in range(min(A[cur_index], M), M + 1):
        A[cur_index + 1] = i
        solve(cur_index + 1)


if __name__ == '__main__':
    N, M, Q = map(int, input().split())
    a = [0 for _ in range(Q)]
    b = [0 for _ in range(Q)]
    c = [0 for _ in range(Q)]
    d = [0 for _ in range(Q)]
    for i in range(Q):
         a[i], b[i], c[i], d[i] = map(int, input().split())
    ret = 0
    A = [1 for _ in range(N + 1)]
    solve(0)
    print(ret)

167 - Skill Up

Code 1. bit full search

time: O(M2^N) space: O(N) + O(M)

def is_valid(vals, M, X):
    for i in range(M):
        if vals[i] < X:
            return False
    return True

def solve(N, M, X, C, A):
    ret = float("inf")
    for i in range(2 ** N):
        tmp_vals = [0 for _ in range(M)]
        cost = 0
        for j in range(N):
            if (i >> j) & 1:
                cost += C[j]
                for k in range(M):
                   tmp_vals[k] += A[j][k]
        ret = min(ret, cost) if is_valid(tmp_vals, M, X) else ret
    return ret if ret != float("inf") else -1

if __name__ == '__main__':
    N, M, X = map(int, input().split())
    C = []
    A = []
    for _ in range(N):
        tmp = list(map(int, input().split()))
        C.append(tmp[0])
        A.append(tmp[1:])

    print(solve(N, M, X, C, A))

D problem

145 - Knight

--If you want to use dynamic programming, just initialize the two-line array and TLE. ――Even if you notice the binomial coefficient, if you do not speed up, it is still TLE. --TLE if you submit it in Python3 even if you speed it up as below.

I was thinking when I started to solve things like "Can I make oblique coordinates ...?", But that's impossible. By the way, speeding up the binomial coefficient seems to be a common setting.

Code 1. Naive implementation

time: O\ (X + Y) A special feature on how to find "too much divided by 1000000007"! ~ From inverse element to discrete logarithm ~

X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

n, m = map(int, [n, m])
mod = 10**9 + 7
fact = [1]
inv = [1]
for i in range(1, X + Y + 1):
    fact.append((fact[i-1] * i) % mod)
    inv.append(pow(fact[-1], mod-2, mod))

def cmb(n, r):
    return fact[n] * inv[n-r] * inv[r]

print(cmb(n+m, min(n, m)) % mod)

Code 2. Introduction of ModInt + Acceleration of inverse element calculation

When submitting, it is better to describe only the required method. time: O\ (X + Y) I implemented modint in Python

X, Y = map(int, input().split())
n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or m < 0 or not n.is_integer() or not m.is_integer():
    print(0)
    exit()

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

n, m = map(int, [n, m])
fact = [ModInt(1)]
for i in range(1, X + Y + 1):
    fact.append(fact[i-1] * i)

def cmb(n, r):
    return fact[n] / fact[n-r] / fact[r]

print(cmb(n+m, min(n, m)))

146 - Coloring Edges on Tree

Code 1. Super Stupid BFS (TLE)

Well, the idea itself is correct. Unfortunately, this does not have enough calculation time. The point is that while doing BFS, I'm searching inside ʻused_edges and ʻused_colors with the ʻin` function. Calculation orders are increasing here. The correct answer can be derived by eliminating this extra calculation. time: O(N^2)


from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = []
colors = [1 for _ in range(1, N + 1)]
used_colors = [[] for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.popleft()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].append(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.append(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)

Code 2. Improved BFS

Changed the data structures used in ʻused_edges and ʻused_colors from list to set. This changed the average order for ʻin` searches from $ O (n) $ to $ O (1) $. Time Complexity - Python Wiki time: O(N)

from collections import deque
N = int(input())
edges = [[] for _ in range(N + 1)]
for edge_idx in range(1, N):
    a, b = map(int, input().split())
    edges[a].append([edge_idx, b])
    edges[b].append([edge_idx, a])

used_edges = set()
colors = [1 for _ in range(1, N + 1)]
used_colors = [set() for _ in range(N + 1)]
stack = deque([[edges[1], 0]])
max_col = 1

while stack:
    edge_info, parent_node_idx = stack.pop()
    cur_color = 1
    for edge_idx, node_idx in edge_info:
        if edge_idx in used_edges: continue
        while cur_color in used_colors[node_idx] or cur_color in used_colors[parent_node_idx]:
            cur_color += 1
        used_colors[node_idx].add(cur_color)
        colors[edge_idx] = cur_color
        stack.append([edges[node_idx], node_idx])
        used_edges.add(edge_idx)
        max_col = max(max_col, cur_color)
        cur_color += 1

print(max_col)
for c in colors[1:]:
    print(c)

147 - Xor Sum 4

Code 1. Double loop (TLE)

Implementation using the above-mentioned ModInt. Well, it's a solution that you definitely want to try just in case, although it never passes in terms of calculation amount. Needless to say, turning a double loop is TLE. time: O(N^2)

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

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

def xor(a, b):
    return a ^ b

ret = ModInt(0)
for i in range(N - 1):
    for j in range(i + 1, N):
        ret += xor(A[i], A[j])

print(ret)
Code 2. XOR calculation (TLE) for each bit

It is a hypothetical solution, but it is TLE. time: O(Nlog(max(A)))

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def encode(N, A, max_k):
    bits = [[0, 0] for _ in range(max_k)]
    for i in range(N):
        a = format(A[i], 'b').zfill(max_k)
        for k in range(max_k):
            if int(a[k]) == 0:
                bits[max_k - 1 - k][0] += 1
            else:
                bits[max_k - 1 - k][1] += 1
    return bits

def decode(bits):
    return sum([ModInt(2 ** k * (counter[0] * counter[1])) for k, counter in enumerate(bits)])

N = int(input())
A = list(map(int, input().split()))
max_k = len(bin(max(A))) - 2

print(decode(encode(N, A, max_k)))

Code 3. XOR calculation for each bit (acceleration)

--Do not use arrays --Bit calculation directly without using a character string --Define as a constant (maximum number of digits of A) without finding the maximum value of A

You can speed up by doing this. This is nearly four times faster. time: O(Nlog(max(A)))

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        if isinstance(x, str):
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def calc(N, A, max_k):
    ret = ModInt(0)
    for k in range(max_k):
        count = 0
        for i in A:
            if i & (1 << k):
                count += 1
        ret += 2 ** k * count * (N - count)
    return ret

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

print(calc(N, A, max_k))

148 - Brick Break

Code 1. Iterate

I have nothing to say. When I read the sentence, I was a little scared that it was too simple and I overlooked something. time: O(N)


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

for n in range(N):
    if a[n] != broken + 1:
        continue
    broken += 1

if broken == 0:
    print(-1)
else:
    print(N - broken)

149 - Prediction and Restriction

Code 1. Iterate

time: O(N)


N, K = map(int, input().split())
R, S, P = map(int, input().split())
T = input()

def getScore(t, R, S, P):
    if t == 'r':
        return P
    if t == 's':
        return R
    return S

latest = [{'string': '', 'count': 0} for _ in range(K)]

ret = 0
for idx, t in enumerate(T):
    latest_idx = idx % K
    if idx + 1 <= K or t != latest[latest_idx]['string']:
        ret += getScore(t, R, S, P)
        latest[latest_idx]['string'] = t
        latest[latest_idx]['count'] = 1
        continue

    if latest[latest_idx]['count'] % 2 == 0:
        ret += getScore(t, R, S, P)
    latest[latest_idx]['count'] += 1

print(ret)

150 - Semi Common Multiple

Code 1. Iterate

I had a hard time because I overlooked it in my consideration. AtCoder ABC 150 D --Semi Common Multiple (400 points) time: O(N)

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

def solve(N, M, A):
    while A[0] % 2 == 0:
        for idx, a in enumerate(A):
            if a % 2 != 0:
                return 0
            A[idx] //= 2
        M //= 2

    for a in A:
        if a % 2 == 0:
            return 0

    cur_lcm = 1
    for a in A:
        cur_lcm = lcm(cur_lcm, a)
        if M < cur_lcm:
            return 0
    return (M // cur_lcm + 1) // 2

if __name__ == '__main__':
    N, M = map(int, input().split())
    A = list((map(int, input().split())))
    A = [a // 2 for a in A]
    print(solve(N, M, A))

151 - Maze Master

Code 1. BFS + double loop

Updating ʻused after stack.popleft () instead of stack.append` is TLE.

time: O((HW)^2)

from collections import deque

def bfs(start, maze, H, W):
    max_step = 0
    used = [[False for _ in range(W)] for _ in range(H)]
    start_x, start_y = start
    used[start_x][start_y] = True
    stack = deque([[start, 0]])
    while stack:
        (i, j), step = stack.popleft()
        if maze[i][j] == '#':
            continue
        max_step = max(max_step, step)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < H and 0 <= y < W and not used[x][y]:
                stack.append([(x, y), step + 1])
                used[x][y] = True
    return max_step

if __name__ == '__main__':
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(input()))
    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, bfs((i, j), S, H, W))
    print(ret)

152 - Handstand 2

Code 1. map generation

Did you notice that you can store all the numbers in a constant-length two-dimensional array? time: O(N)

def solve(N):
    ret = 0
    counter = [[0 for _ in range(10)] for _ in range(10)]
    for n in range(1, N + 1):
        i, j = map(int, [str(n)[0], str(n)[-1]])
        counter[i][j] += 1

    for i in range(10):
        for j in range(10):
            ret += counter[i][j] * counter[j][i]
    return ret


if __name__ == '__main__':
    N = int(input())
    ret = solve(N)
    print(ret)

156 - Bouquet

Code 1. Iterate and factorial calculation (TLE)

By the way, I don't know how to calculate factorial faster than linear order. time: O(N)

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    return fact[n] / fact[n-r] / fact[r]

def solve(n, a, b):
    fact = [ModInt(1)]
    for i in range(1, max(n, a, b) + 1):
        fact.append(fact[i-1] * i)

    return  ModInt(2**n) - 1 - cmb(fact, n, a) - cmb(fact, n, b)

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    ret = solve(n, a, b)
    print(ret)
Code 2. Improved nCr calculation

For some reason, I misunderstood the iterator of $ n-r + 1 $ ~ $ n $ as $ O (N) $ (why really?). I tried to implement the square method repeatedly, but it seems that it is not necessary because it is already adopted in the pow function in python.

time: max(O(A), O(B))

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n, r):
    mul = ModInt(1)
    for i in range(n - r + 1, n + 1):
        mul *= i
    return mul / fact[r]

def solve(n, a, b):
    fact = [ModInt(1)]
    for i in range(1, max(a, b) + 1):
        fact.append(fact[i-1] * i)
    return  ModInt(pow(2,n)) - 1 - cmb(fact, n, a) - cmb(fact, n, b)

if __name__ == '__main__':
    n, a, b = map(int, input().split())
    ret = solve(n, a, b)
    print(ret)

157 - Friend Suggestions

Code 1. Stupid Union Find (TLE)

time: O(N^2)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

def solve(uf, first_order_friends, blocked_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(list(set(uf.members(i)) - first_order_friends[i] - blocked_list[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        blocked_list[c].add(d)
        blocked_list[d].add(c)

    for ans in solve(uf, first_order_friends, blocked_list)[1:]:
        print(ans, end=' ')
Code 2. Double loop + Union Find (TLE)

Unified first_order_friends and blocked_list. At this stage, I realized that turning the double loop was the direct cause of the TLE. time: O(N^2)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x, except_list):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root and i not in except_list]

def solve(uf, first_order_friends):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(len(uf.members(i, first_order_friends[i])) - 1)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    first_order_friends = [set() for _ in range(N + 1)]
    blocked_list = [set() for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        first_order_friends[a].add(b)
        first_order_friends[b].add(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        first_order_friends[c].add(d)
        first_order_friends[d].add(c)

    for ans in solve(uf, first_order_friends)[1:]:
        print(ans, end=' ')

Code 3. Input check + UnionFind

Based on the consideration in Code 2

--Add to ʻexcept_list` only if c and d belong to the same group -Get the number of elements in the group with $ O (1) $

I changed it to.

time: O(N)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x

        self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]

def solve(uf, except_list):
    ret = [0]
    for i in range(1, N + 1):
        ret.append(uf.size(i) - 1 - len(except_list[i]))
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    except_list = [[] for _ in range(N + 1)]
    uf = UnionFind(N + 1)

    for _ in range(M):
        a, b = map(int, input().split())
        except_list[a].append(b)
        except_list[b].append(a)
        uf.union(a, b)

    for _ in range(K):
        c, d = map(int, input().split())
        if not uf.same(c, d):
            continue
        except_list[c].append(d)
        except_list[d].append(c)

    for ans in solve(uf, except_list)[1:]:
        print(ans, end=' ')

160 - Line++

Code 1. BFS

I was worried that $ 10 ^ 6 $ would be enough, but it seems to be okay. time: O(N^2)

from collections import deque

def solve(N, X, Y):
    ret = [0] * N
    already_used = [[False for _ in range(N + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        already_used[i][i] = True
        reached = [False for _ in range(N + 1)]
        reached[i] = True
        stack = deque([[i, 0]])

        while stack:
            node, step = stack.popleft()
            if 1 <= step and not already_used[i][node]:
               ret[step] += 1
            already_used[i][node], already_used[node][i] = True, True

            for x in [node + 1, node - 1]:
                if 0 < x < N + 1 and not reached[x]:
                    stack.append([x, step + 1])
                    reached[x] = True
            if node == X and not reached[Y]:
                stack.append([Y, step + 1])
                reached[x] = True
            if node == Y and not reached[X]:
                stack.append([X, step + 1])
                reached[x] = True
    return ret

if __name__ == '__main__':
    N, X, Y = map(int, input().split())
    for r in solve(N, X, Y)[1:]:
        print(r)

161 - Lunlun Number

Code 1. 3D array

When I saw the commentary, I heard a voice saying "Ah". It's too late to implement it. time: O(N)

def solve(K):
    ref = [[['0'], ['1'], ['2'], ['3'], ['4'], ['5'], ['6'], ['7'], ['8'], ['9']]]
    if K < 10:
        return ref[0][K][0]

    rest = K - 9
    i = 0
    while True:
        i += 1
        ref.append([[] for _ in range(10)])
        for j in range(10):
            if j == 0:
                for r in ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
            elif j == 9:
                for r in ref[i-1][j-1] + ref[i-1][j]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r
            else:
                for r in ref[i-1][j-1] + ref[i-1][j] + ref[i-1][j+1]:
                    ref[i][j].append(str(j) + r)
                    rest -= 1
                    if rest == 0:
                        return str(j) + r

if __name__ == '__main__':
    K = int(input())
    print(solve(K))
Code 2. deque

It was very refreshing. time: O(N)

from collections import deque

def solve(K):
    stack = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
    for _ in range(K):
        num = stack.popleft()
        one_digit = num % 10
        if one_digit % 10 == 0:
            nexts = [num * 10, num * 10 + 1]
        elif one_digit % 10 == 9:
            nexts = [num * 10 + 8, num * 10 + 9]
        else:
            nexts = [num * 10 + one_digit - 1, num * 10 + one_digit, num * 10 + one_digit + 1]

        for n in nexts:
            stack.append(n)
    return num

if __name__ == '__main__':
    K = int(input())
    print(solve(K))

163 - Sum of Large Numbers

Code 1. Japanese formula

time: O(N - K) space: O(1)

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
def sumOfArithmeticSequence(a, b):
    return (a + b) * (b - a + 1) // 2

def solve(N, K):
    ret = ModInt(0)
    for i in range(K, N + 2):
       ret += sumOfArithmeticSequence(N - i + 1, N) - sumOfArithmeticSequence(0, i - 1) + 1
    return ret


if __name__ == '__main__':
    N, K = map(int, input().split())
    print(solve(N, K))
Code 2. Cumulative sum

time: O(N) space: O(N)

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def differenceOfMaximumSumAndMinimumSum(cumulative_sum, i):
    return (cumulative_sum[-1] - cumulative_sum[-i-1]) - cumulative_sum[i - 1]

def solve(N, K):
    ret = ModInt(1)
    cumulative_sum = [0] * (N + 1)
    tmp_sum = 0
    for i in range(1, N + 1):
        tmp_sum += i
        cumulative_sum[i] = tmp_sum

    for i in range(K, N + 1):
        ret += differenceOfMaximumSumAndMinimumSum(cumulative_sum, i) + 1
    return ret


if __name__ == '__main__':
    N, K = map(int, input().split())
    print(solve(N, K))

164 - Multiple of 2019

Code 1. DP

time: O(N) space: O(N)

MOD = 2019

def solve(S):
    N = len(S)
    dp = [0 for _ in range(MOD)]
    tmp = 0
    ret = 0
    for i in range(N - 1, -1, -1):
        m = (tmp + int(S[i]) * pow(10, N - i - 1, MOD)) % MOD
        ret += dp[m]
        dp[m] += 1
        tmp = m
    ret += dp[0]
    return ret

if __name__ == "__main__":
    S = input()
    print(solve(S))

167 - Teleporter

Code 1. Floyd's cycle finding

time: O(N) space: O(N)

def solve(N, K, A):
    slow, fast = 1, 1
    is_first = True
    while is_first or slow != fast:
        is_first = False
        slow = A[slow - 1]
        fast = A[A[fast - 1] - 1]
    fast = 1
    steps_before_entering_cycle = []
    while slow != fast:
        steps_before_entering_cycle.append(fast)
        slow = A[slow - 1]
        fast = A[fast - 1]

    if K < len(steps_before_entering_cycle):
        return steps_before_entering_cycle[K]

    cycles = [slow]
    while A[slow - 1] != cycles[0]:
        cycles.append(A[slow - 1])
        slow = A[slow - 1]
    ret = cycles[(K - len(steps_before_entering_cycle)) % len(cycles)]
    return ret

if __name__ == '__main__':
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    print(solve(N, K, A))

168 - .. (Double Dots)

Code 1. BFS

time: O(N + M) space: O(N + M)

from collections import deque, defaultdict

def solve(N, M, paths):
    used = [False for _ in range(M)]
    stack = deque([1])
    ret = [[float("inf"), -1] for _ in range(N + 1)]
    ret[1] = [0, 1]

    while stack:
        cur = stack.popleft()
        nexts = paths[cur]
        for n in nexts:
            if used[n[0]]:
                continue
            used[n[0]] = True
            if ret[cur][0] + 1 < ret[n[1]][0]:
                ret[n[1]] = [ret[cur][0] + 1, cur]
                stack.append(n[1])

    print("Yes")
    for r in ret[2:]:
        print(r[1])

if __name__ == "__main__":
    N, M = map(int, input().split())
    paths = defaultdict(list)
    for idx in range(M):
        a, b = map(int, input().split())
        paths[a].append([idx, b])
        paths[b].append([idx, a])

    solve(N, M, paths)

E problem

148 - Double Factorial

Code 1. Expression transformation

time: O(logN) space: O(1)

def solve(N):
   if N < 9 or N % 2:
       return 0
   ret = 0
   N //= 2
   while N:
       ret += N // 5
       N //= 5
   return ret

if __name__ == "__main__":
    N = int(input())
    print(solve(N))

153 - Crested Ibis vs Monster

Code 1. dp

time: O(NH) space: O(H)

def solve(h, n, A, B):
    dp = [float("inf")] * h + [0]
    for i in range(h, -1, -1):
        if dp[i] == float("inf"):
            continue
        for j in range(n):
            if 0 <= i - A[j]:
                dp[i - A[j]] = min(dp[i - A[j]], dp[i] + B[j])
            else:
                dp[0] = min(dp[0], dp[i] + B[j])
    return dp[0]

if __name__ == '__main__':
    h, n = map(int, input().split())
    a = [0] * n
    b = [0] * n

    for i in range(n):
        a[i], b[i] = map(int, input().split())

    print(solve(h, n, a, b))

160 - Red and Green Apples

Code 1. Sort + Iterate

time: max(O(X + Y), O(AlogA), O(BlogB), O(ClogC))

def solve(X, Y, p, q, r):
    red_apples = sorted(p, reverse=True)[: X]
    green_apples = sorted(q, reverse=True)[: Y]
    white_apples = sorted(r)

    ret = 0
    while red_apples and green_apples:
        if not white_apples or (white_apples[-1] < red_apples[-1] and white_apples[-1] < green_apples[-1]):
            return ret + sum(red_apples) + sum(green_apples)

        ret += white_apples.pop(-1)
        if red_apples[-1] < green_apples[-1]:
            red_apples.pop(-1)
        else:
            green_apples.pop(-1)


    if not red_apples:
        while green_apples and white_apples and (green_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            green_apples.pop(-1)
        return ret + sum(green_apples)

    else:
        while red_apples and white_apples and (red_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            red_apples.pop(-1)
        return ret + sum(red_apples)

if __name__ == '__main__':
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    print(solve(X, Y, p, q, r))
Code 2. Sort

This is more concise. time: max(O(AlogA), O(BlogB), O((X + Y + C)log(X + Y + C)))

def solve(X, Y, p, q, r):
    red_apples = sorted(p, reverse=True)[: X]
    green_apples = sorted(q, reverse=True)[: Y]
    return sum(sorted(red_apples + green_apples + r, reverse=True)[: X + Y])

if __name__ == '__main__':
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    print(solve(X, Y, p, q, r))

166 - This Message Will Self-Destruct in 5s

Code 1. Iterate + Dictionary

time: O(N) sapce: O(N)

def solve(N, A):
    ret = 0
    ref = {}
    for idx, a in enumerate(A):
        ith_val = idx - a
        ret += ref[ith_val] if ith_val in ref else 0
        ref[idx + a] = ref.get(idx + a, 0) + 1
    return ret

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))

167 - Colorful Blocks

Code 1. Iterate a number of different colors

time: O(N) space: O(N)

MOD = 998244353
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def cmb(fact, n ,r):
    return ModInt(1) * fact[n] / fact[n - r] / fact[r]

def solve(N, M, K):
    fact = [ModInt(1)]
    for i in range(1, N + 1):
        fact.append(fact[i -1] * i)

    ret = ModInt(0)
    for x in range(K + 1):
        ret += cmb(fact, N - 1, x) * M * pow(M - 1, N - x - 1, MOD)
    return ret

if __name__ == '__main__':
    N, M, K = map(int, input().split())
    print(solve(N, M, K))

ARC

B problem

26-Perfect number

Code 1. Divisor enumeration

time: O(\sqrt{N}) space: O(\sqrt{N})

def getDivs(N):
    divs = []
    for i in range(1, int(N**0.5) + 1):
        if not N % i:
            divs.append(i)
            if i != N // i:
                divs.append(N // i)
    return divs

def solve(N):
    divs = getDivs(N)
    div_sum = sum(divs)
    if div_sum == 2 * N:
        return "Perfect"
    return "Abundant" if 2 * N < div_sum else "Deficient"

if __name__ == "__main__":
    N = int(input())
    print(solve(N))

AGC

A problem

43 - Range Flip Find Route

Code 1. DP

It was harder to consider than the implementation. time: O(HW) space: O(HW)

def solve(H, W, s):
    scores = [[float('inf') for _ in range(W)] for _ in range(H)]
    scores[0][0] = 0 if s[0][0] == '.' else 1

    for i in range(H):
        for j in range(W):
            for x, y in [(i - 1, j), (i, j - 1)]:
                if x < 0 or y < 0:
                    continue
                if s[i][j] == '.' or s[x][y] == '#':
                    scores[i][j] = min(scores[i][j], scores[x][y])
                else:
                    scores[i][j] = min(scores[i][j], scores[x][y] + 1)

    return scores[H - 1][W - 1]

if __name__ == '__main__':
    H, W = map(int, input().split())
    s = []
    for _ in range(H):
        s.append(list(input()))

    print(solve(H, W, s))

B problem

3 - Simplified mahjong

Code 1. Greedy algorithm

time: O(N) space: O(1)

def solve(N, A):
    ret = 0
    for idx in range(N):
        ret += A[idx] // 2
        A[idx] %= 2
        if A[idx] and idx + 1 < N and A[idx + 1]:
            ret += 1
            A[idx + 1] -= 1
    return ret

if __name__ == "__main__":
    N = int(input())
    A = [0 for _ in range(N)]
    for idx in range(N):
        A[idx] = int(input())
    print(solve(N, A))

Other

B problem

KEYENCE Programming Contest 2020 --Robot Arms

Code 1. Greedy algorithm

time: O(N) sapce: O(1)

def solve(N, data):
   ret = N
   data.sort(key=lambda x: x[0] - x[1])
   most_right = float("-inf")
   for idx, d in enumerate(data):
       l, r = d[0] - d[1], d[0] + d[1]
       if not idx or most_right <= l:
           most_right = r
           continue
       ret -= 1
       most_right = min(r, most_right)
   return ret

if __name__ == "__main__":
    N = int(input())
    data = []

    for _ in range(N):
        data.append(list(map(int, input().split())))
    print(solve(N, data))

C problem

SoundHound Inc. Programming Contest 2018 - Ordinary Beauty

For me, a complete first-time knowledge was required. I could think of a solution for $ O (m) $ with $ d = 1 $, but I couldn't generalize it and speed it up.

Code 1. Linearity of expected value

Explanation of "linearity of expected value" and summary of problems using it time: O(1) sapce: O(1)

def solve(n, m, d):
    return (m - 1) * 2 * (n - d) / n**2 if d else (m - 1) / n

if __name__ == "__main__":
    n, m, d = map(int, input().split())
    print(solve(n, m, d))

D problem

Sumitomo Mitsui Trust Bank Programming Contest 2019 --Lucky PIN

Code 1. Iterator + Dictionary

time: O(100\ N) sapce: O(100\ N) 100\ N \leq 3\times 10^6

import copy
def solve(N, S):
    single_ref = [False for _ in range(10)]
    double_ref = [{} for _ in range(N)]

    for i in range(N - 1, -1, -1):
        if i == N - 1:
            single_ref[int(S[i])] = True
            continue
        double_ref[i] = copy.deepcopy(double_ref[i + 1])
        for j in range(10):
            if not single_ref[j]:
                continue
            double_ref[i][S[i] + str(j)] = 1
        single_ref[int(S[i])] = True

    ret = {}
    for i in range(N - 1):
        for k in double_ref[i + 1].keys():
            ret[S[i] + k] = 1
    return len(ret.keys())

if __name__ == "__main__":
    N = int(input())
    S = input()
    print(solve(N, S))

Panasonic Programming Contest 2020 --String Equivalence

Code 1. DFS
def dfs(s, mx):
    if len(s) == N:
        print(s)
        return
    for c in range(ord("a"), mx + 1):
        dfs(s + chr(c), mx + 1 if c == mx else mx)

if __name__ == "__main__":
    N = int(input())
    dfs("", ord("a"))

E Problem --Colorful Hats 2

Sumitomo Mitsui Trust Bank Programming Contest 2019

Code 1. Iterate

time: O(N) space: O(N)

MOD = 10**9 + 7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def solve(N, A):
    ret = ModInt(1)
    count = [3 if not i else 0 for i in range(N + 1)]

    for a in A:
        ret *= count[a]
        if not ret:
            break
        count[a] -= 1
        count[a + 1] += 1

    return ret

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))

Recommended Posts

Fill at Coder
At Coder (2020/09/08)
At Coder # 1 at midnight
[At Coder] Output method
[At Coder] ABC128B --Guidebook
[At Coder] Acing C-XYZ Triplets
[Python] Competitive template [At Coder]
[At Coder] Beginner Contest 175 ABCD python Solution introduction
[Python] ABC133B (upper right triangle problem) [At Coder]
[At Coder] Solve the problem of binary search
[Python] ABC159D (High School Mathematics nCr) [At Coder]