[PYTHON] AtCoder Beginner Contest 043 Rückblick auf frühere Fragen

Benötigte Zeit

Problem A

Finden Sie einfach die Summe.

answerA.py

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

B-Problem

Einfach 0,1 hinzufügen und mit B entfernen.

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

Im Fall von -100 oder weniger und 100 oder mehr sind -100 bzw. 100 das Minimum. Suchen Sie daher alle Werte, die sich von -100 auf 100 ändern.

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

Erstens haben unausgeglichene Saiten die gleiche Mehrheit. Außerdem (** während des Experiments **) ** habe ich festgestellt, dass der unsymmetrische Teilstring in dem unsymmetrischen String verborgen ist **. Beispielsweise enthält die benötigte Probe unausgeglichene Teilzeichenfolgen wie nee und ede, aber ee in nee ist auch eine unausgeglichene Teilzeichenfolge. Da nur ein unsymmetrischer Teilstring ausgegeben werden muss, habe ich mir überlegt, welcher Teilstring die kleinste Einheit ist. Erstens wird ein Teilstring der Länge 2 zu einem unausgeglichenen Teilstring, wenn die beiden Zeichen gleich sind. Als nächstes ist zu sehen, dass zwei Zeichen ebenfalls in der Teilzeichenfolge der Länge 3 enthalten sind, und wenn die Zeichen fortlaufend sind, ist die Teilzeichenfolge der Länge 2 auch eine unausgeglichene Teilzeichenfolge. Ich werde. Mit anderen Worten, unter der Annahme, dass der kleinste unausgeglichene Teilstring existiert, können wir sehen, dass der kleinste wahrscheinlich an beiden Enden die gleichen Zeichen hat (was durch die Absurdität angezeigt werden kann, wenn sie nicht die gleichen Zeichen haben). Darüber hinaus versteht es sich intuitiv, dass diese unausgeglichene Zeichenkette nicht die kleinste unausgeglichene Zeichenkette ist, wenn die gleichen Zeichen wie beide Enden in der unausgeglichenen Zeichenkette vorhanden sind. Daher ist es ausreichend, wenn eine unausgeglichene Zeichenfolge (Muster wie aa oder aba) vorhanden ist, die an beiden Enden dasselbe Zeichen und eine Länge von 2 oder mehr aufweist, und diese sollte ausgegeben werden. Da ** die Mehrheit dieselben Zeichen sind, sind dieselben Zeichen immer "benachbart" oder "alle anderen" **, was diese Intuition unterstützt. Wenn es kein Muster wie ** aa oder aba gibt, gibt es zwei oder mehr verschiedene Zeichen zwischen denselben Zeichen **, sodass es nicht immer möglich ist, eine unausgeglichene Zeichenfolge zu erstellen. Ich kann sagen. Die obige Diskussion wird unten implementiert. Der Code im ersten Bachacon war schrecklich, also habe ich ihn umgeschrieben.

Es ist oft gut, mit Zeichenketten zu experimentieren, um ein Gefühl für ihre Eigenschaften zu bekommen!

Dieses Mal besteht das Problem darin, sich auf den "minimalen" Teilstring zu konzentrieren!

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