Ich werde erklären, wie man ** A-, B-, (C), D-Probleme ** des ** AtCoder Beginners Contest 165 ** mit ** Python 3 ** so sorgfältig wie möglich löst.
Ich möchte eine Lösung erklären, die die folgenden drei Punkte erfüllt, nicht nur eine Methode, die gelöst werden kann.
5/17 C Das Problem war sehr schwierig und der Artikel war lang, deshalb habe ich ihn in einen separaten Artikel aufgeteilt.
[AtCoder Erklärung] Steuern Sie das C-Problem von ABC165 mit Python!
ABC165
Datum: 2020-05-02 (Sa) 21:10 ~ 2020-05-02 (Sa) 22:50 (100 Minuten) Eine Anzahl von Personen, die Fragen stellen: 11626
| Performance | AC | Ergebnis | Zeit | Rangfolge | Richtlinie |
|---|---|---|---|---|---|
| 400 | AB-- | 300 | 14 Minuten | 73 25 .. | Teeleistung |
| 600 | A--D | 500 | 98 Minuten | 5940 | Brown Rate bei 8 mal |
| 800 | AB-D | 700 | 75 Minuten | 4505 | Grüne Leistung |
| 1200 | ABCD | 1000 | 93 Minuten | 2194 | Wasserleistung |
(Referenz) Me: Performance 1426 ABCD-- 41:05 1379. Platz D wurde zuerst gelöst und an C </ font> zurückgegeben
C-Problem ist der Schwierigkeitsgrad des schwierigen D-Problemniveaus. Wenn Sie nur "herumgehen und alle Antworten überprüfen" sagen, sehen Sie häufig das C-Problem.
Es ist jedoch schwer zu bemerken, dass dieses Problem auf mögliche Sequenzen gerundet werden kann. Darüber hinaus können Sie es nicht lösen, ohne zu wissen, wie alle möglichen Sequenzen erstellt werden.
Andererseits war das D-Problem der übliche Schwierigkeitsgrad des C-Problems. Mit dieser Art von Problemstellung müssen Sie den Mut haben, sich zu beruhigen und das D-Problem zu überprüfen, dann das C-Problem wegzuwerfen und das D-Problem zu lösen.
ABC165A 『We Love Golf』
** Problemseite **: A - Wir lieben Golf ** Schwierigkeit **: ★★ ☆☆☆ ** Punkt **: Mathematik, Umgang während
Wenn Sie wissen, wie man alle Vielfachen von k unter b macht, können Sie es lösen.
Eine einfache Möglichkeit besteht darin, alle Vielfachen von k aufzulisten, die kleiner oder gleich b sind, und "OK" zu setzen, wenn es mindestens eines gibt, das größer oder gleich a ist. Jetzt können Sie mit dem Schreiben von Code beginnen.
Es ist jedoch einfacher, das maximale Vielfache von k unter b zu finden, und wenn es größer oder gleich a ist, die im offiziellen Kommentar-PDF geschriebene Methode "OK". Wenn Sie sich das vorstellen können, schreiben Sie es hier. Ist gut. Ich konnte nicht daran denken.
Ich werde zwei Methoden schreiben.
k = int(input())
a, b = list(map(int, input().split()))
x = 0
#Ich habe das Gefühl, ich kann es etwas schöner schreiben, aber vorerst eine Endlosschleife+in der Pause
while True:
x += k
if a <= x <= b:
print("OK")
break
if x > b:
print("NG")
break
k = int(input())
a, b = list(map(int, input().split()))
#Finden Sie "ein Vielfaches des Maximums k kleiner oder gleich b"
largest = (b // k) * k
if a <= largest:
print("OK")
else:
print("NG")
ABC165B『1%』
** Problemseite **: B-1% ** Schwierigkeit **: ★★ ☆☆☆ ** Punkt **: Behandlung während, Lesen der Problemstellung genau
Tun Sie einfach so, wie es geschrieben steht, aber das Wichtigste steht in Klammern: ** "Schneiden Sie jedes Jahr Geld nach dem Dezimalpunkt ab" **.
Im Fall von C ++ usw. müssen Sie vorsichtig mit Überläufen sein, aber in Python müssen Sie sich darüber keine Sorgen machen. Es ist Python, nicht wahr?
Ich habe am Anfang 100 Yen und es steigt mit Zinseszins um 1% pro Jahr. Wenn Sie dieser Straße folgen, können Sie sie lösen.
Wenn Sie die Problemstellung sorgfältig lesen, werden Sie feststellen, dass sie in Klammern sehr wichtig ist (doppeltes Interesse, ** Kürzung nach dem Dezimalpunkt **).
Lassen Sie uns daher nach dem Dezimalpunkt abschneiden.
Sobald Sie die Problembeschreibung richtig gelesen haben, müssen Sie sie nur noch schreiben.
Selbst wenn Sie die Kürzung nach dem Dezimalpunkt verpassen, ist die Antwort anders, wenn Sie sie mit einem Beispiel überprüfen, sodass Sie feststellen, dass etwas nicht stimmt. Mir ist aufgefallen.
Insbesondere lautet die Antwort für Probe 2 3760 und die Ausgabe 3703, und Probe 3 ist 1706 für 1649.
Beispiel 2 ist die größte Einschränkung von $ 10 ^ {18} $. Ich bin daher zuversichtlich, dass Sie sich in diesem Fall keine Sorgen über Fehler machen müssen.
x = int(input())
year = 0 #Antworten
money = 100 #Anfangswert 100 Yen
#Drehen Sie die Schleife, bis sie über x Yen liegt
while money < x:
money *= 1.01
money = int(money)
year += 1
print(year)
ABC165C『Many Requirements』
** Problemseite **: C - Viele Anforderungen ** Schwierigkeit **: ★★★★★★★★★★★ (Schwierige D-Problemstufe!) ** Typ **: Round-Robin-Idee, Suche mit Tiefenpriorität (andere Methoden sind ebenfalls verfügbar), vergangene Übungen
Zunächst ist es schwierig, die Problemstellung zu lesen und die Bedeutung zu verstehen. Selbst wenn Sie die Bedeutung verstehen, müssen Sie daran denken, alle Sequenzen zu erstellen und zu überprüfen. Und selbst wenn Sie wissen, dass Sie ein Round-Robin machen werden, können Sie es nicht lösen, ohne zu wissen, wie man eine Zahlenfolge macht.
Um ehrlich zu sein, ist es die Schwierigkeit des schwierigen D-Problems.
Was? Sie könnten denken, aber das ist wichtig. Bei AtCoder ist es durchaus üblich, dass sich die Schwierigkeit des Problems umkehrt. Wenn das dahinter stehende Problem eher gelöst werden kann, ist es besser, dies in Bezug auf Punkte zu tun.
Diesmal gab es in C 2500 AC-Leute und in D 5000 AC-Leute, was mehr als das Doppelte des Unterschieds war. Es ist selten, dass es einen solchen Unterschied in der Schwierigkeit gibt, aber es ist oft so, dass es einen kleinen Unterschied in der Schwierigkeit gibt.
Wenn Sie sich auf das Problem konzentrieren, werden Sie nicht auf die Idee kommen, das dahinter stehende Problem zu lösen. Daher ist es wichtig, sich zu beruhigen und sich vom Problem zu entfernen.
Nachdem der Wettbewerb vorbei war, war ich oft frustriert: "Ich hätte dieses Problem lösen können!". Wenn ich also ein wenig nicht verstehe, versuche ich, das Problem dahinter zu überprüfen.
Dieses Mal dachte ich 5 Minuten lang über C nach und hielt es für eine schlechte Idee. Nachdem ich D in 10 Minuten gelöst hatte, kehrte ich zu C zurück und löste es in 15 Minuten.
Es ist lange her, also habe ich es in separate Artikel aufgeteilt. Ich werde auf drei Arten erklären.
--Verwenden Sie itertools.combinations_with_replacement (am einfachsten)
[AtCoder-Kommentar] Gewinnen Sie das ABC165 C-Problem "Many Requirements" mit Python!
Hier sind einige ähnliche Probleme. Die letzten beiden sind etwas schwieriger, aber immer noch einfacher als diese.
Braunstufe: ABC029 C - Brute-Force-Angriff Grüne Stufe: ABC161 D --Lunlun Number Grüne Stufe: Panasonic Programming Contest 2020 D - String Equivalence
ABC165D『Floor Function』 ** Problemseite **: D - Bodenfunktion ** Schwierigkeit **: ★★★ ☆☆ ** Typ **: Mathematik
Wenn Sie gut in Mathematik sind, können Sie die Antwort intuitiv finden. Für diejenigen von uns, die nicht gut in Mathe sind, können wir es herausfinden, indem wir verschiedene Dinge ausprobieren.
Für solche Probleme ist es eine gute Idee, vorerst Zahlen zu ersetzen.
Ich bin froh, dass $ floor (Axe / B) $ groß und $ A \ times {floor (x / B)} $ klein ist.
Sie können sehen, dass letzteres wächst, wenn $ x $ genau ein Vielfaches von $ B $ ist. Nachdem Sie verschiedene Dinge ausprobiert haben, können Sie sehen, dass $ f (x + B) = f (x) $.
Daher muss $ x $ nur im Bereich von $ 0 bis (B-1) $ berücksichtigt werden. Zu diesem Zeitpunkt ist die Subtraktion $ A \ times {floor (x / B)} = 0 $, sodass Sie die Existenz vergessen können.
Jetzt wird $ floor (Axe / B) $ größer, wenn $ x $ größer wird, also sollte $ x $ $ B-1 $ sein. Es gibt jedoch eine Bedingung, dass $ x $ kleiner oder gleich $ N $ ist, daher ist der kleinere Wert von $ N $ und $ B-1 $ die Antwort.
Wenn Sie es verstehen, ist es nur eine Frage des Schreibens.
a, b, n = list(map(int, input().split()))
x = min(b - 1, n) # b-1 ist gut, aber manchmal erlaubt die Obergrenze n dies nicht.
ans = int(a * x / b) #Berechnung. Der letzte Abschnitt ist 0, Sie müssen ihn also nicht schreiben.
print(ans)
Recommended Posts