[PYTHON] AtCoderBeginnerContest161 Review & Summary (zweite Hälfte)

AtCoder ABC161 Dies ist eine Zusammenfassung der Probleme des AtCoder-Anfängerwettbewerbs 161, der am 04.04.2020 (Sa) ausgehend von Problem A unter Berücksichtigung der Berücksichtigung durchgeführt wurde. Die zweite Hälfte befasst sich mit dem DEF-Problem. Klicken Sie hier für die erste Hälfte. Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

D Problem Lunlun Nummer

Problemstellung Wenn die positive Ganzzahl $ X $ die folgenden Bedingungen erfüllt, wird $ X $ als Run-Run-Zahl bezeichnet. ・ Wenn $ X $ in Dezimalschreibweise (ohne führende Null) ausgedrückt wird, beträgt der Absolutwert der Differenz für die Werte zweier benachbarter Ziffern 1 oder weniger. Zum Beispiel sind 1234, 1, 334 Run-Run-Nummern, aber 31415, 119, 13579 sind keine Run-Run-Nummern. Angesichts der positiven ganzen Zahl $ K $. Finden Sie die K-te Run-Run-Nummer aus der kleinsten.

Es war $ 1 \ leq K \ leq 10 ^ 5 $, also dachte ich, es würde ausreichen, die Run-Run-Zahlen von der kleinsten mit einer rekursiven Funktion zu zählen, und ich war sehr glücklich, sie zu lösen, als ich das Programm schrieb. Als ich es gelöst habe, war es Run-Run, aber als ich das Problem sah, lief es überhaupt nicht. Ich werde den eingereichten Code so veröffentlichen, wie er ist.

abc161d.py

