AtCoderBeginnerContest174 Review & Summary (second semestre)

AtCoder ABC174 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 174, qui s'est tenu le 2020-08-02 (dimanche), dans l'ordre du problème A, en tenant compte de la considération. La seconde partie traite du problème de l'ED. Cliquez ici pour la première moitié Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF

D problème Alter Altar

Énoncé du problème L'autel est enchâssé de pierres $ N $ alignées de gauche à droite. La couleur de la pierre $ i $ th $ (1 \ leqq i \ leqq N) $ à partir de la gauche est donnée par la lettre $ c_i $, qui est rouge quand $ c_i $ est "R" et blanche quand elle est "W". Vous pouvez effectuer les deux opérations suivantes autant de fois que vous le souhaitez dans n'importe quel ordre. ・ Sélectionnez des pierres de 2 $ (pas nécessairement les unes à côté des autres) et remplacez-les. ・ Sélectionnez des pierres à 1 $ et changez la couleur des pierres (rouge pour blanc, blanc pour rouge). Selon la diseuse de bonne aventure, la pierre blanche placée à gauche de la pierre rouge provoque le désastre. Combien d'opérations sont nécessaires pour atteindre l'état sans ces pierres blanches?

Quand j'ai lu le problème, j'ai pensé que je pourrais le résoudre simplement en "sélectionnant des pierres de $ 2 $ (pas nécessairement les unes à côté des autres) et en les remplaçant." En n'utilisant pas "・ Sélectionnez des pierres $ 1 $ et changez la couleur des pierres (rouge pour blanc, blanc pour rouge)", l'état sans la réponse finale est fixé. Par exemple, à $ N = 9 $ 'WRWWWRRWR' L'entrée est 'RRRRWWWWW' La réponse peut être donnée en considérant le fonctionnement minimum de sorte que. C'est le nombre de pierres rouges incluses dans l'entrée $ N_r $, et le nombre de pierres blanches de $ 1 $ à $ N_r $ th dans l'entrée est le nombre d'opérations requis. (Dans le cas de l'exemple, $ 3 $ est la réponse car c'est le nombre de pierres blanches dans le $ 1 $ à $ 4 $ th'WRWW'de'WRWWWRRWR '.)

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]))

Journaux des problèmes E

Énoncé du problème Il existe des logs $ N $, chacun étant $ A_1, A_2, ⋯, A_N $. Vous pouvez couper ces journaux jusqu'à un total de $ K $ fois. Si vous coupez un journal de longueur $ L $ d'une extrémité à la position $ t (0 <t <L) $, il sera divisé en journaux de longueur $ t, L − t $. Après avoir coupé le journal jusqu'à un total de $ K $, trouvez la longueur minimale du journal le plus long et sortez la valeur arrondie au nombre entier le plus proche.

Je n'ai pas remarqué la dichotomie et recherchais avidement à partir de $ x = 1 $, donc je n'ai pas pu le résoudre pendant le concours.

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

Merci d'avoir lu la seconde moitié jusqu'à la fin.

Recommended Posts

AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié