[PYTHON] AtCoder Regular Contest 104 Rapport de participation

AtCoder Regular Contest 104 Rapport de participation

En regardant C, D et E, j'ai commencé à penser que D était le plus simple, et en chemin, j'ai remarqué un malentendu et je n'ai pu résoudre aucun d'entre eux. J'ai échoué au défi de la solution rapide et j'ai atteint environ 1900. Je suis triste car la note a baissé.

ABC179A - Plus Minus

Percer en 3 minutes, je me demande quelle distance je devrais vérifier.

A, B = map(int, input().split())

for X in range(-200, 200):
    for Y in range(-200, 200):
        if X + Y == A and X - Y == B:
            print(X, Y)
            exit()

Quand j'y pense maintenant, j'ai résolu l'équation et c'était bien que (A + B) ÷ 2 et (A-B) ÷ 2.

A, B = map(int, input().split())

print((A + B) // 2, (A - B) // 2)

ABC179B - DNA Sequence

Il a éclaté en 14 minutes. Après avoir pensé que c'était SegmentTree, j'ai pensé qu'il s'agissait d'une somme cumulative, ce qui explique pourquoi cela a pris beaucoup de temps. Avec Python, le délai est très proche.

from itertools import accumulate


def main():
    N, S = input().split()
    N = int(N)

    a = [0] * (N + 1)
    g = [0] * (N + 1)
    c = [0] * (N + 1)
    t = [0] * (N + 1)

    for i in range(N):
        x = S[i]
        if x == 'A':
            a[i + 1] = 1
        elif x == 'G':
            g[i + 1] = 1
        elif x == 'C':
            c[i + 1] = 1
        elif x == 'T':
            t[i + 1] = 1

    a = list(accumulate(a))
    g = list(accumulate(g))
    c = list(accumulate(c))
    t = list(accumulate(t))

    result = 0
    for i in range(N):
        for j in range(i + 2, N + 1, 2):
            k = a[j] - a[i]
            l = g[j] - g[i]
            m = c[j] - c[i]
            n = t[j] - t[i]
            if k == n and l == m:
                result += 1
    print(result)


main()

Peut être résolu sans somme cumulée.

def main():
    N, S = input().split()
    N = int(N)

    result = 0
    for i in range(N):
        a, b = 0, 0
        for c in S[i:]:
            if c == 'A':
                a += 1
            elif c == 'T':
                a -= 1
            elif c == 'C':
                b += 1
            elif c == 'G':
                b -= 1
            if a == 0 and b == 0:
                result += 1
    print(result)


main()

Il peut également être résolu avec * O * (* N *).

N, S = input().split()
N = int(N)

result = 0
t = {}
t[(0, 0)] = 1
a, b = 0, 0
for c in S:
    if c == 'A':
        a += 1
    elif c == 'T':
        a -= 1
    elif c == 'C':
        b += 1
    elif c == 'G':
        b -= 1
    if (a, b) in t:
        result += t[(a, b)]
        t[(a, b)] += 1
    else:
        t[(a, b)] = 1
print(result)