def check(mae, keta, count, k):
    if keta == 0:
        count += 1
        if count == k:
            ans = mae
        else:
            ans = -1
        return count, ans
    if mae == 0:
        count, ans = check(0, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(1, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    elif mae == 9:
        count, ans = check(8, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
        count, ans = check(9, keta - 1, count, k)
        if ans >= 0:
            ans += mae * 10 ** keta
            return count, ans
    else:
        for i in [-1, 0, 1]:
            count, ans = check(mae + i, keta - 1, count, k)
            if ans >= 0:
                ans += mae * 10 ** keta
                return count, ans
    return count, ans

k = int(input())
if k < 10:
    print(k)
else:
    count = 9
    flag = 0
    for keta in range(2, 1000):
        for sento in range(1, 10):
            count, ans = check(sento, keta - 1, count, k)
            if ans >= 0:
                print(ans)
                flag = 1
                break
        if flag == 1:
            break

Als ich das Programm schrieb, kam ich auf eine rekursive Funktion und dachte, dass ich beim Erstellen einer Run-Run-Nummer mit $ m $ -Ziffern diese erstellen könnte, indem ich die Nummer von der höchsten Position im Dendrogramm aus entscheide. Zum Beispiel kann die 3-stellige Run-Run-Nummer 1 ** ab 1 erhalten werden, wie in der folgenden Abbildung gezeigt. Es sollte beachtet werden, dass es zwei Arten der Verzweigung gibt, wenn es 0 und wenn es 9 ist, und wenn Sie darauf achten können, geben Sie danach die Variable zum Zählen und die Informationen darüber ein, über welche Ziffer Sie gerade in der Funktion nachdenken. Wenn Sie gierig suchen, können Sie die Antwort rechtzeitig finden.

E Problem Yutori

Problemstellung Takahashi hat beschlossen, ab morgen an $ K $ der $ N $ Tage zu arbeiten. Wählen Sie anhand der Ganzzahl $ C $ und der Zeichenfolge $ S $ einen Arbeitstag aus, der die folgenden beiden Bedingungen erfüllt. ・ Wenn Sie einen Tag arbeiten, werden Sie nicht unmittelbar danach für den $ C $ -Tag arbeiten. ・ Wenn das $ i $ -Zeichen von $ S $ $ x $ ist, funktioniert es nach $ i $ Tagen ab heute nicht mehr. Bitte fragen Sie nach allen Tagen, an denen Takahashi arbeitet.

Ich hatte es zum Zeitpunkt des Wettbewerbs eilig, daher konnte ich die Bedeutung von "Wenn das $ i $ -Zeichen von $ S $ $ x $ ist, funktioniert es in $ i $ Tagen ab heute nicht mehr richtig" lesen und ging sofort zum nächsten Problem über. .. Nachdem ich den Kommentar gelesen hatte, bemerkte ich einen Fehler beim Lesen, aber selbst wenn ich beim Lesen keinen Fehler gemacht hatte, konnte ich ihn meiner Meinung nach nicht lösen, sodass ich noch etwas lernen konnte. Ich fragte mich, ob ich die Erfahrung hatte, zu bemerken, dass es bereits im Kommentar geschrieben war. Code von Kiri8128, der die AC in einem frühen Stadium des eingereichten Codes bestanden hat 11525396) wurde als Referenz verwendet. @ kiri8128

abc161e.py

n, k, c = map(int, input().split())
S = [1 if a == "o" else 0 for a in input()]
count = 0
X = [0] * n
Y = [0] * n
i = 0
while i < n:
    if S[i]:
        count += 1
        X[i] = 1
        # print(i+1)
        i += c + 1
    else:
        i += 1
if count > k:
    exit()
i = n - 1
while i >= 0:
    if S[i]:
        Y[i] = 1
        # print(i+1)
        i -= c + 1
    else:
        i -= 1
for i in range(0, n):
    if X[i] and Y[i]:
        print(i + 1)

Es war hilfreich, wie man S. empfängt. Danach weiß ich nicht, wie ich eine Lösung finden soll, wenn ich dieses Problem sehe, aber ich halte es für wichtig, trotzdem viele Probleme zu lösen, deshalb werde ich mich dem widmen. Ich habe print (i + 1) für diejenigen auskommentiert, die es auch nach dem Lesen der Erklärung nicht verstanden haben. Wenn Sie es also auskommentieren und das Beispiel lösen, werden Sie verschiedene Dinge sehen. Das unten gezeigte Eingabebeispiel 1 dient als Beispiel.

11 3 2 
ooxxxoxxxoo

Die Druckausgabe in der ersten for-Anweisung ist 1, 6, 10 und die Druckausgabe in der zweiten for-Anweisung ist 11, 6, 2. Daher lautet die Antwort 6. Wenn Sie diese für andere Beispiele auf die gleiche Weise ausprobieren, ist es einfacher zu verstehen, warum die Antwort herauskommt. (Ich konnte keine gute Erklärung im Text finden (Schweiß))

F Problem Division oder Subtraktion

Problemstellung Bei einer positiven ganzen Zahl $ N $. Bestimmen Sie eine Ganzzahl $ K $, die größer oder gleich 2 und kleiner oder gleich $ N $ ist, und wiederholen Sie die folgende Operation, bis $ N $ kleiner als $ K $ ist. ・ Operation: Wenn $ N $ durch $ K $ teilbar ist, ersetzen Sie $ N $ durch $ N / K $. Wenn nicht, ersetzen Sie $ N $ durch $ N - K $. Wie viele Möglichkeiten gibt es, $ K $ zu bestimmen, damit $ N $ schließlich 1 wird?

Zum Zeitpunkt des Wettbewerbs habe ich das E-Problem schnell aufgerundet und das F-Problem in Frage gestellt. Der Grund ist, dass das Eingabebeispiel 2 "3141" ist und $ K $ feststellt, dass 3141 und 3140 zuerst in der Antwort enthalten sind und dass 3140 die Antwort um $ N- um 1570, 785 ist ... Es stellt sich heraus, dass alle Brüche von 1 $ in der Antwort enthalten sind. 「2, 4, 5, 10, 20, 157, 314, 628, 785, 1570」 Von hier aus weiß ich nicht, wie ich zählen soll, dass $ K = 2 $ in 6 von Eingabebeispiel 1 enthalten ist und die Zeit vorbei ist (Schweiß). Mit ein wenig Nachdenken habe ich nur überprüft, ob der $ N $ -Fraktion die Bedingung erfüllt. Da der $ K $ -Kandidat ein Bruchteil ist, kann er geteilt werden, bis er bricht. Wenn er nicht bricht, überprüfen Sie den Rest. Wenn er 1 ist, ist er 1, wenn $ K $ mehrmals subtrahiert wird, sodass ersichtlich ist, dass die Bedingung erfüllt ist.

abc161f.py

def make_divisors(n):
    divisors = []
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

n = int(input())
if n == 2:
    print(1)
elif n == 3:
    print(2)
elif n == 4:
    print(3)
else:
    count = 2
    check_list = make_divisors(n-1)
    count += len(check_list)
    check_list = make_divisors(n)
    for k in check_list:
        temp_n = n // k
        while(True):
            if temp_n % k == 0:
                temp_n = temp_n // k
            elif temp_n % k == 1:
                count += 1
                break
            else:
                break
    print(count)

Da es sich um ein Huhn handelt, ist n, wenn es klein ist, in Fälle unterteilt, aber es sollte möglich sein, es ohne es zu lösen. Die Aufschlüsselung von count = 2 ist $ N $ und $ N-1 $. Ich möchte in der Lage sein, dieses F-Problem rechtzeitig zu lösen, also werde ich mein Bestes geben, um fortzufahren.

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.