Looking at C, D, E, I started thinking that D was the easiest, and on the way I noticed a misunderstanding and I could not solve any of them. I'm sad because the rating has dropped because it's gone.
Break through in 3 minutes. While wondering how much range should be checked.
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()
When I think about it now, I solved the equation and it was good that (A + B) ÷ 2 and (A-B) ÷ 2.
A, B = map(int, input().split())
print((A + B) // 2, (A - B) // 2)
It broke through in 14 minutes. After thinking that it was a SegmentTree, I thought that it was a cumulative sum, which was the reason why it took a lot of time.
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()
Can be solved without cumulative sum.
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()
It can also be solved with * 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