Ich werde das Memo der Hingabe wieder aufnehmen. Ich werde es fragiler zusammenfassen als übliche Artikel, und ich werde es überprüfen, sobald ich es löse.
diff:1911 Ergebnis: Wechselstrom für insgesamt ca. 2 Stunden
Einreichung: https://atcoder.jp/contests/agc014/submissions/18039440
Bewegen Sie sich zunächst → öffnen → bewegen →…. Wenn also ein Raum noch nicht frei ist, können Sie nicht in diesen Raum gehen, was ein Problem darstellt. Daher dachte ich, dass es besser wäre, ** die Anzahl der Bewegungen und die Mindestanzahl der freien Räume ** zu verwalten, aber dies ist nicht zählbar und es scheint, dass es viel Berechnung erfordern wird. Wenn es sich hier um ein Muster von Öffnen → Bewegen → Öffnen →… handelt (** Denken Sie daran, es in einem einfachen Fall fallen zu lassen! **), können Sie sehen, dass Sie nur den Raum am nächsten Ende auswählen müssen ($ \ weil $ dieser Raum). Weil Sie alle geschlossenen Räume öffnen können, bis Sie dazu kommen).
Daher ist ersichtlich, dass es nur notwendig ist, ** nur den ersten Satz zu trennen **. Mit anderen Worten, da Sie nur die Räume verfolgen können, die im ersten Zug nicht geöffnet sind, sollten Sie BFS ** berücksichtigen, das nur die Räume verfolgt, die geöffnet sind und deren Tiefe weniger als $ k $ beträgt. Im Muster von Öffnen → Bewegen → Öffnen →… danach muss nur noch der kürzeste Weg vom Raum, der von BFS verfolgt werden kann, zum Endraum (vier Richtungen) und zur Decke (Länge des kürzesten Weges) gefunden werden. / k) +1 ist die Antwort. Daher ist der Mindestwert in dem Raum, der die Bedingungen erfüllt, die Antwort.
Es war nicht schlecht zu glauben, dass es gut wäre, zwei Informationen über die Anzahl der Bewegungen und die Mindestanzahl an freien Räumen zu haben, aber es dauerte einige Zeit, bis die Idee kam, die Operationsmethode zu entwickeln. Es war nicht gut, zu weit zu gehen. Ich möchte die Haltung berücksichtigen, Probleme aus mehreren Blickwinkeln zu betrachten, was darauf hindeutet, dass die Anzahl der zu lösenden Probleme gering ist.
diff:2803 Ergebnis: Wechselstrom in 30 Minuten zur Prüfung + Implementierung, 50 Minuten zur Fehlerbehebung Einreichung: https://atcoder.jp/contests/agc012/submissions/18040503
** Konzentriere dich auf Kugeln der gleichen Farbe $ c $ **, die Kombination der beiden Kugeln muss kleiner als $ x $ sein. Zu diesem Zeitpunkt kann durch Auswahl eines der beiden Bälle mit der Farbe $ c $ und dem kleinsten Gewicht ** der andere Ball so schwer wie möglich gemacht werden. Zusätzlich können alle Anordnungen zwischen Bällen mit einem Gewicht von weniger als $ x $ zusammen mit dem kleinsten Ball der Farbe $ c $ ($ \ weil $ ** Ball mit minimalem Gewicht) realisiert werden. Sie sollten immer **) auswählen. … ①
Wenn Sie auch ** verschiedene Bälle ** notieren, können Sie den Ball mit dem geringsten Gewicht aller farbigen Bälle ** (Farbe ist $ c $) als einen der Bälle auswählen. Kann auf die gleiche Weise wie besprochen werden. Wie bei der anderen Kugel können Sie jedoch nur eine Kugel auswählen, deren Farbe nicht $ c $ ** ist. Daher ist ersichtlich, dass für Bälle mit einer Farbe von $ c $ ** der Ball mit dem geringsten Gewicht unter denen mit einer anderen Farbe als $ c $ ausgewählt werden sollte. … ②
Aus dem Obigen können unter Berücksichtigung eines Prim-Set-Systems von Bällen, deren Positionen vertauscht werden können, die Positionen zwischen beliebigen Elementen innerhalb des Prime-Sets ausgetauscht werden. Daher können Sie die Operation in der Reihenfolge ① und ② teilen und die Vereinigung im Union Find-Baum ausführen. Wenn es ein Prime-Set-System gibt, ist die Anordnung der Bälle in einem Prime-Set der Größe $ l $ $ l! $. Da Sie die Reihenfolge der Kugelfarben ** ermitteln möchten, müssen Sie die Kugeln mit überlappenden Farben durch den Grad der Überlappung ** teilen. Hier wird der Duplizierungsgrad als $ l ^ {'}! $ Definiert, wenn die Anzahl der Kugeln einer bestimmten Farbe $ c ^ {'} $ $ l ^ {'} $ beträgt.
Um das Obige zu implementieren, sollte die folgende Datenstruktur und dergleichen vorbereitet werden.
colors[i]:=Index i Kugelfarbe
color[i]:=Von der Kugel, die Farbe wird i(Gewicht,Index)Bestelltes Set, das speichert
weight:=(Gewicht,Index)Bestelltes Set, das speichert
Schauen Sie sich in (1) der Reihe nach $ color [i] $ an und die Kugeln, die mit dem Mindestgewicht kombiniert werden können, in der Reihenfolge der Kugeln mit dem geringsten Gewicht. Betrachten Sie in (2) $ weight $ in der richtigen Reihenfolge und betrachten Sie Bälle, die sich von der kleinsten Ballfarbe $ c $ unterscheiden, auf dieselbe Weise wie in (1), und betrachten Sie dann Bälle mit einer Farbe, die auf dieselbe Weise wie in (1) zu $ c $ wird. Mal schauen. Einzelheiten finden Sie im eingereichten Code.
Die Diskussion hat funktioniert, aber ich habe nicht bemerkt, dass ** ich etwas anderes zwischen der Diskussion und der Implementierung gemacht habe **. Es ist ein Muster, an das man sich leicht binden kann, daher möchte ich es besonders beachten, wenn ich Fehler behebe.
Tenka1 Programmer Contest 2017 D - IntegerotS
diff:1794 Ergebnis: 20 Minuten zur Prüfung, 15 Minuten zur grundlegenden Implementierung, 15 Minuten zur Fehlerbehebung Einreichung: https://atcoder.jp/contests/tenka1-2017/submissions/18043771
Erstens wirkt sich die Auswahl von $ A \ _j (= A \ _i) $ bei Auswahl eines bestimmten $ A \ _i $ nicht bitweise aus, sodass die angegebenen Informationen den gleichen Wert $ A \ _i $ haben Durch Zusammenfügen kann $ A \ _i $ unterschiedliche Werte haben. Betrachtet man die Bedingungen der Problemstellung darunter, so scheint es, dass sie mit einer Idee nahe der Ziffer DP gelöst werden kann, da es Bedingungen von ** $ k $ oder weniger gibt. Außerdem bemerkte ich, dass ich kein Element mit $ MSB $ auswählen konnte, das größer als $ MSB $ ($ m $) von $ k $ ist, und entschied mich daher, ** Fälle durch $ MSB $ von jedem Wert zu trennen **. .. Derzeit können Sie nicht $ MSB $ auswählen, das größer als $ m $ ist. Wenn Sie nur die Elemente auswählen, deren $ MSB $ kleiner als $ m $ ist, wissen Sie, dass dies bitweise oder kleiner als $ k $ ist, sodass Sie solche Elemente auswählen können. Wenn ich jedoch $ msb $ habe, das mit $ m $ identisch ist, wurde mir klar, dass es in den Ziffern unter ** $ msb $ ** weniger als $ k $ sein sollte, also ** in der Reihenfolge von der oberen Ziffer DP * Ich habe mich für eine Politik in der Nähe von * entschieden. Mit anderen Worten, der Satz von Zahlen, der ausgewählt werden kann, wenn eine bestimmte Ziffer betrachtet wird, ist $ s $ wie folgt. (Übrigens ist die Implementierung einfacher und schneller, indem verwaltet wird, ob $ s $ mit einem Bool-Array ausgewählt ist oder nicht.)
Wenn das $ i $ -Bit angezeigt wird, wird die folgende Verarbeitung ausgeführt, bevor das $ i-1 $ -Bit verarbeitet wird.
(1) Wenn dieses Bit von $ k $ gesetzt ist Es ist einer der Lösungskandidaten, weil bitweise oder kleiner als $ k $ wird, indem nur die Anzahl der in $ s $ enthaltenen ausgewählt wird, die dieses Bit nicht haben.
(2) Wenn dieses Bit von $ k $ nicht gesetzt ist Wenn Sie eine Zahl mit gesetztem Bit wählen, bitweise oder größer als $ k $, ** sind solche Zahlen von $ s $ ** ausgeschlossen und bitweise oder nicht immer kleiner als $ k $. Es gibt keine Kandidaten für eine Lösung.
Der Maximalwert unter den Lösungskandidaten, die durch Ausführen des obigen mit beliebigen Bits erhalten werden, kann erhalten werden. Außerdem wird oben nur die Verarbeitung von weniger als $ k $ durchgeführt, und die Verarbeitung von (1) und (2), wenn ** $ i = 0 $ ist, kann als Verarbeitung von $ k $ oder weniger ** durchgeführt werden, also (1) Im Fall von können Sie jedes in $ s $ enthaltene Element auswählen, und im Fall von (2) können Sie jede in $ s $ enthaltene Zahl auswählen, deren Bits nicht gesetzt sind. Und da es keine msb von ** $ k = 0 $ ** gibt, sollte zu diesem Zeitpunkt der Wert des in $ s $ enthaltenen 0-Elements im Anfangszustand ausgegeben werden.
(✳︎)… Der in der Ziffer DP (Problem in der Nähe) zu beachtende Punkt ist, dass ** er unter einer bestimmten Ziffer ** liegen sollte. In den folgenden Fällen ** Seien Sie jedoch nur vorsichtig, wenn die Werte gleich sind **.
Ich kannte die Art von Eckkoffer, die ich bisher gesehen hatte, aber ich trat darauf. ** Ich möchte das Teil, das als Eckkoffer erscheint, hervorheben, wenn ich überlege **.
diff:1404 Ergebnis: Diskussion 10 Minuten, Grundlegende Implementierung 10 Minuten, Fehlerbehebung ∞ Minuten → Überprüfen und bestätigen Sie, dass es eine Lösung gibt, und nehmen Sie dann den Fehler AC Einreichung: https://atcoder.jp/contests/agc020/submissions/18056229
(Im Folgenden wurde $ k $ in der Problemstellung durch $ n $ ersetzt, aber keine Sorge.)
Erstens muss $ a [n-1] $ 2 sein. Zu diesem Zeitpunkt frage ich mich, welcher der minimalen und maximalen Werte leichter zu finden ist. Zu diesem Zeitpunkt sollte die Konstruktion des Mindestwerts so klein wie möglich gemacht werden, damit es am Ende jeder Runde ein Vielfaches von ** $ a [i] $ ist **, damit ich sofort daran denken kann. Mit anderen Worten, wenn $ check [i] $: = (die Anzahl der nach der Runde $ i $ verbleibenden Kinder ist vorbei), ist $ check [i] = \ lceil \ frac {check [i + 1]} {a [ Das Minimum ist i]} \ rceil \ times a [i] $ (es gilt nicht immer, wie Sie in Beispiel 2 sehen können).
Um das Ergebnis basierend auf dem Minimum zu maximieren, beträgt das Maximum ** $ check [i + 1] + a [i] -1 $ oder weniger für $ check [i] $. Es sollte die Zahl von $ a [i] $ ** sein, also $ check [i] = \ lfloor \ frac {check [i + 1] + a [i + 1] -1} {a [i]} \ rfloor \ times a [i] $ ist die Antwort.
Wenn es auf dem Minimalwert hält, hält es tatsächlich auf dem Maximalwert, so dass es in ** Stufen als Konstruktion zum Minimalwert unterteilt werden sollte → die Beurteilung, ob das konstruierte Produkt korrekt ist → die Konstruktion des Maximalwerts ** Ich habe einen Fehler gemacht, weil ich die Konstruktion und das Urteil zur minimalen Zeit zur gleichen Zeit gemacht habe. ** Ich möchte bedenken, dass ich ein Programm entwerfen werde, das weniger Fehler verursacht, selbst wenn der Schreibaufwand zunimmt.
Außerdem wurde es überflutet ... Ich habe einen Fehler gemacht, indem ich gleichzeitig die Konstruktion und die Beurteilung von Eckfällen durchgeführt habe, z. B. ** Die Implementierung erfolgt separat, ohne zu überspringen **.
Recommended Posts