[PYTHON] Füllen Sie bei Coder

Einführung

Dies ist ein Protokoll für Anfänger in der Wettbewerbsprogrammierung, um Probleme mit dem Codierer zu beheben. Der Hauptzweck besteht darin, die Fortsetzung durch Veröffentlichung von Protokollen zu fördern. Da es offizielle Problemeinstellungen und Erklärungen gibt, werde ich sie weglassen. Ich werde die Eindrücke (Kommentare) veröffentlichen, die ich gelöst habe, die Stellen und Codes, auf die ich mich in der Beschichtung bezogen habe. Da es als Anfängerprotokoll hinterlassen wird, werden außerdem andere Codes als die richtige Antwort veröffentlicht. Insbesondere werde ich einen Code veröffentlichen, der der Richtlinie entspricht, aber als Referenz zu TLE wird.

ABC

C Problem

147 - HonestOrUnkind2

Code 1. Bit vollständige Suche

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 vollständige Suche

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

Ich dachte, als ich anfing, Dinge wie "Kann ich schräge Koordinaten machen ...?" Zu lösen, aber das ist unmöglich. Übrigens scheint es eine übliche Einstellung zu sein, den Binomialkoeffizienten zu beschleunigen.

Code 1. Naive Implementierung

time: O\ (X + Y) Eine Besonderheit, wie man "zu viel geteilt durch 1000000007" findet! ~ Vom inversen Element zum diskreten Logarithmus ~

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. Einführung von ModInt + Beschleunigung der inversen Elementberechnung

Bei der Einreichung ist es besser, nur die erforderliche Methode zu beschreiben. time: O\ (X + Y) Ich habe Modint in Python implementiert

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 dummes BFS (TLE)

Nun, die Idee selbst ist richtig. Leider hat dies nicht genügend Rechenzeit. Der Punkt ist, dass wir während der Ausführung von BFS in "used_edges" und "used_colors" mit der Funktion "in" suchen. Die Rechenaufträge nehmen hier zu. Die richtige Antwort kann abgeleitet werden, indem diese zusätzliche Berechnung eliminiert wird. 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. Verbessertes BFS

Die in used_edges und used_colors verwendete Datenstruktur wurde von list in set geändert. Dies änderte die durchschnittliche Reihenfolge der Suchvorgänge um "in" von $ O (n) $ auf $ 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. Doppelschleife (TLE)

Implementierung mit dem oben genannten "ModInt". Nun, es ist eine Lösung, die Sie auf jeden Fall für alle Fälle ausprobieren möchten, obwohl sie in Bezug auf den Berechnungsbetrag nie erfolgreich ist. Es ist unnötig zu erwähnen, dass das Drehen der Doppelschleife TLE ist. 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-Berechnung (TLE) für jedes Bit

Es ist eine hypothetische Lösung, aber es ist 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-Berechnung für jedes Bit (Beschleunigung)

Sie können dies beschleunigen. Das ist fast viermal schneller. 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. Kursiv schreiben

Ich habe nichts zu sagen. Als ich die Bedeutung las, hatte ich ein wenig Angst, dass es zu einfach war und ich etwas übersehen habe. 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. Kursiv schreiben

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. Kursiv schreiben

Ich hatte es schwer, weil ich es in meiner Überlegung übersehen habe. AtCoder ABC 150 D - Semi Common Multiple (400 Punkte) 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 + Doppelschleife

Das Aktualisieren von "used" nach "stack.popleft ()" anstelle von "stack.append" ist 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. Kartengenerierung

Merkst du, dass du alle Zahlen in einem zweidimensionalen Array konstanter Länge speichern kannst? 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. Kursiv und multipliziert (TLE)

Ich weiß übrigens nicht, wie ich den Multiplikator schneller als die lineare Ordnung berechnen soll. 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. Verbesserte nCr-Berechnung

Aus irgendeinem Grund habe ich falsch verstanden, dass die Iteration von $ n-r + 1 $ ~ $ n $ $ O (N) $ war (warum wirklich?). Ich habe wiederholt versucht, die Quadratmethode zu implementieren, aber es scheint, dass sie für Python nicht erforderlich ist, da sie bereits von der pow-Funktion übernommen wurde.

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. Dumme 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. Doppelschleife + Union Find (TLE)

Vereinheitlichte first_order_friends und blockierte_liste. Zu diesem Zeitpunkt wurde mir klar, dass das Drehen der Doppelschleife die direkte Ursache für TLE war. 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. Eingabeprüfung + UnionFind

Basierend auf der Überlegung in Code 2

Ich habe es geändert in.

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

Ich hatte Angst, dass $ 10 ^ 6 $ ausreichen würden, aber es scheint in Ordnung zu sein. 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

Als ich den Kommentar sah, hörte ich eine Stimme, die "Ah" sagte. Es ist zu spät, um es umzusetzen. 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

Es war sehr erfrischend. 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. Japanische Formel

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. Kumulative Summe

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. Floyds Zyklusfindung

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. Ausdruckstransformation

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. Sortieren + Iterieren

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. Sortieren

Dies ist prägnanter. 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. Kursiv + Wörterbuch

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. Die Anzahl der verschiedenen Farben kursieren

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-Vollständige Nummer

Code 1. Aufzählungen aufzählen

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

Ein Problem

43 - Range Flip Find Route

Code 1. DP

Es war schwieriger zu überlegen als die Implementierung. 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. Gierige Methode

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

Andere

B Problem

Keyence Programming Contest 2020 - Roboterarme

Code 1. Gierige Methode

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

Für mich war ein vollständiges Erstwissen erforderlich. Ich könnte mir eine Lösung für $ O (m) $ mit $ d = 1 $ vorstellen, aber ich konnte sie nicht verallgemeinern und beschleunigen.

Code 1. Erwartungswertlinearität

Erklärung der "Linearität der erwarteten Werte" und Zusammenfassung der Probleme bei deren Verwendung 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

Programmierwettbewerb der Sumitomo Mitsui Trust Bank 2019 - GlückspIN

Code 1. Kursiv + Wörterbuch

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 Programmierwettbewerb 2020 - String-Äquivalenz

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 - Farbige Hüte 2

Programmierwettbewerb der Sumitomo Mitsui Trust Bank 2019

Code 1. Kursiv schreiben

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

Füllen Sie bei Coder
Bei Coder (2020/09/08)
Bei Coder # 1 um Mitternacht
[At Coder] Ausgabemethode
[Bei Coder] ABC128B - Handbuch
[Bei Coder] Acing C-XYZ Triplets
[Python] Competitive Pro-Vorlage [At Coder]
[At Coder] Anfängerwettbewerb 175 Einführung in die ABCD-Python-Lösung
[Python] ABC133B (Problem mit dem oberen rechten Dreieck) [At Coder]
[Bei Coder] Lösen Sie das Problem der Dichotomie
[Python] ABC159D (High School Mathematics nCr) [Bei Coder]