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é.
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)
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)
Recommended Posts