AtCoder Beginner Contest 125 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-14 16.40.05.png

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} )), gcd ( A_). {k + 1} $ ~ $ A_ {N} )) et pgcd (pgcd ( A_1 $ ~ $ A_ {k} ), pgcd ( A_ {k + 2} $ ~ $ A_ {N} $) ), Vous pouvez donc voir que $ A_1 $ ~ $ A_ {k-1} $ et $ A_ {k + 2} $ ~ $ A_ {N} $ sont communs. De la même manière, en considérant la sélection de $ A_1 $ ~ $ A_ {N} $ respectivement, en considérant le pgcd cumulatif de gauche et de droite, il n'est pas nécessaire de calculer plusieurs fois, et O ($ N \ times log (maxA)) Vous pouvez déposer la commande à $) et calculer. De ce qui précède, il était possible d'écrire un programme facilement en séparant la phase mémo et la phase de calcul et en les implémentant docilement. ( J'ai l'habitude de penser étrangement compliqué, donc je veux y remédier. **)

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

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes