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

Benötigte Zeit

Impressionen

Ich habe zum ersten Mal in Bacha den ersten Platz belegt! , Banzai! Ich möchte mich bemühen, es so gut zu passen. D war ein Moment, in dem ich die grundlegende Lösung für das Spielproblem anwendete. (Es gab einen Fall, in dem ich vergessen habe, darüber nachzudenken, während ich das sagte. Ich bereue es.)

Problem A

Nehmen Sie einfach den ersten Buchstaben in der richtigen Reihenfolge.

answerA.py

x=input().split()
print(x[0][0]+x[1][0]+x[2][0])

B-Problem

Unter Berücksichtigung des kleinsten Vielfachen von x über a (Deckenfunktion) und des größten Vielfachen von x unter b (Bodenfunktion) ist es nur erforderlich, die Anzahl der Vielfachen von x zwischen den beiden Zahlen (einschließlich beider Enden) zu zählen. Sie können sehen, dass. Um Ungenauigkeiten zu vermeiden, habe ich diesmal den Operator // verwendet, ohne die Decken- oder Bodenfunktionen zu verwenden.

answerB.py

a,b,x=map(int,input().split())
A=-((-a)//x)
B=b//x
print(B-A+1)

C-Problem

Es ist ausreichend, wenn $ a_i + a_ {i + 1} <= x $ für i = 1 bis n-1 gilt. Um die Anzahl der Operationen zu minimieren, ** sollten Sie alle Summen zweier benachbarter Zahlen ** berücksichtigen. Daher ist es besser, ** dies gierig von vorne zu tun ** (ich denke, es gibt viele ähnliche Probleme mit AtCoder). .). Insbesondere machen Sie unter $ a_1 $ als x oder weniger $ a_ {i + 1} $ kleiner, so dass $ a_i + a_ {i + 1} <= x $ von i = 1 bis n-1 gilt. Machen. Wenn es bereits gilt, nichts tun. Hier können Sie entweder $ a_i $ oder $ a_ {i + 1} $ kleiner machen, aber wenn Sie $ a_ {i + 1} $ kleiner machen, $ a_ {i + 1} + a_ {i + 2 Sie können erwarten, dass $ a_j + a_ {j + 1} $ in j> i kleiner ist, da} $ kleiner ist. Daher kann daraus gesagt werden, dass die minimale Anzahl von Operationen erreicht werden kann, indem sie gierig von vorne ausgeführt werden.

answerC.py

n,x=map(int,input().split())
a=list(map(int,input().split()))
if a[0]>x:
    ans=a[0]-x
    a[0]=x
else:
    ans=0
for i in range(1,n):
    if a[i-1]+a[i]>x:
        ans+=(a[i-1]+a[i]-x)
        a[i]=x-a[i-1]
print(ans)

D Problem

Es ist ein Problem, ein Spiel mit zwei Personen zu spielen. Es gibt zwei grundlegende Richtlinien für solche Probleme. Die erste ist ** achte auf die letzte Phase des Spiels **. In der Wettbewerbsprogrammierung ist es oft nicht möglich, alles zu simulieren, daher ist es oft gut, sich auf die letzte Phase zu konzentrieren. Die zweite ist ** was die Phase des Spiels ist **. Spiele, die durch wettbewerbsfähige Programmierung gelöst werden, sind darauf ausgelegt, zu lösen, und viele von ihnen können in mehrere Zustände unterteilt werden. (In diesem Problem werden die Operationen abwechselnd ausgeführt, daher sind ** gerade und ungerade ** ebenfalls wichtige Kontrollpunkte.)

Die Lösung ist wie folgt unter Berücksichtigung der beiden oben genannten Punkte. Zunächst können Sie in der letzten Phase sehen, dass entweder (1) es nicht entfernt werden kann, weil nur noch zwei Zeichen übrig sind (weil es an beiden Enden ist), oder (2) es nicht entfernt werden kann, weil dieselben Zeichen nebeneinander liegen. Außerdem ist es wichtig, dass die Zeichen an beiden Enden ** niemals entfernt werden können **. Mit anderen Worten, die verbleibenden zwei Zeichen in Muster (1) sind zwei Zeichen an beiden Enden, und die gleichen Zeichen, die in Muster (2) nebeneinander liegen, sind zwei Zeichen an beiden Enden (insgesamt drei Zeichen). Hier dachte ich, dass als letztes noch zwei oder drei Zeichen übrig waren, aber dies ist nicht der Fall bei Mustern wie Abababa, bei denen sich zwei Arten von Zeichen abwechseln. Ich habe es nicht bemerkt, bis ich die Antwort sah ... Die Überlegung ist süß. (Da der Fall durch gerade und ungerade geteilt wird, hat dies keinen Einfluss auf das Ergebnis.) In jedem Fall ist die Anzahl der in Muster (1) verbleibenden Zeichen ** gerade ** und die Anzahl der in Muster (2) verbleibenden Zeichen ** ungerade **. Wenn also n in Muster (1) gerade ist, verlieren Sie den ersten Angriff und n. Wenn ungerade ist, geht der zweite Angriff verloren, wenn n in Muster (2) gerade ist, geht der zweite Angriff verloren, und wenn n ungerade ist, geht der erste Angriff verloren. (Einzelheiten finden Sie unter Antwort.)

answerD.py

s=input()
n=len(s)
if s[0]==s[-1]:
    if n%2==0:
        print("First")
    else:
        print("Second")
elif s[0]!=s[-1]:
    if n%2==1:
        print("First")
    else:
        print("Second")