[PYTHON] AtCoderBeginnerContest173 Review & Summary (second semestre)

AtCoder ABC173 Ceci est un résumé des problèmes de AtCoder Beginner Contest 173, qui s'est tenu le 2020-07-05 (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

Problème de conversation en cercle

Énoncé du problème Vous avez terminé le tutoriel du jeu en ligne "AT Chat" et avez décidé de visiter un certain endroit avec des joueurs $ N $ qui y étaient. Cette personne $ N $ est numérotée de $ 1 $ à $ N $, et la gentillesse de la personne $ i (1 \ leq i \ leq N) $ est $ A_i $. Lors d'une visite, les personnes $ N $ arrivent dans n'importe quel ordre, 1 $ chacune. Pour éviter de se perdre, nous avons décidé d'une règle selon laquelle les personnes déjà arrivées s'aligneront en cercle, et les nouveaux arrivants s'interrompront et se joindront à la position de leur choix. Chaque personne autre que la première personne arrivée se sentira aussi à l'aise que la moindre de la gentillesse de «la personne la plus proche dans le sens des aiguilles d'une montre» et «la personne la plus proche dans le sens inverse des aiguilles d'une montre» en arrivant de la position interrompue. Je le sens. Le confort de la première personne à arriver est de 0 $. Quel est le confort total maximum des personnes $ N $ lorsque l'ordre d'arrivée et la position d'interruption sont correctement déterminés?

Pour être honnête, je pensais que j'aurais dû y réfléchir correctement. D'une manière ou d'une autre, j'ai eu du mal à voir le problème, et je l'ai ignoré pour résoudre le problème E pour faire une différence.

abc173d.py


n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
ans = 0
for i in range(0, n - 1):
    ans += a_list[(i + 1) // 2]
print(ans)

Problème E Multiplication 4

Énoncé du problème $ N $ entiers $ A_1,…, A_N $ sont donnés. Lorsque vous ne sélectionnez que des éléments de $ K $ à partir de cela, trouvez le produit maximum possible des éléments sélectionnés. Ensuite, divisez la réponse par $ (10 ^ 9 + 7) $ et affichez le reste sous forme d'entier entre $ 0 $ et $ 10 ^ 9 + 6 $.

Je pensais au problème en le divisant en nombres positifs, nombres négatifs et nombres 0, mais pour une raison quelconque, j'ai désespérément écrit les cas où le résultat de $ K = N $ était négatif et quand il était positif. , Il était temps. Si vous y réfléchissez bien, lorsque vous les utilisez tous, vous pouvez le calculer avidement (réflexion). Cependant, en regardant le code soumis pour étude,

4 3
-1 -2 3 4

Je me suis demandé ce qui se passait avec "AC" qui ne pouvait pas correspondre à l'exemple d'entrée comme. Les personnes qui réfléchissent à ce qu'il faut faire dans de tels cas finissent par manquer de temps, ne pensent pas trop à l'entrée et, heureusement, passent par l'entrée limitée dans le test. S'il y a des gens qui ont marqué, j'aimerais que vous ajustiez le taux plus tard, mais il ne sert à rien de trop demander pour le concours gratuit (transpiration). Actuellement, after_contest_01.txt a été ajouté à la vérification, et ce code sera "WA".

abc173e.py


n, k = map(int, input().split())
a_list = list(map(int, input().split()))
mod = 10**9+7
a_list.sort()
ans = 1
if k % 2 == 1 and a_list[-1] < 0:
    for i in range(k):
        ans *= a_list[n - 1 - i]
        ans %= mod
else:
    l = 0
    r = -1
    mlt1 = a_list[0] * a_list[1]
    mlt2 = a_list[-2] * a_list[-1]
    count = 0
    while True:
        if count == k:
            break
        elif count == k - 1:
            ans *= a_list[r] % mod
            ans %= mod
            break
        if mlt1 >= mlt2:
            ans *= mlt1 % mod
            l += 2
            count += 2
            if l <= n - 2:
                mlt1 = a_list[l + 1] * a_list[l]
        else:
            ans *= a_list[r] % mod
            r -= 1
            count += 1
            if r >= - n + 1:
                mlt2 = a_list[r - 1] * a_list[r]
        ans %= mod
print(ans)

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

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second semestre)
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)
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)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (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é