[PYTHON] AtCoder Beginner Contest 125 Revue des questions précédentes
Temps requis
Impressions
Questions passées résolues il y a quelques jours C'est typique d'une pierre, donc je n'ai pas pu le résoudre
Problème A
C'est facile compte tenu du nombre de fois que les biscuits sont fabriqués.
answerA.py
a,b,t=map(int,input().split())
print(b*(t//a))
Problème B
Accédez par ordre croissant à partir du plus petit index et comptez le plus grand par rapport à 0.
answerB.py
n=int(input())
v=input().split()
c=input().split()
co=0
for i in range(n):
co+=max(0,int(v[i])-int(c[i]))
print(co)
Problème C
Dans l'ère des quatre questions, le problème C est plus difficile que le problème D, n'est-ce pas? Eh bien, c'est le problème typique ... Comme vous pouvez sélectionner un entier et le réécrire en n'importe quel nombre de votre choix, vous pouvez voir que vous pouvez trouver le nombre maximal de promesses des N-1 entiers restants et considérer la valeur maximale. Cependant, s'il est implémenté purement, ce sera O ($ N ^ 2 \ times log (maxA) $), donc la contrainte sera dépassée avec une marge. Ici, pour une raison quelconque (je pense que j'étais fou), j'essayais d'expérimenter sans politique ou d'utiliser un algorithme approprié (comme la dichotomie). Tout en considérant la raison pour laquelle cela n'est pas possible, j'ai fait les importantes découvertes suivantes. (Les bases dans les bases ...)
Il existe un algorithme pour réduire la quantité de calcul!
En d'autres termes, je pense qu'il est facile de remarquer que la première chose à considérer dans ce problème est ** la cause de la grande quantité de calcul **, et ** il y a une partie du calcul pgcd qui est calculée plusieurs fois . Je vais. Par exemple, en comparant le cas de la sélection du kème entier et le cas de la sélection du k + 1ème entier, gcd est respectivement pgcd (gcd ($ A_1 $ ~ $ A_ {k-1}
answerC.py
from fractions import gcd
n=int(input())
a=[int(i) for i in input().split()]
a1=[a[0]]
for i in range(1,n-1):
a1.append(gcd(a1[-1],a[i]))
a2=[a[-1]]
for i in range(n-2,0,-1):
a2.append(gcd(a2[-1],a[i]))
m=[]
for i in range(n-2):
m.append(gcd(a1[i],a2[-i-2]))
m.append(a1[-1])
m.append(a2[-1])
print(max(m))
Problème D
Tout d'abord, je vais également expérimenter cela. Dans ce problème, nous voulons maximiser la somme, donc l'idée est d'augmenter le nombre de positifs dans la séquence entière autant que possible. Ici, si vous répétez l'expérience, vous constaterez que ** la plupart des éléments peuvent être corrigés **. De plus, comme la plupart des éléments sont positifs, l'opération définie dans ce problème pourrait ** sélectionner n'importe quel i, j et multiplier $ A_i $ et $ A_j $ par -1 **. J'ai pensé. Cette hypothèse est correcte: $ A_i $ et $ A_ {i + 1} $, $ A_ {i + 1} $ et $ A_ {i + 2} $,…, $ A_ {j-2} $ et $ A_ { Ceci peut être réalisé en exécutant les opérations définies dans ce problème dans l'ordre de j-1} $, $ A_ {j-1} $ et $ A_ {j} $. Si ce qui précède peut être affiché, seul un nombre pair d'éléments négatifs peut être rendu positif, et lorsqu'il y a un nombre pair d'éléments négatifs, tous peuvent être rendus positifs. Par conséquent, recherchez SUM (valeur absolue de tous les nombres) et créez un élément négatif. Lorsqu'il y a un nombre impair de SUM, vous pouvez trouver SUM en excluant ** le plus petit élément de valeur absolue **.
answerD.py
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
j=n
for i in range(n):
if a[i]>=0:
j=i
break
a=list(map(abs,a))
a.sort()
if j%2==0:
print(sum(a))
else:
print(sum(a)-2*a[0])
Recommended Posts