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