[PYTHON] AtCoder ABC155 Problem D Pairs Review Note 1

Überblick

Ein Hinweis zu AtCoder ABC155 Problem D Pairs.

Hintergrund

AtCoder ABC155 am 2020/02/16 war zu beschäftigt, um daran teilzunehmen, aber aufgrund der Hingabe [Problem D](https: // Atcoder.jp/contests/abc155/tasks/abc155_d) Ich konnte mir keine Lösung vorstellen. Als ich den Kommentarartikel betrachtete, verstand ich, dass er nach der Dichotomiemethode gezählt werden sollte. Ich habe selbst versucht, in Python zu programmieren, aber ich konnte TLE nicht alleine verlassen.

Aus Vorheriger Vergleich habe ich vermutet, dass ich wahrscheinlich mit C ++ gehen könnte, aber

• Ist es möglich, es mit Python zu übergeben? ――Was ist süß an Ihrem Code, wenn Sie ihn übergeben?

Ich war neugierig auf solche Dinge, also habe ich nachgeschlagen.

Umfrageergebnisse

Ist es möglich, es mit Python zu übergeben?

Fazit: Kann bestehen (aber ist es etwas schwierig?)

Als ich nach einer Person suchte, die mit Python3 AC nahm, war das Ergebnis so. Während der Wettbewerbszeit kamen nur zwei Personen durch, maspy war gelb und nohtaray war blau, aber gelb (Stand 20. März 2020). Die Ausführungszeit beträgt ca. 1100 ms.

In Anbetracht der Tatsache, dass nur zwei Personen rechtzeitig vorbeikommen können und dass die beiden Personen, die durchgehen, gelb und blau sind, scheint es ein schwieriges Problem zu sein, an meinen Fähigkeiten vorbeizukommen.

Ich habe es auch mit PyPy versucht, das eine signifikante Verbesserung in Vorheriger Vergleich (Submission # 10928876 zeigte. abc155 / submissions / 10928876)) war diesmal nicht sehr effektiv und TLE konnte nicht gelöst werden.

Was ist süß an Ihrem Code, wenn Sie ihn übergeben?

Vergleich der Ausführungsgeschwindigkeit

Zuerst habe ich die Ausführungszeiten verglichen. maspy's Submission # 10152895 nohtarays Submission # 10155744 Ich habe es auf meinen Server heruntergeladen und selbst geschrieben Programm Submission # 11068460 Außerdem wurde die Ausführungszeit verglichen, zu der jedes Programm für vier Testfälle ausgeführt wurde. Die folgenden Ergebnisse (Zeitbefehlsmessung der verstrichenen Zeit. Einheit ist Sekunden). Da die Ausführungsergebnisse selbst übereinstimmen, scheint das Programm selbst ordnungsgemäß zu funktionieren.

Die Größe des Testfalls ist wie folgt. Ai wurde durch Zufallszahlen erzeugt.

Die Ergebnisse zeigen, dass mein Programm schneller ist, wenn N klein ist, aber wenn N groß ist Die Programme von maspy und nohtaray sind ungefähr zehnmal schneller. .. ..

Codevergleich

Was ist der Unterschied? .. .. Werfen wir einen Blick auf die Programme von maspy und nohtaray, um dies herauszufinden. Es stellt sich heraus, dass die beiden Codes eine Funktion namens [numpy searchsorted] verwenden (https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html). Ein Array wird auch für das zweite Argument verwendet. Es wurde erwartet, dass dies wahrscheinlich viel schneller sein würde als meine Handfunktion. Gibt es eine solche Funktion? .. .. .. Der Code ist kurz, auch dank dieser Verwendung.

Schließlich

Anmerkung 1 ist beendet, bis sich herausstellt, dass die Verwendung der sortierten Suche von numpy "miso" ist.

Ich fand heraus, dass ich nicht genug Wissen über Numpy hatte, um mit Python zu konkurrieren. Wenn Sie Lust haben, numpy searchsorted zu schreiben, oder wenn Sie Code schreiben könnten, der mit C ++ nicht einfacher zu TLE ist, werde ich ihn untersuchen und organisieren.