[PYTHON] AtCoder Andachtsnotiz (11/12)
Es ist ein Memo der Hingabe in AtCoder. Es tut mir leid, dass es eine Mischung aus Tönen und Tönen gibt.
AGC008B - Contiguous Repainting
diff:1821 Ergebnis: 20 Minuten zur Prüfung, 10 Minuten zur Grundimplementierung, ∞ Minuten zur Fehlerbehebung → Der Lambda-Ausdruck der Akkumulationsfunktion war falsch
Einreichung: https://atcoder.jp/contests/agc008/submissions/18058051
Erwägung
Betrachten Sie zunächst ** Malen so viel wie möglich ** (schwarz für $ a \ _i \ geqq 0 $, weiß für $ a \ _i \ <0 $). Zu diesem Zeitpunkt schien der Humor klar zu sein, selbst wenn ich ihn richtig anwendete, also dachte ich über ** Malen in der richtigen Reihenfolge vom Rand ** nach. Zu diesem Zeitpunkt können Sie bequem alle bis auf die $ k $ Quadrate an den Rändern malen, und alle $ k $ Quadrate an den Rändern können schwarz oder weiß gestrichen werden. Daher dachte ich, dass es besser wäre, die $ k $ Quadrate am linken Ende und die $ k $ Quadrate am rechten Ende bequem zu malen, aber wie in Beispiel 2 das $ zwischen ** ** kann optimal sein, wenn nur k $ -Zellen nicht bequem gemalt werden können. Daher dachte ich, wenn diese ** verallgemeinert ** wären, könnten die fortlaufenden $ k $ -Zellen in einer Farbe mit Weiß oder Schwarz gemalt werden, und die anderen Teile könnten auf bequeme Weise gemalt werden. Zu diesem Zeitpunkt habe ich es gelöst, indem ich nur ausreichend gezeigt habe. Wenn ich mich jedoch beruhige, indem ich am Ende überschreibe, werden $ k $ -Zellen angezeigt, die in einer Farbe durchgehend sind, sodass ich auch die Notwendigkeit zeigen kann. **. Wenn Sie dies nur mit der kumulierten Summe implementieren, ist dies wie folgt, wenn Sie es in ein Diagramm schreiben.
Zu diesem Zeitpunkt habe ich es gerade implementiert, aber ich habe einen Fehler gemacht **, weil ich einen Lambda-Ausdruck für die Funktion verwendet habe, die an die ** Akkumulationsfunktion übergeben wurde. Ich möchte ** vorverarbeitete Iterables an die Akkumulationsfunktion übergeben **.
Es scheint auch eine typische Idee zu sein, die Operation ** beim Problem des Überschreibens umzukehren. Das ist wahr, und das Überschreiben ist eine destruktive Operation, während es durch Umkehren ** zerstörungsfrei gemacht werden kann, was praktisch ist. Ich denke, dies ähnelt der Tatsache, dass es bequem ist, es als umgekehrte Reihenfolge zu betrachten, wenn Kanten in einem Union Find-ähnlichen Problem geschnitten werden.
Betrachtung
** Ich habe einen Fehler gemacht, weil ich versucht habe, den Code kurz zu halten **, wie in der vorherigen Ausgabe ** Ich überspringe die Implementierung nicht ** (lernen ...), es tut mir leid für die Gedanken ...
DDPC2020 Qualifying D --Digit Sum Replace
diff:1650 Ergebnis: Diskussion: ca. 25 Minuten, Implementierung: Keine, AC Einreichung: https://atcoder.jp/contests/ddcc2020-qual/submissions/18059365
Erwägung
Zuerst habe ich mich gefragt, was mit der Kombination von Zahlen passieren würde, die nach Durchführung eines Experiments das Minimum darstellen würde, aber ich dachte, dass es schwierig sein würde, ehrlich zu simulieren, weil die Zahl groß ist.
Als ich mich auf die Operationen konzentrierte, bemerkte ich daher, dass sie in ** (1) Operationen unterteilt werden können, die die Anzahl der Ziffern reduzieren, und (2) Operationen, die die Anzahl der Ziffern nicht reduzieren **. Zu diesem Zeitpunkt habe ich festgestellt, dass im Fall von (1) die Anzahl der Ziffern nur reduziert wird und sich die Summe der Zahlen nicht ändert **, und im Fall von (2) wird die Anzahl der Ziffern nicht reduziert, aber die Summe der Zahlen wird gleichmäßig um 9 reduziert.
Mit anderen Worten, hier sollte die Endbedingung umformuliert werden, um mit den Operationen von ① und ② übereinzustimmen, und es ist ersichtlich, dass die Anzahl der Ziffern eine Ziffer und die Summe der Zahlen 9 oder weniger sein sollte. Außerdem habe ich festgestellt, dass die Operationen ** ① und ② unabhängig voneinander sind und sich nicht gegenseitig stören **, sodass die Häufigkeit ** eindeutig aus der ursprünglichen Anzahl von Ziffern bzw. der Summe der ursprünglichen Zahlen bestimmt wird. Hier kann das erstere leicht durch (die Anzahl der ursprünglichen Ziffern) -1 erhalten werden, das letztere jedoch nicht (der Quotient der ursprünglichen Summe der durch 9 geteilten Zahlen), und wenn der Rest nach dem Teilen durch 9 0 ist, ist es von diesem Wert. Es ist notwendig, -1. Daher ist die maximale Anzahl von Runden die Summe der Anzahl von Operationen (1) und (2).
✳︎ Summe der Zahlen… Gesamtzahl jeder Ziffer
Betrachtung
Es dauerte eine Weile, bis ich den Knebel bemerkte, und für einen Moment, als ich ihn bemerkte, ist dieser Typ schwierig, aber ** sollte ich auf das Ausmaß der Betriebsänderung achten **?
diff:1564 Ergebnis: Diskussion + Implementierung: 15 Minuten, 15 Minuten, um die Lügenlösung zu reparieren, AC Einreichung: https://atcoder.jp/contests/agc002/submissions/18058456
Erwägung
Erstens, je mehr Sie schneiden, desto kürzer ist das Seil. ** Ich möchte ein möglichst langes Seil im Rücken lassen **. Auch das Schneiden des inneren Knotens macht es nicht bequem, also ** schneiden Sie den Endknoten **.
Mit anderen Worten, ich dachte, dass dies durch die gierige Methode geschehen könnte, das kürzere der beiden Seile am Ende zu schneiden, aber dies ist das Seil, das geschnitten werden muss, wenn ** die Längen der Seile gleich sind ** Die Antwort ändert sich mit dieser Methode, was schwierig ist. Beispielsweise existieren die folgenden Fälle als Eckfälle. (Wie ich später bemerkte, lässt diese Methode das längste Seil auf einer Seite, aber es ist nicht der beste Weg, es zu schneiden, wenn die Seite des Seils kurz ist ...)
Wenn Sie jedoch über diese Überlegung nachdenken, bleiben beim Schneiden vom Ende nur zwei Seile ** übrig, und wenn die Länge dieses Seils $ L $ oder mehr beträgt, liegt dies davor. Mir ist auch aufgefallen, dass die Länge des Seils immer über $ L $ liegt. Außerdem befinden sich die beiden am Ende verbleibenden Seile auch im Ausgangszustand nebeneinander. Wenn Sie also alle benachbarten Seilpaare (Straße $ N-1 $) durchsuchen, um festzustellen, ob mehr als $ L $ vorhanden sind Ist gut. (** Achten Sie auf den Endzustand! **)
Betrachtung
Impressionen: Ich habe es implementiert, weil ich dachte, es wäre eine Methode zur Lösung von Lügen, aber als ich meine Überlegungen vertiefte, konnte ich AC, ** Es ist wichtig, vollständig zu denken, ohne es zu werfen **!
Recommended Posts