AtCoder ABC165 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 165 qui a eu lieu le 02/05/2020 (samedi), en commençant par le problème A et en tenant compte des considérations. Le premier semestre traite des problèmes jusqu'à ABCD. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Jumbo Takahashi a décidé de pratiquer le golf. L'objectif de Jumbo Takahashi est de rendre la distance de vol un multiple de $ K $, mais la plage de distance de vol de Jumbo Takahashi est de $ A $ ou plus et de $ B $ ou moins. Sortez "OK" si l'objectif peut être atteint, et "NG" sinon.
Quand j'ai lu le problème en un coup d'œil, c'était un problème de sauter plus d'un multiple de $ K $, et quand j'ai pensé à utiliser une inégalité, je me demandais si je pouvais rendre la distance de vol un multiple de $ K $. Pour le moment, la contrainte est également $ 1 \ leq A \ leq B \ leq 1000 $, donc je l'ai implémentée en utilisant l'instruction for. Voici le code que j'ai soumis.
abc165a.py
k = int(input())
a, b = map(int, input().split())
flag = 0
for i in range(a, b + 1):
if i % k == 0:
flag = 1
break
if flag == 1:
print("OK")
else:
print("NG")
Cependant, si la gamme de restrictions est très large, il ne sera pas temps de rechercher avec l'instruction for, alors reportez-vous à l'article de commentaire.
Comment trouver un multiple du maximum de $ K $ inférieur à $ B $ et voir s'il est supérieur à $ A $
J'ai également essayé d'implémenter comment le résoudre après avoir terminé. Voici le code réimplémenté.
abc165a.py
k = int(input())
a, b = map(int, input().split())
x = b // k * k
if a <= x:
print("OK")
else:
print("NG")
Pour être honnête, nous sommes en compétition pour la vitesse de résolution du problème D, donc pour le moment, j'essaie de résoudre le problème A par la méthode que j'ai trouvée pour la première fois pendant le concours.
Puisque l'opérateur python // peut générer un entier tronqué après le résultat fractionnaire de la division, x est un multiple du maximum k inférieur ou égal à b par le calcul de x = b // k * k. Il devient.
Énoncé du problème Takahashi a déposé 100 $ yens auprès d'AtCoder Bank. AtCoder Bank gagne 1 $% de dépôts chaque année (double intérêt, arrondi au nombre entier inférieur). En supposant que le montant du dépôt ne change pas en raison de facteurs autres que les intérêts, combien d'années faudra-t-il pour que le montant du dépôt de Takahashi-kun dépasse X $ Yen pour la première fois?
Voyant que la contrainte $ X $ atteignait 10 $ ^ {18} $, j'étais assez impatient au début et j'ai essayé de réfléchir à quelques idées, mais si j'y réfléchis bien, même $ 10 ^ {18} $ sera dans les 10000 $ ans. J'avais l'impression de pouvoir l'atteindre, de l'implémenter et de la confirmer en 3760. Je pensais que je pouvais me le permettre, et quand j'ai essayé de vérifier l'exemple avant de le soumettre, l'entrée dans l'exemple 2 était de 10 $ ^ {18} $. Si vous l'examinez d'abord, vous avez peut-être pu raccourcir un peu le temps pour le résoudre. Voici le code implémenté.
abc165b.py
x = int(input())
y = 100
for i in range(1, 10000):
y = int(y * 1.01)
if y >= x:
print(i)
break
Énoncé du problème Étant donné les entiers positifs $ N, M, Q $ et la paire d'entiers $ 4 $ $ (a_i, b_i, c_i, d_i) Q $. Considérons une séquence $ A $ qui remplit les conditions suivantes. ・ $ A $ est une chaîne d'entiers positifs de longueur $ N $. ・ $ 1 \ leq A_1 \ leq A_2 \ leq ⋯ \ leq A_N \ leq M $ Le score de cette séquence de nombres est déterminé comme suit. ・ Somme de $ d_i $ pour i qui satisfait $ A_ {b_i} −A_ {a_i} = c_i $ ($ 0 $ si un tel $ i $ n'existe pas) Trouvez le score maximum pour $ A $.
Au moment du concours, je n'avais pas les moyens de calculer $ O (?) $. Je voudrais résoudre un peu plus le problème et avoir une idée de si je peux ou non terminer la recherche. Quand je réfléchissais à une méthode pour le résoudre, je manquais de temps, donc je suis passé à la recherche complète avec préparation "TLE" et je l'ai implémentée. Pour le moment, c'est le code que j'ai implémenté et soumis.
abc165c.py
n, m, q = map(int, input().split())
dict_list = {}
key_list = []
for i in range(0, q):
a, b, c, d = map(int, input().split())
key = tuple([a, b, c])
key_list.append(key)
dict_list[key] = d
def func(i, k, a_list):
if k == 0:
temp_score = 0
for key in key_list:
if key[2] == a_list[key[1]-1] - a_list[key[0]-1]:
temp_score += dict_list[key]
return temp_score
k = k - 1
max_score = 0
for j in range(i, m + 1):
max_score = max(func(j, k, a_list + [j]), max_score)
return max_score
score = 0
for i in range(1, m + 1):
score = max(func(i, n - 1, [i]), score)
print(score)
Pour la séquence de nombres $ A $ qui est dans l'ordre croissant, tous les modèles sont créés à l'aide d'une fonction récursive et le score maximum est renvoyé. Cette fois, plutôt que de l'implémenter, j'aimerais écrire une petite partie où il y a $ {} _ {N + M − 1} C _N $ comme une suite de nombres qui satisfait les conditions. Ce type de problème est un problème que les mathématiques du secondaire sont toujours répertoriées dans la collection de problèmes et que le lycée 1 commence à avoir des difficultés. Cela ressemble à un problème d'organisation des nombres dans une rangée, donc je veux utiliser $ P $, mais c'est un problème que je peux utiliser $ C $ pour trouver le nombre de rues (je pense qu'il apparaissait souvent dans les examens simulés).
L'idée est un peu différente de l'explication officielle, mais mon interprétation est de penser à des boules $ N $ et des partitions $ M-1 $, puis de les organiser dans une rangée. Cela peut être fait en additionnant le nombre de boules et de diviseurs et en les arrangeant selon $ (N + M -1)! $, Mais en raison de l'existence d'une duplication, $ N! $ Et $ (M-1)! $ Doit être divisé par (problèmes de séquence courants avec des caractères en double). Donc,
\frac{(N + M - 1)!}{N!(M - 1)!} = {}_{N+M−1} C _N
Par conséquent, vous pouvez utiliser $ C $ pour trouver le nombre de rues. Pourquoi pouvons-nous trouver le nombre de balles $ N $ et de diviseurs $ M-1 $ d'affilée et le nombre de nombres $ A $ dans l'ordre croissant? Plus précisément, $ N = 6, M = Prenons le cas de 8 $ comme exemple.
Ce n'est pas grave si vous pensez qu'il affiche $ A_1, A_2, ..., A_N $ dans l'ordre à partir du cercle de gauche, donc l'exemple 1 est
Considérant la même chose que dans l'exemple 1, les salles 1, 3, 7, 8 sont vides et il y en a deux dans les salles 4, 6, donc la ligne numérique $ A $ est
Quand je suis professeur de cram school, on me pose souvent cette question depuis le lycée 1, donc c'est assez facile de trébucher.
Énoncé du problème Compte tenu des entiers $ A, B, N $. Trouvez la valeur maximale de $ floor (Ax / B) −A × floor (x / B) $ pour un entier non négatif $ x $ inférieur ou égal à $ N $. Cependant, $ floor (t) $ représente le plus grand entier inférieur ou égal au nombre réel $ t $.
Pour le moment, j'ai soumis un programme de recherche complet et était "TLE", pensant que je ne pouvais pas tous les énumérer (je ne pense pas qu'il devrait y avoir une recherche complète qui soit facile à implémenter en raison du problème D). Après cela, j'ai regardé la formule et divisé les cas en fonction de ce que j'ai trouvé, et je l'ai résolu sans aucun problème. L'ordre des instructions if dans le code est écrit dans l'ordre dans lequel elles ont été divisées pendant le concours. J'ai rapidement réalisé que $ floor (Ax / B) $ était une augmentation monotone au sens large, j'ai donc d'abord divisé les cas par $ N <B $. C'est $ floor (x / B) = 0 $, ce qui est facile à penser, donc je pense que c'est facile à trouver. Comme il s'agit d'une augmentation monotone au sens large, on peut voir que $ X = N $ est le maximum. Ensuite, il était clair en remplaçant que $ N = B $ devient $ floor (Ax / B) −A × floor (x / B) = 0 $, donc $ X = N-1 $ Vous pouvez voir que c'est le maximum. Après cela, en substituant spécifiquement $ X = B-1 $ etc., en classant les observations selon la taille de $ A $ et $ B $, écrivez le code suivant et soumettez-le, "AC J'ai pu émettre.
abc165d.py
a, b, n = map(int, input().split())
max_score = 0
if n < b:
max_score = int(a * n / b) - a * (n // b)
elif n == b:
max_score = int(a * (n-1) / b) - a * ((n-1) // b)
elif a <= b:
max_score = a - 1
elif a >= b:
max_score = int(a * (b-1) / b) - a * ((b-1) // b)
print(max_score)
Quand j'ai regardé l'explication, je suis arrivée à une conclusion très simple et j'ai senti que je manquais de capacités. Quand j'ai implémenté la conclusion de l'explication, je pouvais l'écrire avec le code suivant (extrêmement court).
abc165d.py
a, b, n = map(int, input().split())
x = min(b - 1, n)
print(int(a * x / b) - a * (x // b))
C'est la fin du premier semestre.
Dans ce concours, après avoir résolu le problème ABD, je ne me suis pas rendu compte que le problème C était un problème de recherche complet, et j'ai passé trop de temps sur la façon de le résoudre, donc je n'ai pas eu le temps de l'utiliser pour les problèmes E et F, alors j'ai commencé avec le problème D. Je veux pouvoir le résoudre en 40 minutes environ. Merci d'avoir lu jusqu'à la fin de la première moitié pour le moment.
La seconde moitié expliquera le problème EF. Prévu pour continuer dans la seconde moitié.
Recommended Posts