[PYTHON] AtCoder Regular Contest 104 Teilnahmebericht

AtCoder Regular Contest 104 Teilnahmebericht

Als ich C, D und E betrachtete, begann ich zu denken, dass D das einfachste sei, und auf dem Weg bemerkte ich ein Missverständnis und konnte keines von ihnen lösen. Ich scheiterte an der Herausforderung der schnellen Lösung und erreichte ungefähr 1900. Ich bin traurig, weil die Bewertung gesunken ist.

ABC179A - Plus Minus

Brechen Sie in 3 Minuten durch und fragen Sie sich, wie viel Reichweite überprüft werden soll.

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

Jetzt, wo ich darüber nachdenke, habe ich die Gleichung gelöst und es war gut, dass (A + B) ÷ 2 und (A-B) ÷ 2.

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

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

ABC179B - DNA Sequence

Es brach in 14 Minuten durch. Nachdem ich dachte, dass es SegmentTree war, dachte ich, dass es eine kumulative Summe war, was der Grund war, warum es viel Zeit in Anspruch nahm. Mit Python ist das Zeitlimit sehr nahe.

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

Kann ohne kumulative Summe gelöst werden.

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

Es kann auch mit * O * (* N *) gelöst werden.

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)