Examen du concours AtCoder Beginner Contest 163, jusqu'à la question E (Python)
Ceci est un article de synthèse pour les débutants des professionnels de la compétition.
La solution que j'écris ici est écrite en regardant les commentaires et les soumissions d'autres personnes. Ce n'est peut-être pas ce que vous avez réellement soumis.
A - Circle Pond C'est un problème de sortir la circonférence du rayon R.
Circonférence c par rapport au rayon r
Il peut être trouvé par.
import math
R = int(input())
print(2 * math.pi * R)
La tolérance de l'erreur étant grande, il semble qu'il ne soit pas nécessaire de lire le rapport de circonférence de cette manière.
$ \ boldsymbol {A} $ jours Si vous faites les devoirs nécessaires pour les vacances d'été, la question est de savoir combien de jours il vous reste pour les vacances d'été.
(Nombre de jours pendant les vacances d'été) -Si (tableau total) est négatif-1, afficher comme il en est autrement. Si vous utilisez max (), vous n'avez pas besoin d'utiliser l'instruction if.
N, M = map(int, input().split())
A = list(map(int, input().split()))
print(max(N - sum(A), -1))
Vous recevrez l'information "Employé avec le numéro d'employé $ i $ qui a le numéro d'employé $ A_i $ comme son patron". Il s'agit du nombre de subordonnés de chaque membre du personnel.
Il a fallu le plus de temps pour comprendre l'énoncé du problème. Bref, on vous interroge sur la distribution des nombres.
J'ai compté la distribution des nombres en utilisant collections.Counter.
import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
print(count[n+1])
Il s'agit de répondre au nombre de sommes possibles parmi toutes les combinaisons qui prennent $ K $ ou plus sur des nombres $ N + 1 $. Cependant, comme chaque nombre est sous la forme de 10 $ ^ {100} + i $, la somme de $ M $ et la somme de $ M + 1 $ ne correspondront jamais.
Je n'en ai aucune idée. N'est-il pas possible de formuler le nombre de sommes? J'ai essayé de calculer quel genre de distribution serait la "combinaison de sommes quand $ M $ est pris des nombres de 1 à 9". Il montre la distribution de la somme lorsque la sortie sur la ligne $ m $ prend $ m $.
En fait, j'ai abandonné ici. Cependant, si vous regardez cela maintenant, vous obtiendrez un indice important.
En regardant cette sortie, on suppose qu'il n'y a pas de nombre manquant entre les valeurs minimale et maximale de la somme des combinaisons. Ensuite, si vous calculez respectivement la "valeur minimale de la somme" et la "valeur maximale de la somme", vous pouvez trouver le nombre de sommes combinées lorsque $ M $ est pris.
La valeur minimale lorsque $ M $ est pris est "total des nombres jusqu'à $ M $", et la valeur maximale est "total des nombres de $ N-M + 1 $". Le reste est le nombre de combinaisons qui peuvent avoir une différence de +1.
N, K = map(int, input().split())
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
maxSum = (n*(N + N-n+1))//2
minSum = (n*(n-1))//2
count += maxSum - minSum + 1
count %= mod
print(count)
Je suis passé par là. Je le savais sans regarder le commentaire, alors j'ai voulu le résoudre pendant le concours. E - Active Infants
Étant donné le coefficient $ A_i $ pour chaque enfant qui existe à la position $ i $, le problème est de trouver la valeur maximale de la distance parcourue par l'enfant autour de x le coefficient.
Je ne comprends pas du tout. J'ai abandonné (TLE) en soumettant une réponse à la ronde en détresse.
Gars TLE.py
import itertools
N = int(input())
A = list(map(int, input().split()))
ureshisa = [
[A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
maxV = max(maxV, sum([ureshisa[P[i]][i] for i in range(N)]))
print(maxV)
Je n'ai pas compris même si j'ai regardé l'explication, je vais donc me référer à d'autres réponses. Le code suivant est tiré de cette réponse tel quel.
Citation.py
# E - Active Infants
n = int(input())
a = list(map(int, input().split()))
assert len(a) == n
#Liste des indices
p = list(range(n))
p.sort(key=lambda i: a[i])
# dp[j] =Bonheur maximum quand je suis placé dans la section de la position j à la largeur i du plus petit
dp = [0] * (n + 1)
for i in range(n):
for j in range(n - i):
dp[j] = max(dp[j] + a[p[i]] * abs(p[i] - (j + i)),
dp[j + 1] + a[p[i]] * abs(p[i] - j))
print(dp[0])
Je ne sais pas, alors je vais suivre le processus
Suivons dans l'ordre ce qu'il faut faire lorsque le tableau «[1, 3, 4, 2]» est donné.
Tout d'abord, considérons le placement d'un bébé (ci-après appelé $ a_0 $) avec $ i = 0 $, qui a la valeur minimale de $ A_i $.
La joie de placer $ a_0 $ à chacune des positions 0, 1, 2 et 3 est calculée pour être 0, 1, 2, 3.
Enregistrez cette valeur sous le tableau dp. Le tableau dp lorsqu'un enfant $ a_0 $ est placé à partir du bas est le suivant
Ensuite, placez le bébé $ a_3 $ avec $ i = 3 $, où $ A_i $ est la deuxième plus petite valeur. Cependant, ne considérons que l'état "placer un derrière $ a_0 $" et "pousser $ a_0 $ un derrière".
Premièrement, lorsque $ a_0 $ est placé à $ i = 0 $, "Laissez $ a_0 $ et placez $ a_3 $ à $ i = 1 $" "Définissez $ a_0 $ sur $ i = 1 $" Poussez-le et placez $ a_3 $ à $ i = 0 $ ". La joie était calculée à 4 et 7, respectivement. Ne laissez que la valeur la plus grande et définissez dp [0] = 7.
Si cela est calculé de la même manière, lorsque le placement de $ a_0 $ est $ i = 1, 2 $, 6 et 5 sont respectivement le maximum. (La valeur de «dp [3]» a été absorbée ici)
Donc, les deux nourrissons avec le coefficient le plus bas ($ a_) Lors de l'organisation de {03} $) côte à côte
Est la valeur maximale correspondant à chaque position.
Ensuite, considérons le placement de l'enfant $ a_1 $ avec le troisième coefficient à partir du bas, $ i = 1 $.
Calculez respectivement "placez deux tout-petits dans une rangée derrière $ a_ {03} $" et "placez deux tout-petits dans une rangée derrière $ a_ {03} $".
Il a été calculé de la même manière que précédemment, et lorsque les trois nourrissons (appelés $ a_ {031} $) du bas ont été placés côte à côte, il a été obtenu comme suit.
Enfin, refaites la même chose pour l'enfant $ a_2 $ avec le plus grand coefficient $ A_i $.
Lorsque $ a_ {031} $ est placé à $ i = 0 $ et $ a_2 $ est placé à $ i = 3 $, 14 $ est placé et $ a_ {031} $ est placé à $ i = 1 $. 20 $ quand a_2 $ est placé à $ i = 0 $. Prenez le plus grand.
Maintenant vous avez la réponse.
Je ne rattrape pas ma compréhension ... Pour aller avec cette idée, devons-nous avoir l'idée que «le nourrisson avec le coefficient M du bas est toujours adjacent à la« rangée de nourrissons du 1er au M-1er »?» Je ne me sens pas comme ça intuitivement, mais je ne suis pas sûr de pouvoir le prouver.
Selon la façon de penser du commentateur, le mur gauche ou droit est rempli dans l'ordre à partir de l'enfant avec le coefficient le plus élevé. Bref, il semble que vous faites la même chose dans l'ordre inverse.
C'est tout pour cet article.
référence
https://atcoder.jp/contests/abc163/submissions/12150591 La question E a cité ceci.
Recommended Posts