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

AtCoder ABC169 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 169, der am 2020-05-31 (So) stattfand, beginnend mit Problem A unter Berücksichtigung der Berücksichtigung. Die zweite Hälfte befasst sich mit dem DE-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 Div Game

Problemstellung Eine positive ganze Zahl $ N $ wird angegeben. Wiederholen Sie die folgenden Vorgänge für $ N $. ・ Wählen Sie zunächst eine positive Ganzzahl $ z $ aus, die alle folgenden Bedingungen erfüllt. ◦ Kann ausgedrückt werden als $ z = p ^ e $ unter Verwendung einer bestimmten Primzahl $ p $ und einer positiven ganzen Zahl $ e $ ◦ $ N $ ist teilbar durch $ z $ ◦ Unterscheidet sich von allen in der vorherigen Operation ausgewählten Ganzzahlen ・ Ersetzen Sie $ N $ durch $ N / z $ Finden Sie heraus, wie oft Sie den Vorgang ausführen können.

Vorerst wurde mir klar, dass dieses Problem leicht durch Berücksichtigung der Primfaktoren gelöst werden kann. Deshalb suchte ich nach Artikeln, denen ich immer verpflichtet war, und kopierte den Code für den Faktorisierungsteil. Hochgeschwindigkeits-Primfaktorisierung mit Python - für Wettbewerbsprofis Das Problem ist diesmal, dass Sie, wenn Sie $ k $ eines bestimmten Primfaktors $ p_1 $ haben, überlegen müssen, wie viele Operationen Sie ausführen können, aber die Anzahl der Operationen → die Anzahl der erforderlichen Primfaktoren $ p_1 $ Ist 1 → 1 2 → 3 3 → 6 4 → 10 5 → 15 Es ist eine Differenznummernfolge. Wenn Sie dies berechnen, können Sie sehen, dass die Anzahl der Primfaktoren $ p_1 $, die erforderlich sind, um $ m $ mal zu betreiben, $ \ frac {m (m + 1)} {2} $ ist, also jede Primfaktor-Zerlegung Ich konnte die Antwort erhalten, indem ich berechnete, wie oft die Operation für den Primfaktor ausgeführt werden kann, und sie addierte.

`abc169d.py`


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr
n = int(input())
if n == 1:
    print(0)
else:
    x_list = factorization(n)
    ans = 0
    for x in x_list:
        n = 2
        while True:
            if x[1] < (n * n + n) // 2:
                ans += n - 1
                break 
            n += 1
    print(ans)

Sie müssen nur vorsichtig sein, wenn die Eingabe $ 1 $ ist.

E Problem Count Median

Problemstellung Es gibt $ N $ ganze Zahlen $ X_1, X_2, ⋯, X_N $, von denen wir wissen, dass sie $ A_i \ leq X_i \ leq B_i $ sind. Finden Sie heraus, wie viele mögliche Medianwerte für $ X_1, X_2, ⋯, X_N $ vorliegen.

Ich war zu beschäftigt mit den B- und C-Problemen, aber ich erkannte schnell, dass ich sie lösen konnte, indem ich $ A $ und $ B $ getrennt sortierte und ihre Medianwerte verwendete. Durch Schreiben von Code wird die Zeit abgelaufen, bis die Anzahl der Daten ungerade ist.

In Bezug auf das Problem werden zuerst $ A_1, A_2, ..., A_N $ sortiert, und die resultierende Sequenz lautet $ C_1, C_2, ..., C_N $, und $ B_1, B_2, ..., B_N $ werden sortiert. Infolgedessen lautet die resultierende Sequenz $ D_1, D_2, ..., D_N $.

Eine ungerade Anzahl von Daten

Die Antwort lautet $ D_ {(N + 1) / 2} - C_ {(N + 1) / 2} + 1 $.

Gerade Anzahl von Daten

Die Antwort lautet $ D_ {N / 2} - C_ {N / 2} + D_ {N / 2 + 1} - C_ {N / 2 + 1} + 1 $. Wenn beispielsweise $ C_ {N / 2} = 5, C_ {N / 2 + 1} = 7, D_ {N / 2} = 7, D_ {N / 2 + 1} = 9 $, sind die möglichen Kombinationen ，

	5	6	7
7	6	13/2	7
8	13/2	7	15/2
9	7	15/2	8

Die Antwort lautet $ 6,13 / 2,7,15 / 2,8 $, was 5 $ entspricht. Da diese Antwort die Anzahl der Zeilen + die Anzahl der Spalten der Tabelle -1 ist, kann dieselbe Antwort durch die obige Formel erhalten werden.

`abc169e.py`


n = int(input())
a_list = []
b_list = []
for i in range(0, n):
    a, b = map(int, input().split())
    a_list.append(a)
    b_list.append(b)
a_list.sort()
b_list.sort()
if n % 2 == 0:
    x1 = n // 2 - 1
    x2 = n // 2
    print(b_list[x2] - a_list[x2] + b_list[x1] - a_list[x1] + 1)
else:
    x = n // 2
    print(b_list[x] - a_list[x] + 1)

Wenn das von A nach C eingestellte Problem der übliche Schwierigkeitsgrad ist, hätte ich wahrscheinlich 5 abgeschlossen, aber ich habe das Gefühl, dass ich nicht lernen kann. Als ich einen Job bekam, dachte ich, ich sollte meine Programmierkenntnisse so weit wie möglich verbessern, damit ich das Gefühl habe, dass es meinem Zweck entspricht, und ich würde gerne weiter teilnehmen (ich kann die B- und C-Probleme nicht bestehen.) Wenn die Rate fallen würde, müsste ich Abstand halten). Ich bin diese Woche mit dem F-Problem beschäftigt, daher möchte ich es hinzufügen, auch wenn ich Zeit habe.

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