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

Benötigte Zeit

Impressionen

Ich konnte mich nicht dem Schreiben von [einem Artikel über 10.000 Zeichen über itertools] widmen (https://qiita.com/DaikiSuyama/items/11f63a94d63fa72e8bf4). Als ich das löste, war ich bei B in einem Rätsel gefangen und mir ging die Zeit davon, so dass ich nicht genug Zeit für D aufwenden konnte. Unmöglich! Als ich mir die Antwort ansah, war es die erwartete Lösung, also muss ich sorgfältig überlegen ... Dieser Mangel an Stabilität ist der Grund, warum es grün bleibt, aber wie kann es verbessert werden?

Problem A

Die ungerade Zahl wird mit "k // 2" berechnet, der Rest ist also eine gerade Zahl.

answerA.py

k=int(input())
print((k-k//2)*(k//2))

B-Problem

Allein dieses Problem dauerte über 30 Minuten. Aus irgendeinem Grund habe ich falsch verstanden, dass eine Seite des Quadrats parallel zu x und y war ... Da wir wie unten gezeigt ein kongruentes Dreieck zeichnen können, können wir die Koordinaten der verbleibenden Quadrate linear aus den Koordinaten der beiden angegebenen Punkte ableiten.

answerB.py

x1,y1,x2,y2=map(int,input().split())
a=x1-x2
b=y1-y2
print(x2+b,y2-a,x1+b,y1-a)

C-Problem

Da $ a + b, b + c, c + a $ ein Vielfaches von K ist, betrachten Sie den Rest von $ a, b, c $ geteilt durch K.

Wenn hier jeder Rest $ x, y, z (0 \ leqq x, y, z \ leqq K) $ ist, dann ist $ x + y = (0 \ oder \ K), y + z = (0) Es reicht aus, wenn \ oder \ K), z + x = (0 \ oder \ K) $ gilt und $ (x, y, z) = (\ frac {K} {2}, \ frac {K} {2}, \ frac {K} {2}) \ oder \ (0,0,0) $.

Außerdem habe ich schnell herausgefunden, dass ich einen Rest benötige, also habe ich alle Reste im Wörterbuch gespeichert, aber ich muss sie nur für k // 2 oder 0 speichern.

answerC.py

n,k=map(int,input().split())
d=dict()
for i in range(k):
    d[i]=0
for i in range(1,n+1):
    d[i%k]+=1
#print(d)
if k%2!=0:
    print(d[0]**3)
else:
    print(d[0]**3+d[k//2]**3)

D Problem

** Grafikprobleme sind immer beängstigend ... **. Ich möchte viele Grafikprobleme lösen und mich daran gewöhnen, aber ich habe keine Zeit. Ich konnte es während des Wettbewerbs nicht lösen, also warf ich einen Blick auf diesen Blog, aber folge einfach den Richtlinien, die ich gemacht habe. Mir wurde klar, dass es gut und verdorrt war. ** Ich habe nicht genug Kraft, um es gemäß meiner eigenen Politik voranzutreiben ** ...

Da alle Pfade unterschiedlich sind und alle Pfade von 0 bis L-1 in Schritten von 1 generiert werden müssen und es viele Einschränkungen gibt, hatte ich zuerst das Gefühl, dass ** es nicht gut ist, über die Pfade richtig nachzudenken **. Da es zwei Möglichkeiten gibt, je nachdem, ob der Pfad übergeben wird oder nicht, habe ich festgestellt, dass ** Seiten dadurch ausgedrückt werden können, ob das Bit gesetzt ist oder nicht **.

Ich konnte kein genaues Diagramm zeichnen und experimentieren, um zu sehen, ob es mit diesem Bit ausgedrückt werden kann. Obwohl es bergab geht, können Sie die ausgewählte Seite ändern, je nachdem, ob das Bit gesetzt ist oder nicht, indem Sie die folgenden Schritte ausführen.

Im obigen Fall können 0 bis 15 als 16 verschiedene Pfade dargestellt werden, indem jedes ** $ i → i + 1 $ als das $ i-1 $ -Bit ** (L = 16) betrachtet wird. Im Falle von). Auf die gleiche Weise können Sie leicht erkennen, dass 0 bis 31 durch Hinzufügen der 6 Eckpunkte (L = 32) dargestellt werden können. Wenn L also eine Potenz von 2 ist, scheint es, dass es ausgedrückt werden kann. Betrachten wir also die anderen Fälle (L = 19).

Je mehr Kanten Sie hinzufügen, desto mehr unterschiedliche Pfade werden Sie haben. Erhöhen Sie also die Kanten, aber erhöhen Sie sie nicht blind. Angenommen, Sie fügen 4 → 5 Seiten hinzu. Zu diesem Zeitpunkt erhöht sich die Anzahl der verschiedenen Pfade um $ 2 ^ 3 $ ($ , weil $ 1 → 4 Pfade $ 2 ^ 3 $ sind), sodass die Gesamtzahl der verschiedenen Pfade 24 beträgt. Daher überschreitet es 19 Zeilen. Wenn Sie auf die gleiche Weise denken **, erhöht das Hinzufügen einer Seite, die sich von jedem Scheitelpunkt $ i $ zur größten Anzahl von Scheitelpunkten erstreckt, die Anzahl der Pfade, die sich um $ 2 ^ {i-1} $ ** unterscheiden. Darüber hinaus kann der Pfad, der zu diesem Zeitpunkt zunimmt, in Schritten von 1 ausgedrückt werden (es ist nicht schwierig, wenn Sie ein Diagramm zeichnen und experimentieren).

Wenn L binär angezeigt wird, bestimmen Sie daher, wie viele Scheitelpunkte aus dem Bit der höchsten Ziffer vorhanden sind, und betrachten Sie die Einsen in der Reihenfolge mit den darunter liegenden Bits. Wenn es 1 dieses Bits gibt Durch Erweitern der Seiten von den entsprechenden Scheitelpunkten zu den letzten Scheitelpunkten ist es möglich, L verschiedene Pfade zu erstellen, während die Anzahl der Scheitelpunkte und die Anzahl der Seiten erfüllt werden.

Ich denke auch, dass die Erklärung etwas schwer zu verstehen ist, deshalb werde ich Ihnen zeigen, wie man sie löst, wenn L = 19 (von Hand) unten.

Darüber hinaus wird im folgenden Code die Dropwhile-Funktion verwendet, um das oberste Bit zu finden (Suche von oben nach $ \ weil $, um das Element zu finden, das zum ersten Mal 1 wird). Ich habe beim Schreiben von diesem Artikel itertools studiert.

answerD.py

from itertools import dropwhile
l=int(input())
#Richten Sie sich vom oberen Bit aus
k=[(l>>i & 1) for i in range(20)][::-1]
#Liste zum ersten Mal unter 1 Bit
k=list(dropwhile(lambda x:x==0,k))

n=len(k)
path=[]
for i in range(n-1):
    path.append((i+1,i+2,0))
    path.append((i+1,i+2,2**i))

path_len=2**(n-1)
for i in range(1,n):
    if k[i]:
        x=n-1-i
        path.append((x+1,n,path_len))
        path_len+=(2**x)

m=len(path)
print(n,m)
for i in path:
    print(i[0],i[1],i[2])