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

Benötigte Zeit

スクリーンショット 2020-05-22 22.05.00.png

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

Recommended Posts

AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
AtCoder Beginner Contest 087 Rückblick auf frühere Fragen
AtCoder Beginner Contest 067 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 046 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 049 Rückblick auf frühere Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 081 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 060 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 057 Rückblick auf frühere Fragen
AtCoder Beginner Contest 121 Rückblick auf frühere Fragen
AtCoder Beginner Contest 126 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 103 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 059 Rückblick auf frühere Fragen
AtCoder Beginner Contest 044 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 048 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 092 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen
AtCoder Beginner Contest 045 Rückblick auf frühere Fragen
AtCoder Beginner Contest 120 Rückblick auf frühere Fragen
AtCoder Beginner Contest 108 Rückblick auf frühere Fragen