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

AtCoder ABC174 Dies ist eine Zusammenfassung der Probleme des AtCoder Beginner Contest 174, der am 2020-08-02 (So) in der Reihenfolge von Problem A unter Berücksichtigung der Berücksichtigung stattfand. 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 Alter Altar

Problemstellung Der Altar ist mit $ N $ Steinen versehen, die von links nach rechts aufgereiht sind. Die Farbe des Steins $ i $ th $ (1 \ leqq i \ leqq N) $ von links wird als Buchstabe $ c_i $ angegeben, der rot ist, wenn $ c_i $ 'R'ist, und weiß, wenn er' W 'ist. Sie können die folgenden zwei Vorgänge beliebig oft in beliebiger Reihenfolge ausführen. ・ Wählen Sie $ 2 $ Steine (nicht unbedingt nebeneinander) und ersetzen Sie sie. ・ Wählen Sie $ 1 $ Steine und ändern Sie die Farbe der Steine (rot für weiß, weiß für rot). Laut der Wahrsagerin verursacht der weiße Stein links vom roten Stein eine Katastrophe. Wie viele Operationen sind erforderlich, um den Staat ohne solche weißen Steine zu erreichen?

Als ich das Problem las, dachte ich, ich könnte es einfach lösen, indem ich "$ 2 $ Steine (nicht unbedingt nebeneinander) auswähle und sie ersetze". Wenn Sie nicht "・ $ 1 $ Steine auswählen und die Farbe der Steine ändern (rot für weiß, weiß für rot)" verwenden, wird der Status ohne die endgültige Antwort festgelegt. Zum Beispiel bei $ N = 9 $ 'WRWWWRRWR' Eingabe ist 'RRRRWWWWW' Die Antwort kann gegeben werden, indem die minimale Operation berücksichtigt wird, so dass. Dies ist die Anzahl der roten Steine, die in der Eingabe $ N_r $ enthalten sind, und die Anzahl der weißen Steine von $ 1 $ bis $ N_r $ th in der Eingabe ist die erforderliche Anzahl von Operationen. (Im Fall des Beispiels ist $ 3 $ die Antwort, da es sich um die Anzahl der weißen Steine im $ 1 $ bis $ 4 $ th'WRWW'of'WRWWWRRWR handelt.)

abc174d.py

n = int(input())
mozi = input()
a_list = []
for i in range(n):
    if mozi[i] == 'W':
        a_list.append(0)
    else:
        a_list.append(1)
r_count = sum(a_list)
print(r_count - sum(a_list[0:r_count]))

E Problemprotokolle

Problemstellung Es gibt $ N $ -Protokolle, von denen jedes $ A_1, A_2, ⋯, A_N $ ist. Sie können diese Protokolle auf insgesamt $ K $ mal schneiden. Wenn Sie ein Protokoll der Länge $ L $ an der Position von $ t (0 <t <L) $ von einem Ende abschneiden, wird es in Protokolle der Länge $ t, L - t $ unterteilt. Nachdem Sie das Protokoll auf insgesamt $ K $ aufgeschnitten haben, ermitteln Sie die Mindestlänge des längsten Protokolls und geben Sie den auf die nächste ganze Zahl aufgerundeten Wert aus.

Ich habe die Dichotomie nicht bemerkt und habe gierig nach $ x = 1 $ gesucht, also konnte ich sie während des Wettbewerbs nicht lösen.

abc175e.py

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
if k == 0:
    print(a_list[0])
else:
    start = 1
    end = a_list[0]
    x = (start + end) // 2 
    while True:
        k_count = 0
        flag = 1
        for a in a_list:
            temp_k = 0
            if a % x == 0:
                temp_k = a // x - 1
            else:
                temp_k = a // x
            if temp_k == 0:
                flag = 1
                break
            k_count += temp_k
            if k_count > k:
                flag = 0
                break
        if flag == 1:
            end = x
        if flag == 0:
            start = x
        next_x = (start + end) // 2
        if next_x == x:
            if flag == 1:
                print(x)
            if flag == 0:
                print(x + 1)
            break
        x = next_x

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