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 - Beginner Sur un certain site de compétition pro, il semble que la note des personnes avec un petit nombre de fois soit affichée plus haut que la note interne. La notation interne réelle est la question qui répond à certains.
Si le nombre de fois N est égal ou supérieur à 10, émettez tel quel. S'il est inférieur à 10, la valeur obtenue en ajoutant la valeur de correction 100 $ \ times (10-N) $ sera la note interne.
N, R = map(int, input().split())
if N < 10:
print(R + 100 * (10-N))
else:
print(R)
B - Digits C'est une question de savoir combien de chiffres seront quand la valeur numérique N est exprimée en notation K.
Pensez à l'emplacement du plus grand chiffre. Par exemple, si $ N = 9, K = 2 $, $ 1000 $, soit 2 $ ^ 3 $, sera le plus grand chiffre et $ r = 4 $ sera obtenu. En exprimant cela dans une formule mathématique, nous pouvons trouver un multiplicateur r qui satisfait ce qui suit.
J'ai simplement mis en œuvre cela.
N, K = map(int, input().split())
r = 1
while not(K**(r-1) <= N and N < K ** r):
r += 1
print(r)
Cela s'est passé sans aucun problème, mais quand j'ai regardé l'explication, la méthode était différente.
Le nombre de chiffres à calculer est $ D $, et la valeur de chaque chiffre est $ a_ {D-1}, \ cdots, a_1, a_0 $
Puis
Il est exprimé par la formule.
Si vous répétez l'opération consistant à diviser $ N $ par $ K $ et en prenant le quotient, le quotient sera de 0 $ lorsque $ D $ est divisé par $ K $.
Implémentons ceci.
N, K = map(int, input().split())
D = 0
while N:
N //= K
D += 1
print(D)
Il n'y avait aucun problème avec le temps de calcul.
C - Rally
La question est de répondre où se trouve le point (valeur entière) où l'erreur carrée est la plus petite pour ceux placés sur la droite numérique.
La méthode du carré minimum est associée à l'énoncé du problème, mais N et X ont tous deux une plage étroite de 1 à 100. J'ai décidé que je n'avais pas besoin de compétences mathématiques parce que $ O (N ^ 2) $ passait sans aucun problème, alors j'ai simplement cherché partout.
N = int(input())
X = list(map(int, input().split()))
minLoss = 1e6
for i in range(1, 101):
minLoss = min(minLoss, sum([(x - i)**2 for x in X]))
print(minLoss)
Je suis passé par là.
Je pense que ce serait un peu plus efficace si les plages gauche et droite étaient définies sur les valeurs minimale et maximale de X au lieu de 1 à 100.
D - Bouquet Combien de combinaisons peuvent être prises à partir de N fleurs différentes? Cependant, a et b ne peuvent pas être supprimés. C'est le problème.
TLE parce que j'ai essayé de trouver une combinaison avec $ _nC_r $ pour chaque nombre n de 1 à N. J'ai abandonné.
J'ai vu le commentaire. "Toutes les combinaisons pour tous les nombres" est beaucoup plus facile à calculer.
Il n'y a que deux options pour chaque fleur, «utiliser» et «ne pas utiliser». Donc, toutes les combinaisons valent 2 $ ^ N $. Cependant, la combinaison qui utilise 0 est exclue, donc c'est exactement $ 2 ^ N-1 $.
Il peut être obtenu en soustrayant les combinaisons à exclure de $ _nC_r $ pour a et b.
from scipy.misc import comb
m = 1000000007
n, a, b = map(int, input().split())
out = 2**n - comb(n, a) - comb(n, b)
print(out%m)
Ce n'était pas bon. Le problème est que 2 ** n, $ _nC_a et _nC_b $ sont trop nombreux.
Pour se débarrasser de ça Il faut réduire le calcul par une méthode mathématique utilisant la condition "reste divisé par 10 $ ^ 9 + 7 $".
Tout d'abord, considérons le multiplicateur de 2. En python, vous pouvez utiliser pow () au lieu de ** pour spécifier le nombre à diviser par le troisième argument, et le calcul du reste peut être effectué à grande vitesse.
print(pow(2, 4, 3)) # 1
Ensuite, envisagez d'accélérer le calcul des combinaisons.
Il y a le théorème de Fermat. Quand $ p $ est un nombre premier et $ a $ et $ p $ sont premiers l'un par rapport à l'autre
Est établi. Autrement dit, en divisant a par la puissance p-1 de p donne 1. Il semble. Je ne savais pas.
Je ne l'ai pas vraiment ressenti, alors je vais essayer.
p = 29
for a in range(3, 29, 5):
print("a: {}, p: {}, a^(p-1)%p: {}".format(a, p, pow(a, p-1, p)))
'''
a: 3, p: 29, a^(p-1)%p: 1
a: 8, p: 29, a^(p-1)%p: 1
a: 13, p: 29, a^(p-1)%p: 1
a: 18, p: 29, a^(p-1)%p: 1
a: 23, p: 29, a^(p-1)%p: 1
a: 28, p: 29, a^(p-1)%p: 1
'''
C'est vrai. Hmm. La preuve n'est pas mentionnée ici.
Renvoyez l'histoire. Sous cette condition, $ 10 ^ 9 + 7 $ et Y sont toujours premiers l'un par rapport à l'autre, donc l'équation suivante est vraie.
Divisez les deux côtés par Y
pow () pour calculer à grande vitesse comme auparavant. Les termes qui apparaissent dans le calcul de combinaison sont séparés en le dénominateur X et la molécule Y, et Y est soumis à ce traitement.
m = 1000000007
n, a, b = map(int, input().split())
def comb(n, r, m):
X, Y = 1, 1
for i in range(r):
X *= n-i
Y *= i+1
X %= m
Y %= m
return int(X * pow(Y, m-2, m))
out = pow(2, n, m) - 1 - comb(n, a, m) - comb(n, b, m)
print(out%m)
Je suis passé par là.
E - Roaming Combien de conditions de pièce une personne dans chacune des n pièces peut-elle déplacer k fois? C'est le problème.
Je ne pouvais pas imaginer comment le résoudre, alors j'ai abandonné.
J'ai vu le commentaire.
Tout d'abord, considérons une combinaison de chambres avec 0 personnes. Supposons que $ m $ de pièces soient vides. Ensuite, la combinaison de la sélection de m pièces parmi les n pièces
Il peut être trouvé par.
À partir de là, considérez la combinaison de pièces dans laquelle le résident d'origine de la chambre m a déménagé. Il y a plusieurs façons de penser, mais la façon la plus simple est de diviser les $ m $ habitants par des murs $ n-m-1 $. Si le résident est 〇 et le mur est |, cela peut être changé en un problème de réflexion sur la combinaison de modèles pour organiser les chaînes de caractères.
〇〇|〇|〇〇 Vous pouvez faire une combinaison comme celle-ci.
Cet arrangement est
Peut être calculé avec.
L'application de ce calcul à cette situation donne la formule suivante.
Par conséquent, la combinaison de $ _nC_m \ times _ {n-1} C _ {m} $ lorsque la salle $ m $ vaut 0 personne peut être obtenue. Vous pouvez additionner en changeant ce $ m $ de 0 à $ k $ (ou $ n-1 $).
De plus, le résultat du calcul de la combinaison peut être utilisé pour le prochain calcul de la combinaison.
C'est pourquoi c'est un exemple de mise en œuvre. J'écris en regardant le code de presque d'autres personnes.
n, k = map(int, input().split())
c1 = 1
c2 = 1
mod = 10**9+7
ans = 0
for i in range(min(n, k+1)):
ans += c1 * c2
c1 *= (n-i) * pow(i+1, mod-2, mod)
c1 %= mod
c2 *= (n-i-1) * pow(i+1, mod-2, mod)
c2 %= mod
print(ans%mod)
Ceci est la fin de cet article.
Recommended Posts