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

Benötigte Zeit

Impressionen

Das D-Problem war schrecklich. Es war später als zu dem Zeitpunkt, als ich es im Dezember löste. Ich werde es fest überprüfen.

Problem A

Da es diagonal ist, sind die Zeilen- und Spaltennummern gleich.

answerA1.py

s=[input()[i] for i in range(3)]
print("".join(s))

B-Problem

Beurteilen Sie, ob es sich um eine Zirkulation von A nach B handelt. Sie müssen jeweils nur einen Charakter beurteilen.

answerB.py

a,b=map(int,input().split())
ans=0
for i in range(a,b+1):
    s=str(i)
    l=len(s)
    for i in range(l//2):
        if s[i]!=s[l-1-i]:
            break
    else:
        ans+=1
print(ans)

C-Problem

** Ich habe die Problemstellung falsch verstanden ** und dachte, dass es ** Karten in allen 9 Feldern ** gibt **, aber es war einfach, weil ich nur ** existieren musste **. Es ist schmerzhaft.

answerC.py

n,m=map(int,input().split())
if n==1 and m==1:
    print(1)
elif n==1:
    print(m-2)
elif m==1:
    print(n-2)
else:
    print((n-2)*(m-2))

D Problem

Der einfachste Weg ist, sowohl a als auch b zu bewegen, aber es ist O ($ n ^ 2 ), also ist es zu spät. In diesem Problem geht aus Experimenten hervor, dass es eine Beziehung zwischen den beiden Zahlen ** gibt, so dass es nur notwendig ist, eine zu fixieren und die andere gut mit O (1) ** zu finden Ich dachte es könnte sein. In Bezug darauf, welches hier repariert werden soll, habe ich festgestellt, dass das Bewegen von b unregelmäßige Bewegungen verursacht, wenn ** a repariert ist. Stellen Sie sich das daher als Fixierung vor. B. Erstens ist unter Berücksichtigung des Bereichs von b der Rest k oder mehr, also k + 1 ~ n. Ich werde es in diesem Bereich reparieren, aber vorher dachte ich, dass ** es schwer zu glauben ist, dass der Rest k + 1 ~ n ** ist, also habe ich beschlossen, es unter Berücksichtigung seiner komplementären Menge zu zeichnen. Beachten Sie daher, dass ** den Rest von 0 bis k-1 von der Anzahl der Kombinationen von b von k + 1 ~ n und a von 1 ~ n ( (nk) \ mal n $) ** subtrahiert. Betrachten Sie a **, wobei b durch k + 1 ~ n geteilt wird und der Rest 0 ~ k-1 ist. Ein verallgemeinerter Export solcher ** Kandidaten ** würde folgendermaßen aussehen:

Betrachten Sie die Anzahl der Kandidaten für eine der oben genannten. Zunächst ist es für l oben ausreichend zu berücksichtigen, wie viele b unter n liegen, damit es mit n // b berechnet werden kann. Darüber hinaus ist die Anzahl der Zahlen zwischen l * b + 1 und n, die einen Rest von 0 bis k-1 haben, die kleinere von n geteilt durch b und k-1 (wobei k = Wenn es 0 ist, wird k-1 negativ, so dass angenommen wird, dass es größer als 0 ist. Die Antwort kann erhalten werden, indem die obigen Kandidaten für a ** subtrahiert werden und darüber nachgedacht wird, indem b bewegt wird.

Durch dieses Problem

Experimentieren und verstehen Sie das Verhalten

Schreiben Sie es auf und denken Sie bei der Verallgemeinerung darüber nach

Ich habe das gelernt.

answerD.py

n,k=map(int,input().split())
ans=n*(n-k)
for i in range(k+1,n+1):
    ans-=(k*(n//i))
    ans-=max(0,min(k-1,n%i))
print(ans)