Examen du concours AtCoder Beginner Contest 165, 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.
Il s'agit de savoir si K est inclus dans la plage de A ou plus et B ou moins.
A partir de la contrainte de $ 1 \ leq A \ leq B \ leq 1000 $, $ 1 \ leq K \ leq 1000 $, il n'y a pas de problème si vous recherchez simplement une valeur qui satisfait la condition dans la plage de $ A $ à $ B $. ..
N = int(input())
A, B = map(int, input().split())
for i in range(A, B+1):
if i % N == 0:
print('OK')
break
else:
print('NG')
Lorsque les 100 yens déposés ont un taux d'intérêt annuel de 1%, il s'agit de savoir combien d'années plus tard il dépassera le montant donné de X yens.
Les montants sous la virgule décimale seront tronqués. A répondu le nombre de fois où «while» a été tourné jusqu'à ce que le montant spécifié soit dépassé
X = int(input())
n = 100
count = 0
while n < X:
count += 1
n = int(n * 1.01)
print(count)
Pour les entrées $ a, b, c, d $, obtenez $ d $ points quand $ A_b --A_a = c $. Lorsque vous êtes libre de créer une séquence de nombres $ \ boldsymbol {A} $, la question est de savoir quel sera le score total maximum.
Cela ressemble à un problème déroutant ... mais la longueur de la séquence $ N $, le maximum $ M $ est $ 1 \ leq N \ leq 10, 1 \ leq M \ leq 10 $, étant donné $ a, b Le nombre de, c, d $ $ Q $ est également spécifié comme $ 1 \ leq Q \ leq 50 $. Je pensais que ce serait une poussée détournée.
J'ai utilisé ʻitertools.combinations_with_replacement () `pour le round-robin. Notez que la colonne numérique $ A $ a une valeur triée fixe, mais des valeurs en double sont possibles.
import itertools
N, M, Q = map(int, input().split())
abcd = [tuple(map(int, input().split())) for _ in range(Q)]
Max = 0
for C in itertools.combinations_with_replacement(range(1, M + 1), N):
score = sum([d for a, b, c, d in abcd if C[b-1] - C[a-1] == c])
Max = max(Max, score)
print(Max)
Postscript
Est-ce vraiment un nombre qui peut être poussé? $ O (M ^ N Q) $, non? J'étais inquiet et j'ai essayé de calculer.
import itertools
print(len(list(itertools.combinations_with_replacement(range(1, 11), 10))))
# 92378
Il semble que vous puissiez y aller. En regardant le commentaire, cette recherche complète a été difficile en soi. Vive Python. Vive la bibliothèque.
Est le problème de trouver $ x $ qui est la valeur maximale.
Mis à part la preuve mathématique, je me suis demandé si je devais trouver la valeur maximale de $ x $ telle que $ floor (x / B) = 0 $. La condition est remplie par le plus grand $ B-1 $ en dessous de $ N $, c'est-à-dire le plus petit de $ B-1 $ ou $ N $.
C'est pourquoi j'ai écrit ce qui suit.
A, B, N = map(int, input().split())
x = min(B-1, N)
print(A*x // B - A * (x//B))
Explication mathématique
Je n'ai pas compris l'explication mathématique, alors je vais lire l'explication.
Et mettez-le. Lorsque la valeur de $ x $ est augmentée de $ B $ dans cette formule, le premier terme du côté droit est toujours augmenté de $ A $. Le deuxième terme est toujours réduit de $ A $. Cela s'annule et le total ne change pas. En d'autres termes, la formule suivante est valable.
Vous n'avez donc pas à penser à la plage de $ B \ leq x $. Trouvez la valeur maximale dans la plage de $ 0 \ leq x <B $, $ 0 \ leq x \ leq N $.
Dans cette plage, la valeur du deuxième terme, qui est initialement négative, est toujours 0, donc la valeur du premier terme, qui est une augmentation monotone, doit être maximisée dans la plage. Autrement dit, maximisez $ x $ dans la plage.
Je n'utilise pas le deuxième terme, vous pouvez donc l'écrire comme suit.
A, B, N = map(int, input().split())
print(A * min(B-1, N) // B)
C'est un problème de réfléchir à la façon de prendre une combinaison dans laquelle les adversaires ne se chevauchent pas lorsque les participants à $ N $ jouent à 1 contre 1 pierre-papier-ciseaux en même temps pour des jeux $ M $ et des fois $ N $.
L'énoncé du problème est extrêmement compliqué. Que demandez-vous?
Disons que $ N = 9 $ personnes ont participé à ce tournoi. Il y aura 9 séries de matchs. À partir de là, définissons $ M = 3 $ et faisons trois paires.
Choisissez une paire de 1 ou 2 comme vous le souhaitez.
Même si vous tournez 9 fois dans cet état, il n'y aura pas de duplication des adversaires.
Ensuite, prenons 3, 5 paires.
Cela n'entraînera pas de duplication.
Ensuite, prenons une paire de 6 et 7.
Cela entraînera une duplication. Une paire de 1 et 2 équipes et une paire de 6 et 7 équipes prennent la même chose sur le chemin.
Comment régler ceci? Il a été décalé de un ou deux, alors décalons-le de trois cette fois.
Cette fois, il n'y a pas de duplication. Le problème est de faire une telle paire.
En d'autres termes, ce problème peut être reformulé comme suit.
"Sortie $ M $ paires de ($ A_i, B_i $) avec $ B_i --A_i = 1, 2, 3, ..., M $, sans duplication des valeurs."
Vous n'avez pas fait une recherche décente pour résoudre ce problème. (TLE est sorti.) La forme est décidée et placée depuis le début.
C'est pourquoi je l'ai implémenté comme suit.
N, M = map(int, input().split())
halfPos = -(-N//2)
qPos = halfPos // 2
q3Pos = qPos + halfPos
for m in range(1, M+1):
if m % 2:
print(qPos-m//2, qPos+m//2+1)
else:
print(q3Pos-m//2, q3Pos+m//2)
Cet article se termine ici. C'est la première fois que je le résolve en production avec ABCDE.
Recommended Posts