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

Benötigte Zeit

Impressionen

Ich möchte in der Lage sein, Probleme, in denen ich nicht gut bin (glaube ich), wie das Zählen, schnell zu lösen, weil die Probleme, in denen ich gut bin, so schnell zu Ende gehen. Außerdem möchte ich heute Abend mein Bestes geben, da AGC zum ersten Mal seit 5 Monaten sterben wird. Jedes Mal, wenn die AGC um mehr als 100 steigt, werde ich mein Bestes geben, um auch diesmal erfolgreich zu sein.

Problem A

A Ich hatte den Eindruck, dass das Problem ziemlich schwierig war. Wenn Sie die Zahl in der Mitte festlegen, wird die Lösung auf eine Weise festgelegt, sodass Sie die kleinste Lösung ausgeben können, die aus der Zahl in der Mitte erhalten werden kann (drei Möglichkeiten).

answerA.py

a,b,c=map(int,input().split())
print(min(abs(b-a)+abs(a-c),abs(b-c)+abs(c-a),abs(a-b)+abs(b-c)))

B-Problem

Alles was Sie tun müssen, ist alle möglichen Muster aufzuschreiben. Die Manipulation von Python-Strings ist praktisch!

answerB.py

s,t=input(),input()
for i in range(len(s)):
    if s[i:]+s[:i]==t:
        print("Yes")
        break
else:
    print("No")

C-Problem

Die Formel wurde zu einfach und ich wurde ängstlich. Der größte Rest nach dem Teilen von $ m $ für ein Element $ a_i $ in einer Sequenz ist $ a_i-1 $, der für alle Elemente in der Sequenz $ a $ berücksichtigt wird. Die Lösung ist $ -n $ aus der Summe.

Ebenso wie die Antwort kann $ m = a_1 \ mal a_2 \ mal ... \ mal a_n-1 $ verwendet werden, um solche $ m $ zu erreichen.

answerC.py

n=int(input())
a=list(map(int,input().split()))
print(sum(a)-n)

D Problem

Zuerst habe ich mir die erste Probe angesehen und ein Experiment durchgeführt. Wenn es dann mindestens eine unpassierbare Brücke zwischen den Inseln ** $ a_i $ th und $ b_i $ th ** gibt, kann die Anforderung $ i $ erfüllt werden.

Wenn Sie einfach hier denken, dachte ich, dass es besser wäre, von der Brücke zu gehen, die viele Anforderungen in der richtigen Reihenfolge erfüllen kann. Ich hatte jedoch das Gefühl, dass es hinsichtlich des Rechenaufwands schwierig sein würde, da möglicherweise Muster fehlen würden.

Deshalb habe ich mir überlegt, von Ende an gierig zu zählen. Wenn Sie diese Idee erreichen können, können Sie die Idee der Intervallplanung verwenden. Das heißt, ** eine Brücke wird am rechten Ende des ersten Abschnitts basierend auf der Reihenfolge des Abschnitts erstellt, in dem sich das rechte Ende des Abschnitts ganz links befindet. Wenn diese Brücke im nächsten Abschnitt enthalten ist, wird der nächste Abschnitt weiter untersucht Wenn die Brücke nicht im nächsten Abschnitt enthalten ist, können Sie alle Ihre Anforderungen mit der Mindestanzahl von Brücken erfüllen, indem Sie weitere Brücken erstellen und dann den nächsten Abschnitt untersuchen.

Wenn es fortlaufende Abschnitte gibt, die auf mehreren geraden Linien dargestellt werden können, ist es sehr wichtig, ** nach der Reihenfolge zu sortieren und zu denken **. Ich denke, Sie sollten dies berücksichtigen (Selbstdisziplin). Darüber hinaus kann es nach dem Sortieren auf verschiedene Muster wie DP, Greedy-Methode (einschließlich Abschnittsplanung), BIT, Seg-Baum, Skalierungsmethode, Kartoffelmethode, Grafik usw. reduziert werden.

Darüber hinaus ist es schwierig, einen Algorithmus auszuwählen, um zu der richtigen Idee zu gelangen. Daher halte ich es für wichtig, sich dessen bewusst zu sein, ihn fest zu verbalisieren.

answerD.py

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
ab.sort(key=lambda x:x[1])
ans=[[ab[0][1]-1,ab[0][1]]]
ab.pop(0)
for i in range(m-1):
    if ans[-1][0]>=ab[i][0]:
        continue
    else:
        ans.append([ab[i][1]-1,ab[i][1]])
print(len(ans))