AtCoder Beginner Contest 043 Review of past questions

Time required

スクリーンショット 2020-01-27 18.26.37.png

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

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions
AtCoder Beginner Contest 109 Review of past questions