Je vais vous expliquer comment résoudre les ** problèmes A, B, (C), D ** du ** AtCoder Beginners Contest 165 ** avec ** Python 3 ** aussi soigneusement que possible.
Je vise à expliquer une solution qui satisfait les trois points suivants, pas seulement une méthode qui peut être résolue.
5/17 C Le problème était très difficile et l'article était long, je l'ai donc séparé en un article séparé.
[Explication AtCoder] Contrôlez le problème C de ABC165 avec Python!
ABC165
Date: 02/05/2020 (sam) 21h10 ~ 02/05/2020 (sam) 22h50 (100 minutes) Un nombre de personnes qui soumettent des questions: 11626
| Performance | AC | But | temps | Classement | Ligne directrice |
|---|---|---|---|---|---|
| 400 | AB-- | 300 | 14 minutes | 73 25e | Thé performance |
| 600 | A--D | 500 | 98 minutes | 5940e | Taux brun à 8 fois |
| 800 | AB-D | 700 | 75 minutes | 4505e | Performance verte |
| 1200 | ABCD | 1000 | 93 minutes | 2194e | Performance de l'eau |
(Référence) Moi: Performance 1426 ABCD-- 41:05 1379e place D a été résolue en premier et renvoyée à C </ font>
Le problème C est le niveau de difficulté du niveau de problème difficile D. Si vous dites simplement "faites le tour et vérifiez toutes les réponses", vous verrez souvent le problème C.
Cependant, il est difficile de remarquer que ce problème peut être arrondi sur des séquences possibles. En plus de cela, vous ne pouvez pas le résoudre sans savoir faire toutes les séquences possibles.
D'autre part, le problème D était la difficulté de niveau de problème C habituelle. Avec ce type de problème défini, vous devez avoir le courage de vous calmer et de vérifier le problème D, puis de jeter le problème C et de résoudre le problème D.
ABC165A 『We Love Golf』
** Page des problèmes **: A --We Love Golf ** Difficulté **: ★★ ☆☆☆ ** Point **: Mathématiques, manipulation en
Si vous savez comment faire tous les multiples de k en dessous de b, vous pouvez le résoudre.
Un moyen facile de trouver est d'énumérer tous les multiples de k qui sont inférieurs ou égaux à b et de faire «OK» s'il y en a au moins un qui est supérieur ou égal à a. Vous pouvez maintenant commencer à écrire du code.
Cependant, il est plus facile de trouver le multiple maximum de k en dessous de b et s'il est supérieur ou égal à a, la méthode de `` OK '' 'écrite dans le PDF de commentaire officiel, donc si vous y pensez, écrivez-la ici. Est bon. Je ne pouvais pas y penser.
J'écrirai deux méthodes.
k = int(input())
a, b = list(map(int, input().split()))
x = 0
#J'ai l'impression de pouvoir l'écrire un peu plus joliment, mais pour le moment, une boucle infinie+en pause
while True:
x += k
if a <= x <= b:
print("OK")
break
if x > b:
print("NG")
break
k = int(input())
a, b = list(map(int, input().split()))
#Trouver "un multiple du maximum k inférieur ou égal à b"
largest = (b // k) * k
if a <= largest:
print("OK")
else:
print("NG")
ABC165B『1%』
** Page de problème **: B-1% ** Difficulté **: ★★ ☆☆☆ ** Point **: Manipulation en, lecture précise de l'énoncé du problème
Faites comme il est écrit, mais l'important est écrit entre parenthèses, ** "Tronquer l'argent après la virgule décimale chaque année" **.
Dans le cas de C ++ etc., vous devez faire attention au débordement, mais en Python, vous n'avez pas à vous en soucier. C'est Python, n'est-ce pas?
J'ai 100 yens au début et ça augmente de 1% par an avec les intérêts composés. Si vous suivez cette rue, vous pouvez le résoudre.
Si vous lisez attentivement l'énoncé du problème, vous constaterez qu'il est très important entre parenthèses (double intérêt, ** troncature après la virgule décimale **).
Par conséquent, tronquons après la virgule décimale.
Une fois que vous avez lu correctement l'énoncé du problème, tout ce que vous avez à faire est de l'écrire.
Même si vous manquez la troncature après la virgule décimale, si vous la vérifiez avec un échantillon, la réponse sera différente, vous remarquerez donc que quelque chose ne va pas. J'ai remarqué.
Plus précisément, la réponse pour l'échantillon 2 est 3760 et la sortie est 3703, et l'échantillon 3 est 1706 pour 1649.
L'échantillon 2 est la plus grande contrainte de $ 10 ^ {18} $, donc je suis convaincu que si cela réussit, vous n'aurez pas à vous soucier des erreurs.
x = int(input())
year = 0 #répondre
money = 100 #Valeur initiale 100 yens
#Tournez la boucle jusqu'à ce qu'elle dépasse x yen
while money < x:
money *= 1.01
money = int(money)
year += 1
print(year)
ABC165C『Many Requirements』
** Page de problème **: C --Beaucoup d'exigences ** Difficulté **: ★★★★★★★★★★ (niveau de problème Difficile D!) ** Type **: Idée round-robin, recherche prioritaire en profondeur (d'autres méthodes sont également disponibles), exercices antérieurs
Tout d'abord, il est difficile de lire l'énoncé du problème et d'en comprendre le sens. Même si vous en comprenez le sens, vous devez penser à faire toutes les séquences et à les vérifier. Et même si vous savez que vous allez faire un round robin, vous ne pouvez pas le résoudre sans savoir comment faire une séquence de nombres.
Pour être honnête, c'est la difficulté du difficile problème D.
Quoi? Vous pourriez penser, mais c'est important. ChezAtCoder, il est assez courant que la difficulté du problème soit inversée. Si le problème derrière est plus susceptible d'être résolu, il vaut mieux le faire en termes de points.
Cette fois, il y avait 2500 personnes AC en C et 5000 personnes AC en D, ce qui représentait plus du double de la différence. Il est rare qu'il y ait une telle différence de difficulté, mais il arrive souvent qu'il y ait une légère différence de difficulté.
Si vous vous concentrez sur le problème, vous n'aurez pas l'idée de résoudre le problème qui se cache derrière, il est donc important de se calmer et de s'éloigner du problème.
Une fois le concours terminé, je me sentais souvent frustré, "j'aurais pu résoudre ce problème!", Donc si je ne comprends pas un peu, j'essaye de vérifier le problème derrière.
Cette fois, j'ai pensé à C pendant 5 minutes et j'ai eu l'impression que c'était trop mauvais, alors j'ai résolu D en 10 minutes, puis je suis revenu à C et je l'ai résolu en 15 minutes.
Cela fait longtemps, donc je l'ai divisé en articles séparés. J'expliquerai de trois manières.
--Utilisez itertools.combinations_with_replacement (le plus simple) --Créer avec une file d'attente récursive (méthode très polyvalente)
[Commentaire d'AtCoder] Gagnez le problème ABC165 C "Many Requirements" avec Python!
Voici quelques problèmes similaires. Les deux derniers sont un peu plus difficiles de niveau de difficulté D, mais toujours plus faciles que celui-ci.
Niveau marron: ABC029 C --Attaque par force brute Niveau vert: ABC161 D --Lunlun Number Niveau vert: Panasonic Programming Contest 2020 D --String Equivalence
ABC165D『Floor Function』 ** Page de problème **: D --Fonction de sol ** Difficulté **: ★★★ ☆☆ ** Type **: Mathématiques
Si vous êtes bon en mathématiques, vous pouvez trouver intuitivement la réponse. Pour ceux d'entre nous qui ne sont pas bons en maths, nous pouvons le découvrir en essayant diverses choses.
Pour de tels problèmes, c'est une bonne idée de remplacer les nombres pour le moment.
Je suis heureux que $ floor (Ax / B) $ soit grand et que $ A \ times {floor (x / B)} $ soit petit.
Vous pouvez voir que ce dernier grandit lorsque $ x $ est exactement un multiple de $ B $. Ainsi, après avoir essayé diverses choses, vous pouvez voir que $ f (x + B) = f (x) $.
Par conséquent, $ x $ ne doit être considéré que dans la plage de 0 $ à (B-1) $. À ce moment, la soustraction $ A \ times {floor (x / B)} = 0 $, vous pouvez donc oublier l'existence.
Maintenant, $ floor (Ax / B) $ devient plus grand à mesure que $ x $ grossit, donc $ x $ devrait être $ B-1 $. Cependant, il existe une condition selon laquelle $ x $ est inférieur ou égal à $ N $, donc le plus petit de $ N $ et $ B-1 $ est la réponse.
Si vous le comprenez, ce n'est qu'une question d'écriture.
a, b, n = list(map(int, input().split()))
x = min(b - 1, n) # b-1 est bon, mais parfois la limite supérieure n ne le permet pas.
ans = int(a * x / b) #Calculer. La dernière section est 0, vous n'avez donc pas à l'écrire.
print(ans)
Recommended Posts