[PYTHON] AtCoder Hellblau werden

0. Einleitung

Hallo, das ist HIROSHI0635. Ich habe einen einfachen Artikel geschrieben, als er grün wurde, aber ich habe es geschafft, ihn ungefähr 9 Monate nachdem er grün wurde hellblau zu machen. Um ehrlich zu sein, ich denke, es ist lange her. Deshalb schreibe ich in der Hoffnung, etwas zu schreiben, das denjenigen, die mit Grün oder Braun zu kämpfen haben, einige Hinweise gibt. In diesem Sinne habe ich es gewagt, ihm den Titel "Wie man AtCoder hellblau wird" anstelle von "Bis es AtCoder hellblau wird" zu geben (ich liebe die Tatsache, dass das Grün beim Schreiben des Artikels verblasst ist ...).

1. Selbsteinführung

・ Drittes Jahr der Erwerbstätigen in Finanzangelegenheiten. ・ AtCoder wurde einmal in C ++ gestartet, aber ich konnte nichts tun und war in ungefähr einem Monat frustriert. ・ Ich habe die Sprache in Python geändert und es erneut versucht und in anderthalb Jahren hellblau erreicht. ・ Als ich am College war, war ich ein Student der Freien Künste. Ich habe keine Erfahrung in der Programmierung. ・ In der Prüfungsphase der Universität gibt es keine Schwäche in der Mathematik.

Es ist ungefähr so. Informationen zum Starten von AtCoder finden Sie im vorherigen Artikel (AtCoder bis es grün wird). Bitte wende dich an die

2. Über das Problem nachdenken

2-1. Von einem schleppenden Wachstum denken

Während die erste grüne Aufführung der 11. Wettbewerb war, dauerte die erste hellblaue Aufführung die 38. (eigentlich die 41., weil der 38. Hitachi-Wettbewerb zufällig von 100 bis 200 schnellen Antworten abhängig war). Natürlich kannte ich zum 11. Mal die sogenannten "Standardalgorithmen" wie DFS, BFS, Dikstra-Methode, Dichotomie usw. nicht, aber zum 25. Mal können alle mehrmals implementiert und kopiert werden. Es war eine Situation, in der AC für solche Probleme durchgeführt werden konnte. Trotzdem denke ich, dass der Grund, warum ich das Problem der grünen Schwierigkeit [^ 1] nicht lösen konnte, darin bestand, dass ich im Bewusstsein des Rechenaufwands [^ 2] und des Bewusstseins, das Problem zu reduzieren, schwach war.

2-2. Sensibilisierung für den Rechenaufwand

Lassen Sie uns plötzlich die Lösung des AtCoder-Problems durch die Herstellung von Curry ersetzen (Curry hat nichts zu bedeuten, ich habe nur darüber nachgedacht). Angenommen, Sie werden gebeten, ein Curry für weniger als 2000 Yen als Limit zuzubereiten. Ich glaube nicht, dass gewöhnliche Leute mehr als 2000 Yen für Zutaten in Supermärkten kaufen, aber das passiert, wenn Sie unerwartet TLE in wettbewerbsfähiger Programmierung werden. Es ist ein bisschen besser, wenn Sie wissen, dass Sie nicht wissen, wie viel diese Zutat kostet, aber wenn Sie zur Registrierkasse gehen, ohne über den Preis nachzudenken, oder wenn Sie denken, dass dies 100 Yen sind, sind es tatsächlich 5000 Billionen Yen. ist. ** Wenn Sie nicht wissen, wie viel Ihre Antwort berechnet wird, sollten Sie sich angewöhnen, zuerst Ihre eigene Antwort zu erfassen, anstatt verschiedene Algorithmen auszuprobieren **. Wie gesagt, erst kurz bevor es grün wurde, wurde mir der Rechenaufwand und die Antwort bewusst.) Erstens besteht die Motivation für die Verwendung des Algorithmus darin, den Rechenaufwand zu reduzieren, da die vollständige Suche nicht rechtzeitig erfolgt. Wenn Sie den Rechenaufwand nicht kennen, ist dies eine Fundgrube.

Wenn Sie gefragt werden, wie Sie die Fähigkeit verbessern können, den Rechenaufwand zu erfassen, sollten Sie in einer Situation, in der Sie nicht wissen, wie viel dieser Rechenaufwand sich in der Übungsphase befindet, den Rechenaufwand überprüfen oder sich angewöhnen, zu einem Schreibstil zu wechseln, der den Rechenaufwand bestimmt. Ich denke, es gibt keine Wahl. Wenn Sie ein Python-Benutzer sind, ist dieser Artikel (Geschichte der peinlichen Berechnung, wenn Sie Pythonista nicht kennen) sehr hilfreich.

