[PYTHON] AtCoder Beginner Contest 043 Review of past questions

Time required

Problem A

Just find the total.

answerA.py

n=int(input())
print(n*(n+1)//2)

B problem

Just add 0,1 and remove with B.

answerB.py

ans=""
s=input()
for i in s:
    if i=="0":
        ans+="0"
    elif i=="1":
        ans+="1"
    else:
        if i!=[]:
            ans=ans[:-1]
print(ans)

C problem

In the case of -100 or less and 100 or more, -100 and 100 are the minimum, respectively, so search all the values that change from -100 to 100.

answerC.py

n=int(input())
a=[int(i) for i in input().split()]
ans=10000000000000
for i in range(-100,101):
    ans_sub=0
    for j in range(n):
        ans_sub+=(a[j]-i)**2
    ans=min(ans,ans_sub)
print(ans)

D problem

First, unbalanced strings have the same majority. Furthermore, (** during the experiment **) ** I found that the unbalanced substring is hidden in the unbalanced string **. For example, the sample needed contains unbalanced substrings such as nee and ede, but ee in nee is also an unbalanced substring. Therefore, since it is only necessary to output one unbalanced substring, I thought about what the smallest substring is. First, for a substring of length 2, it becomes an unbalanced substring when the two characters are the same. Next, it can be seen that two characters are also included in the substring of length 3, and if the characters are continuous, the substring of length 2 will also be an unbalanced substring. I will. In other words, assuming that the smallest unbalanced substring was present, we can see that the smallest is likely to have the same character at both ends (as shown by reductio ad absurdum if it doesn't have the same character). Furthermore, it is intuitive that this unbalanced string will not be the smallest unbalanced string if the same characters at both ends are present in the unbalanced string. Therefore, it is sufficient if there is an unbalanced character string (pattern such as aa or aba) that has the same character at both ends and has a length of 2 or more, and this should be output. Also, ** the majority of the characters are the same, so the same characters are always "adjacent" or "every other" **, which supports this intuition. Furthermore, if there is no pattern like ** aa or aba, there will be two or more different characters between any of the same characters **, so you can't always create an unbalanced string I can say. The above discussion is implemented below. The code in the first virtual console was terrible, so I rewrote it.

It is often good to experiment with strings to get a feel for their characteristics!

This time the problem is to focus on the "minimum" substring!

answerD.py

def groupby(a):
    a2=[[a[0],1]]
    for i in range(1,len(a)):
        if a2[-1][0]==a[i]:
            a2[-1][1]+=1
        else:
            a2.append([a[i],1])
    return a2
s1=list(input())
l=len(s1)
s2=groupby(s1)
now=0
for i in s2:
    now+=i[1]
    if i[1]!=1:
        print(str(now-i[1]+1)+" "+str(now))
        break
else:
    if l==2:
        print("-1 -1")
    else:
        for i in range(l-2):
            if s1[i]==s1[i+2]:
                print(str(i+1)+" "+str(i+3))
                break
        else:
            print("-1 -1")

answerD_shorter_faster.py

from sys import exit
s=input()
l=len(s)
for i in range(l-2):
    if s[i]==s[i+2]:
        print(str(i+1)+" "+str(i+3))
        exit()
    if s[i]==s[i+1]:
        print(str(i+1)+" "+str(i+2))
        exit()
if s[l-2]==s[l-1]:
    print(str(l-1)+" "+str(l))
else:
    print("-1 -1")