[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.

Recommended Posts

AtCoderBeginnerContest161 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest164 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest176 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest168 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest169 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest166 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest171 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest174 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest173 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest177 Review & Summary (zweite Hälfte)
AtCoderBeginnerContest175 Review & Summary (erste Hälfte)
AtCoderBeginnerContest164 Review & Summary (erste Hälfte)
AtCoderBeginnerContest169 Review & Summary (erste Hälfte)
AtCoderBeginnerContest174 Review & Summary (erste Hälfte)
AtCoderBeginnerContest173 Review & Summary (Erste Hälfte)
AtCoderBeginnerContest165 Review & Summary (erste Hälfte)
AtCoderBeginnerContest170 Review & Summary (erste Hälfte)
AtCoderBeginnerContest167 Review & Summary (erste Hälfte)
AtCoderBeginnerContest177 Review & Summary (erste Hälfte)
AtCoderBeginnerContest168 Review & Summary (erste Hälfte)
AtCoderBeginnerContest178 Review & Summary (erste Hälfte)
AtCoderBeginnerContest171 Review & Summary (erste Hälfte)
AtCoderBeginnerContest166 Review & Summary (erste Hälfte)
AtCoderBeginnerContest161 Review & Summary (erste Hälfte)
AtCoderBeginnerContest172 Review & Summary (erste Hälfte)
AtCoderBeginnerContest176 Review & Summary (erste Hälfte)
AtCoderBeginnerContest180 Review & Zusammenfassung
AtCoderBeginnerContest181 Überprüfung & Zusammenfassung
AtCoderBeginnerContest182 Überprüfung & Zusammenfassung
AtCoderBeginnerContest183 Überprüfung & Zusammenfassung
AtCoderBeginnerContest179 Review & Zusammenfassung
Django Girls Tutorial Zusammenfassung Erste Hälfte