2-3. Sensibilisierung zur Reduzierung von Problemen

Plötzlich (wieder) wird AtCoder oft als Mathe-Spiel bezeichnet. Sicherlich gibt es Fälle, in denen Menschen mit einem starken mathematischen Hintergrund innerhalb von Sekunden nach etwa zehnmaliger Teilnahme blau werden. Meine Theorie ist, dass dies halb richtig und halb falsch ist (es tut mir leid, wenn ich falsch verstehe, weil ich nur Prüfungsmathematik mache). Dies liegt daran, dass es nicht viele Probleme gibt, bei denen AtCoder das Wissen der Mathematik so wie es ist nutzen kann, aber die Denkmethode zum Finden einer Formel, die durch Abstrahieren des Problems angewendet werden kann, die bei der Lösung eines mathematischen Problems erforderlich ist, kann so wie sie ist verwendet werden. Angenommen, Sie haben in der Mittelschule gelernt, wie man eine lineare Gleichung von "5x = 10" → "x = 2" löst. Wenn Sie sich daran erinnern, wie es ist, wird es "Ich weiß es nicht, weil ich es nicht gelernt habe" sein, selbst wenn Sie aufgefordert werden, "3a = 6" zu lösen. Je nachdem, ob das erste Problem nur als eine Variante von x oder x überhaupt als ein Container von Zahlen betrachtet wird, ist der Abstraktionsgrad unterschiedlich und je abstrakter es ist, desto mehr kann es auf viele Probleme angewendet werden. Ich werde. Ich habe es gewagt, ein einfaches Beispiel und ein Beispiel für die Abstraktion zu geben, aber selbst bei einem echten Problem kann sich die Schwierigkeit erheblich ändern, obwohl der Implementierungsbetrag mit demselben Algorithmus nicht sehr unterschiedlich ist. Zum Beispiel (bitte seien Sie vorsichtig, wenn Sie es zuerst lösen möchten, da es unten Spoiler enthält), AtCoder Beginner Contest 177 D - Friends [AtCoder Regular Contest 107 C - Shuffle Permutation] (https://atcoder.jp/contests/arc107/tasks/arc107_c?lang=ja)

Die beiden Probleme verwenden denselben Algorithmus, aber die Schwierigkeit unterscheidet sich um mehr als 500. Das Problem mit 177-D ist, dass das Wort "Gruppe" herauskommt und es eine Atmosphäre gibt, die Union-Find ähnelt. Ich habe das Gefühl, dass es viele Menschen gibt, die es geschafft haben, AC zu betreiben. Ich denke, dass der Unterschied in den Folgen des Problems der Unterschied zwischen denen ist, die das obere Problem und nicht das untere Problem lösen können. Das folgende Problem scheint auf den ersten Blick trivial zu sein, aber da es keine Duplizierung von Elementen gibt, können Sie sehen, dass es vertikal und horizontal getrennt betrachtet werden kann (wenn vertikal und horizontal herauskommen, kann es getrennt betrachtet werden). Es ist ein ziemlich typisches Denkmuster, darüber nachzudenken. Wenn Sie berücksichtigen, dass die Zeilen / Spalten, die ausgetauscht werden können, begrenzt sind, können Sie auch sehen, dass die verbundenen Zeilen / Spalten frei ausgetauscht werden können. Wenn Sie dies bisher tun können, können Sie das Problem lösen, indem Sie die Datenstruktur reduzieren, die verwaltet, ob sie verkettet ist oder nicht → Union-Find. Der größte Punkt ist, ob "Swap" als "Stretching" umschrieben werden kann, aber so abstrakt kann das Problem betrachtet werden. Von nun an werde ich erklären, wie die Fähigkeit verbessert werden kann, das Problem abstrakt zu reduzieren.

2-4. Training zur Verbesserung der Rückkehrfähigkeit

① Lösen Sie Probleme desselben Genres gemeinsam

Wenn Sie diese Hingabe anwenden, werden Sie feststellen, dass jeder Algorithmus auf eine Vielzahl von Problemen angewendet werden kann, wodurch die Auswirkungen des Problems erhöht werden. Um die Konsequenz zu erhöhen, muss jeder Algorithmus in einer abstrakteren Dimension verstanden werden (wie im Beispiel der linearen Gleichung gezeigt). Es ist jedoch schwierig, plötzlich abstrakt zu denken (wenn Sie plötzlich versuchen, eine mathematisch strenge Definition / einen Satz zu verstehen, werden Sie überrascht sein, oder?). Seien Sie also beim Nachdenken über konkrete Beispiele (konkrete Probleme) bemerkt. Ich denke, diese Methode ist einfach zu machen. Für diejenigen, die in Braun oder Grün schwelen, möchte ich besonders Richtlinien zur Verbesserung von Wettkampfprofis und AtCoder von Red Coder [Zwischenausgabe: Ziel für hellblauen Coder! ] soll die 100 aufgeführten Fragen lösen. Ich habe ungefähr 80 Fragen gelöst, aber ich habe das Gefühl, dass ich beträchtliche Stärke gewonnen habe. Es gibt einige schwierige Probleme. Wenn es also wirklich schwierig ist, können Sie es überspringen.

② Lösen Sie dasselbe Problem mit einer anderen Methode

Wenn Methode (1) ein vertikaler Spieß ist, ist Methode (2) ein horizontaler Spieß. Beispielsweise können Probleme, die mit BFS gelöst werden können, mit DFS gelöst werden. Auch Probleme, die mit der Skalierungsmethode gelöst werden können, können durch grobe Dichotomisierung gelöst werden. Das Lösen desselben Problems auf unterschiedliche Weise führt zu einer anderen Perspektive des Problems, wodurch die Umschreibungskraft des Problems erhöht wird, dh die Fähigkeit, es zu reduzieren. Darüber hinaus gibt es eine Lösung, die besagt, dass beide gelöst werden können, die jedoch leichter zu lösen ist (obwohl sie sich je nach Person ändern kann), und es gibt eine Richtlinie, um diesen Algorithmus für solche Probleme, Beschleunigung und Sicherheit anzuwenden. Es führt zu einer Verbesserung. Ich selbst denke, dass BFS leichter zu verstehen ist als DFS und dass die Dichotomie schneller ist als die Skalierungsmethode, ohne Fehler zu verursachen. Wenn Sie also ein Problem haben, das auf beide anwendbar zu sein scheint, verwenden Sie BFS bzw. Dichotomie. Ich mache es. Als jüngste Entdeckung habe ich einen Weg gelernt, um das Problem mit den folgenden Problemen zu reduzieren (zu denen auch Spoiler gehören).

[AtCoder Grand Contest B - Graph Partition] (https://atcoder.jp/contests/agc039/tasks/agc039_b)

Aus der Schlussfolgerung ist dieses Problem eine Frage, ob es möglich ist, "kann es in eine Menge von Eckpunkten getrennt werden" → "zweiteilige Graphbeurteilung" zu paraphrasieren. Als ich selbst über dieses Problem nachdachte, dachte ich, dass es möglich wäre, es zu trennen, wenn es keine geschlossenen Pfade mit ungerader Länge gäbe, aber ich konnte den Code nicht schreiben und sah mir die Erklärung an und bestätigte sie mit einer Lösungsmethode unter Verwendung eines zweiteiligen Diagramms. Ich habe hier nicht geendet, aber da es eine große Sache war, habe ich auch einen Code geschrieben, der auf der Idee basiert, dass "er getrennt werden kann, wenn es keinen geschlossenen Pfad von ungerader Länge gibt", und bestätigt, dass Wechselstrom genommen werden kann. [Methode mit zweiteiliger Graphbeurteilung] (https://atcoder.jp/contests/agc039/submissions/17673050) [Methode, die sich auf das Vorhandensein oder Fehlen von ungeraden gesperrten Straßen konzentriert] (https://atcoder.jp/contests/agc039/submissions/17673603)

Wie Sie durch einen Vergleich sehen können, ist es einfacher, die zweiteilige Diagrammbeurteilung zu verwenden. Wenn Sie sich jedoch trauen, diese Arbeit zu erledigen, und wenn Sie eine Lösung finden, die sich auf die gleiche Weise auf ungerade gesperrte Straßen konzentriert, können Sie diese auf eine zweiteilige grafische Beurteilung reduzieren. Ich denke nicht, dass es notwendig ist, dies für alle Probleme zu tun, aber wenn Sie Schwierigkeiten haben und selbst AC betreiben können, lesen Sie die Erklärung, und wenn Sie einen anderen Ansatz wählen, versuchen Sie es auch. Ich finde das gut

2-5. Zusammenfassung

Neben der Zusammenfassung der bisherigen Geschichte werde ich den Gedankenfluss über das Problem ein wenig erläutern.

Ich denke über das Problem mit einem Fluss nach, der wie eine Folie oben aussieht. Wie Sie sehen können, besteht der Schlüssel darin, den Rechenaufwand in ④ und ⑥ richtig zu erfassen und auf einen typischen Algorithmus zu reduzieren, der das Problem in ② und ⑤ lösen kann. Überlegen Sie sich beim Betreten des Zweigs von a, wie Sie das Problem irgendwie reduzieren können, um das in ② beschriebene Problem zu verstehen. Hier betrachten wir einen Algorithmus, der vorerst gelöst werden kann, ohne Berücksichtigung des Rechenaufwands. Es wäre schön, wenn die Antwort, die Sie dachten, rechtzeitig für die Berechnung wäre, aber wenn sie nicht rechtzeitig ist, versuchen Sie, sie mit der in ⑤ beschriebenen Methode zu reduzieren. Unter ihnen ist der typische Kampf in diesem Artikel gut organisiert (Typische Denkweise für die Erarbeitung einer Lösung für wettbewerbsorientierte Programmierung). .. Ich denke, je mehr Menschen sich nicht bewusst sind, das Problem auf das Typische zu reduzieren, desto mehr können sie erreichen, wenn sie es einmal betrachten.

3. Andere Andachtsinhalte

Ich habe in Kapitel 2 etwas Andacht geschrieben, aber hier sind einige andere Dinge, die ich getan habe.

3-1. JOI Hingabe

Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen Coder! ] Es gibt einige JOI-Probleme, aber es gibt viele gute Fragen zu JOI-Problemen, insbesondere zum DP / Shortest Route-Problem. Ich bin selbst nicht sehr gut in DP, und ich habe auch den Educational DP Contest / DP Summary Contest durchgeführt, aber er war nicht sehr gut etabliert, daher war er sehr nützlich. .. AOJ / AtCoder-JOI ist praktisch, da Sie die gelösten Probleme sowie die nach Ebenen geordneten Probleme verwalten können. Für braune Codierer ist es besser, von Stufe 4 oder Stufe 5 zu lösen, und für grüne Codierer ist es besser, von Stufe 5 oder Stufe 6 zu lösen.

3-2 Kodofo Hingabe

Ich denke, viele Leute machen das. Viele der Kodofo-Wettbewerbe finden jedoch spät in der Nacht statt, und es ist für arbeitende Menschen schwierig, daran teilzunehmen. Wenn Sie Codeforces Anytime verwenden, können Sie auch in einem virtuellen Wettbewerb eine virtuelle Bewertung erhalten, sodass Sie mit einem Gefühl der Spannung arbeiten können.

3-3. Teilnahme am Teamkampf

Kürzlich habe ich an einem Wettbewerb teilgenommen, der von Freiwilligen von Universitäten wie WUPC und KUPC durchgeführt wurde. Es war eine gute Gelegenheit, die Denkmuster anderer Menschen zu lernen, indem man an Dreiergruppen teilnahm. Meine beiden Teamkollegen waren blaue Programmierer, daher konnte ich nicht viel zum Team beitragen, aber wenn ich dachte "Ich möchte bis zum nächsten Mal auch nur eine Frage lösen" und "Ich möchte diese Leute einholen", kann ich das tun. Ich glaube, ich konnte es erweitern.

4. Im Wettbewerb herumlaufen

4-1. Verwenden wir die Rangliste

Sehen Sie die Rangliste während des Wettbewerbs? Ich werde sehen. Im Fall von ABC versuche ich, schnell bis D zu lösen, ohne auf die Rangliste zu schauen, auf die Rangliste, wenn ich sie lösen kann, auf E und F und auf F, wenn sie so viel gelöst sind. Dies liegt daran, dass es wahrscheinlich einfacher ist, F zu lösen, da F genauso gelöst ist wie es Leute gibt, die eine bestimmte Zahl von vorne lösen, ohne auf die Rangliste zu schauen. Wenn Sie der Meinung sind, dass Sie es mit der gierigen Methode lösen können, sich aber nicht auf den Beweis verlassen können, sollten Sie den Sprung wagen und ihn einreichen, wenn Sie anhand der Rangliste feststellen können, dass er erheblich gelöst ist oder die WA-Rate niedrig ist. Ich denke jedoch nicht, dass diese Methode ehrlich sein kann, daher denke ich, dass es besser ist, den Kommentar zu lesen und den Beweis zu verstehen, nachdem der Wettbewerb beendet ist.

4-2. Die Problemstellung enthält möglicherweise Hinweise

Es ist nicht so vielseitig, aber es kann gelegentlich verwendet werden. In letzter Zeit ist das Problem des HHKB-Programmierwettbewerbs 2020 E - Lampen AtCoder-Anfängerwettbewerb 129 D - Lampe Wenn Sie das Problem von / contests / abc129 / task / abc129_d) kennen, können Sie die Vorverarbeitung kopieren und einfügen. In den letzten Jahren scheint ABC das Feld der ehrlichen Fragen abgeschlossen zu haben, und es ist wichtig, die Fragen der Vergangenheit in gewissem Maße zu kennen. Erfordert dieses Problem, AtCoder Beginner Contest 166 D - Ich hasse Faktorisierung, anscheinend eine mathematische Formeltransformation? Ich dachte, aber wenn ich mir die Problemstellung anschaue, heißt es "Ich hasse Faktorisierung" und es gibt keine Garantie, aber ich denke, sie kann durch eine einfache Suche und nicht durch eine erweiterte Formeltransformation gelöst werden. Es war eine Gelegenheit, sich fortzubewegen.

4-3. Wenn der Rechenaufwand verdächtig ist

Selbst wenn Sie den Rechenaufwand kennen, fragen Sie sich möglicherweise, ob Sie ihn rechtzeitig einreichen sollen oder ob es sich um einen heiklen Rechenaufwand handelt. In einem solchen Fall können Sie Ihren eigenen Testfall mit dem maximalen Rechenaufwand erstellen und den Code an den Codetest auf der AtCoder-Seite senden, um die Garantie zu erhalten, dass Sie rechtzeitig sind, ohne die Strafe zu opfern.

5. Bequeme Link-Sammlung

Bisher habe ich einige Websites aufgelistet, aber hier sind einige andere Dinge, die ich hilfreich fand. Ich denke, Sie sollten sich nur die Dinge ansehen, die Ihnen wichtig sind.

Übergabe als Referenz und Übergabe als Wert in Python-Argumenten ... Es fiel mir schwer, die Struktur einer solchen Sprache zu verstehen, weil ich nicht die Möglichkeit hatte, systematisch etwas über Programmiersprachen zu lernen. Wenn Sie Python verwenden, ist dies der erste Inhalt, den Sie beherrschen sollten.

[Gleitkommazahl-Nerd versucht, das C-Problem des AtCoder Beginner Contest 169 zu erklären] (https://qiita.com/mod_poppo/items/910b5fb9303baf864bf7) ... Otaku ist ein Gott, weil er mit einem bestimmten Gebiet vertraut ist. Der Witz handelt von Gleitkommazahlen, die heutzutage häufiger geworden zu sein scheinen, aber dies war auch ein schwaches Feld für mich, der keine Chance hatte, systematisch Programmiersprachen zu lernen. Ich bin noch nicht gut darin, aber ich fange an, Verdacht zu bemerken.

[Verwendung von Python defaultdict] (https://qiita.com/xza/items/72a1b07fcf64d1f4bdb7) ・ ・ ・ Es wird oft verwendet, um zu beurteilen, ob es bei Verwendung einer Schleife einmal herausgekommen ist. Wenn der maximale Wert, der ausgegeben wird, ungefähr $ 10 ^ 6 $ beträgt, gibt es kein Problem mit einer Liste, die mit Null initialisiert wurde. Wenn der Wert jedoch bis zu $ 10 ^ 9 $ beträgt, wird der Umfang der räumlichen Berechnung überschritten und die Liste wird mit Null initialisiert. Kann nicht verwendet werden, daher ist defaultdict praktisch. Sobald Sie sich daran gewöhnt haben, ist es sehr einfach und bequem, also möchte ich auf jeden Fall, dass Sie es beherrschen.

[Eine Besonderheit, wie man "zu viel geteilt durch 1000000007" findet! ~ Vom inversen Element zum diskreten Logarithmus ~] (https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a) ・ ・ ・ Mod-Verarbeitung ist häufig, aber ich war schon immer ein schwaches Feld. Nachdem ich diesen Artikel gelesen hatte, konnte ich den Satz von Fermat so gut wie möglich verstehen, sodass ich mich weniger schwach fühlte.

[^ 1]: Anzeige des Schwierigkeitsgrades im AtCoder-Problem.

[^ 2]: Es gibt zwei Arten von Berechnungsbeträgen: Zeitberechnungsbeträge und räumliche Berechnungsbeträge. Da die Häufigkeit des Engpasses jedoch überwiegend Zeitberechnungsbeträge sind, denke ich, dass es sich um Zeitberechnungsbeträge handelt, sofern nicht anders angegeben. Bitte.