[PYTHON] Keyence Programming Contest 2020 Rückblick

Ich möchte das gestrige Keyence2020 überprüfen.

Die Ergebnisse dieser Zeit

Impressionen

Ich konnte es im vorherigen Dwango überhaupt nicht lösen (ich habe es nicht überprüft, also muss ich es bald überprüfen), aber diesmal hatte ich Angst. Der Grund, warum ich die vierte Frage länger als eine Stunde nicht lösen konnte, war ** Ich hatte nicht genug Logik und Geist **, und obwohl es eine gute Frage war, die ich tun konnte, wenn ich sorgfältig darüber nachdachte, konnte ich sie während des Wettbewerbs nicht tun. Ich war ... Ich habe seit meinem Abitur kein geistiges Wachstum mehr gesehen, daher möchte ich diesen Teil auch ausbauen.

Problem A

Es ist möglich, weiterhin das größere h und w auszuwählen, also tun Sie dies (ist es zu einfach?). Nicht h, w, n = map (int, input (). Split ()), oder? Es wurde.

answerA.py

import math
h=int(input())
w=int(input())
n=int(input())
k=max(h,w)
print(math.ceil(n/k))

B-Problem

In dem Moment, als ich es sah, wusste ich, dass es sich um eine Abschnittsplanung handelte. Verwenden Sie die Abschnittsplanung, um die maximale Anzahl von Abschnitten zu verwenden, sodass beim Aufnehmen von Abschnitten mit gemeinsamen Teilen keine gemeinsamen Teile vorhanden sind. Bei der Abschnittsplanung sortiert der Algorithmus in aufsteigender Reihenfolge nach der Endzeit des Abschnitts, und der Abschnitt, dessen Startzeit nach der Endzeit liegt, wird in der Reihenfolge von zuvor (sortiert) genommen. Die mathematische Regression kann beweisen, warum die maximale Anzahl von Intervallen durch Intervallplanung genommen werden kann. Unter der Annahme, dass es eine optimale Abschnittsauswahlmethode gab, zeigt diese optimale Auswahlmethode dies, da die Endzeit nicht zu spät ist (✳︎), wenn dieselbe Nummer im Vergleich zu jeder anderen Auswahlmethode ausgewählt wird (vereinfachter Beweis). Machen.). Wenn n = 1 ist, wird derjenige mit der frühesten Endzeit ausgewählt. Wenn n = k gilt, wählt n = k + 1 den Abschnitt aus, der nach der Endzeit des durch n = k ausgewählten Abschnitts beginnt und die früheste Endzeit hat, also sogar n = k + 1 Es gilt genauso. Daher kann gesagt werden, dass (✳︎) in dem Algorithmus basierend auf der Intervallplanung gilt. Wenn das Obige implementiert ist, wird es wie folgt. Es kann leicht gelöst werden, indem man denkt, dass x-l die Startzeit und x + l die Endzeit ist.

answerB.py

n=int(input())
sec=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    sec[i][0]+=l
    sec[i][1]-=l
sec.sort()

ans=0
#-inf
t=-10000000000
for i in range(n):
    #=Vergiss nicht anzuziehen
    if t<=sec[i][1]:#Der Start muss größer oder gleich einigen maximalen Koordinaten des Roboterarms sein
        ans+=1#Wenn oben+1
        t=sec[i][0]#Maximale Koordinaten mit Roboterarm aktualisiert
print(ans)

C-Problem

Es war überraschend einfach, als ich dachte, es sei eine Konstruktion. Was ist das. Ich dachte, es gäbe k> n und ich steckte in einem Eckfall von 10 ** 9 fest und gab 4WA aus. Es tut mir Leid. 1 <= l <= r <= n, aber wenn Sie an den Fall von l = r denken, endet er sofort (zuerst 1,1,1,1,…, r-1,…, r) Es hat lange gedauert, weil ich über Dinge wie -1, r + 1, ..., r + 1 nachgedacht habe. ** Die Vereinfachung des Problems ist wichtig für die Konstruktion ** ??). Unter Berücksichtigung eines Musters mit k s und n-k s + 1 können Sie k mit l = r auswählen. Wenn jedoch $ s = 10 ^ 9 $ ist, liegt s + 1 außerhalb der Einschränkung, sodass Sie es auf 1 anstelle von s + 1 setzen können (da die Summe von 1 nicht zu s wird).

answerC.py

n,k,s=map(int,input().split())
if s<10**9:
    x=[s]*k
    y=[s+1]*(n-k)
else:
    x=[s]*k
    y=[1]*(n-k)
z=" ".join(map(str,x))+" "+" ".join(map(str,y))
print(z)

D Problem

Ich bin immer frustriert, weil ich dieses Problem nicht lösen kann. Ich glaube jedoch, dass ich erwachsen geworden bin, weil ich in letzter Zeit einige Tricks mit einem leicht verdrehten Problem wie dem C-Problem gemacht habe. Als ich nach dem Wettbewerb den stärkeren Tweet sah, bemerkte ich, dass es $ 2 ^ {18} $ war, also ungefähr $ 10 ^ 5 $, und ich konnte sehen, dass ich eine vollständige Suche durchführen konnte. Entscheiden Sie zuerst die Vorder- und Rückseite jeder Karte. Wenn Sie sich entscheiden, können Sie die Nummer sehen, die Sie im Endzustand jeder Karte sehen können. In diesem Zustand sortieren Sie in aufsteigender Reihenfolge mit Blasensortierung und überlegen, wie oft Sie zu diesem Zeitpunkt getauscht haben , Finden Sie die Mindestanzahl von Swaps. Es ist auch wichtig zu beachten, dass die vorderen Karten nur eine gerade Anzahl von Entfernungen und die hinteren Karten nur eine ungerade Anzahl von Entfernungen platziert werden können.

Ich konnte eine Richtlinie erstellen, habe aber den Fall, in dem es mehrere gleiche Nummern gibt, nicht berücksichtigt, sodass ich mit WA nichts anfangen kann. Ich würde es gerne geben, sobald AC möglich ist.