[Explication AtCoder] Contrôle ABC184 Problèmes A, B, C avec Python!
** Les ** problèmes A, B, C ** de AtCoder Beginner Contest 184 ** seront expliqués aussi soigneusement que possible avec ** Python3 **.
Je vise à expliquer une solution qui satisfait les trois points suivants, pas seulement une méthode qui peut être résolue.
--Simple: vous n'avez à penser à rien de plus --Facile à mettre en œuvre: je suis content qu'il y ait moins d'erreurs et de bugs ――Cela ne prend pas longtemps: les performances augmentent et il vous reste plus de temps pour les problèmes ultérieurs.
Si vous avez des questions ou des suggestions, veuillez laisser un commentaire ou Twitter. Twitter: u2dayo
table des matières
[Résumé ABC184](# abc184-Résumé) [Un problème "déterminant"](# un problème déterminant) [B problème "Quizzes"](#b problèmes quiz) [Problème C "Super Ryuma"](#c problème super-ryuma)
Résumé ABC184
Nombre total de soumissions: 7822
performance
| Performance | AC | But | temps | Classement(Dans les limites) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 12 minutes | 5984(5769)Rang |
| 400 | AB---- | 300 | 6 minutes | 4983(4768)Rang |
| 600 | AB---- | 300 | 4 minutes | 4132(3917)Rang |
| 800 | ABC--- | 600 | 88 minutes | 3271(3056)Rang |
| 1000 | ABC--- | 600 | 37 minutes | 2454(2240)Rang |
| 1200 | ABCD-- | 1000 | 105 minutes | 1767(1556)Rang |
| 1400 | ABC--F | 1200 | 97 minutes | 1229(1026)Rang |
| 1600 | ABCD-F | 1600 | 66 minutes | 832(636)Rang |
| 1800 | ABCDEF | 2100 | 97 minutes | 551(367)Rang |
| 2000 | ABCDEF | 2100 | 73 minutes | 352(195)Rang |
| 2200 | ABCDEF | 2100 | 57 minutes | 228(96)Rang |
| 2400 | ABCDEF | 2100 | 45 minutes | 130(44)Rang |
Taux de réponse correct par couleur
| Couleur | Nombre de personnes | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| Cendre | 3253 | 98.7 % | 92.0 % | 15.3 % | 2.3 % | 1.0 % | 0.7 % |
| thé | 1499 | 99.3 % | 99.1 % | 45.8 % | 9.5 % | 4.9 % | 4.5 % |
| vert | 1184 | 99.5 % | 99.5 % | 63.4 % | 29.6 % | 18.4 % | 14.1 % |
| eau | 729 | 99.9 % | 99.9 % | 78.5 % | 58.7 % | 49.1 % | 54.6 % |
| Bleu | 360 | 99.7 % | 99.7 % | 94.4 % | 88.6 % | 86.1 % | 88.1 % |
| Jaune | 175 | 96.0 % | 96.0 % | 93.1 % | 94.3 % | 91.4 % | 96.6 % |
| Orange | 31 | 96.8 % | 96.8 % | 96.8 % | 96.8 % | 96.8 % | 96.8 % |
| rouge | 11 | 90.9 % | 90.9 % | 90.9 % | 90.9 % | 100.0 % | 100.0 % |
- Taux d'affichage, les cendres n'incluent pas les nouveaux participants </ font>
Bref commentaire
- Un problème (7738 personnes AC) "Déterminant"
- Même si vous ne connaissez pas l'expression de la matrice, vous pouvez faire ce qu'on vous dit.
- Problème B (7439 personnes AC) "Quizzes"
- Ce n'est pas grave si vous le simulez docilement.
- Problème C (3137 personnes AC) "Super Ryuma"
- Je ne suis pas sûr, c'est donc une bonne idée d'essayer combien de coups vous pouvez atteindre chaque case dans une petite grille pour trouver les règles. L'écriture sur papier est gênante et sujette aux erreurs, c'est donc une bonne idée de créer un programme qui génère des réponses simples.
- Problème D (1561 personnes AC) "incrément de pièces" [non expliqué dans cet article]
- C'est une probabilité DP.
- Problème E (1223 AC) "Third Avenue" [non expliqué dans cet article]
- La recherche de priorité de largeur est effectuée.
- Problème F (1209 personnes AC) "Concours de programmation" [non expliqué dans cet article]
- Je fais juste une "énumération à moitié complète" sans aucun effort particulier.
- $ x $ Les coordonnées sont $ + k $, $ y $ Les coordonnées sont $ + k $ (en haut à droite)
- $ x $ Les coordonnées sont $ + k $, $ y $ Les coordonnées sont $ -k $ (en bas à droite)
- $ x $ Les coordonnées sont $ -k $, $ y $ Les coordonnées sont $ + k $ (en haut à gauche)
- $ x $ Les coordonnées sont $ -k $, $ y $ Les coordonnées sont $ -k $ (en bas à gauche)
Résultats de moi (Unidayo) (référence)
Un problème "déterminant"
** Page de problème **: A --Determinant ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 98,7% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 99,3% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 99,5%
Même si vous ne connaissez pas la formule matricielle, vous pouvez le faire exactement comme il est écrit.
code
A, B = map(int, input().split()) C, D = map(int, input().split()) print(A * D - B * C)Problème B "Quiz"
** Page de problème **: B --Quizzes ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 92,0% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 99,1% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 99,5%
la mise en oeuvre
Ce n'est pas grave si vous utilisez docilement la boucle for et l'implémentez conformément à l'énoncé du problème. Si vous accordez la priorité à la clarté sans essayer de l'écrire de manière cool, vous pouvez réduire les erreurs.
code
N, X = map(int, input().split()) S = input() score = X for char in S: if char == "o": score += 1 else: if score > 0: score -= 1 print(score)Problème C "Super Ryuma"
** Page de problème **: C --Super Ryuma ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 15,3% ** <font color = # 804000> Brun </ font> Taux de réponse correcte du codeur **: 45,8% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 63,4%
Signification du problème
$ 1 $ Il y a une pièce "Super Ryoma" qui vous permet d'effectuer l'un ou l'autre des mouvements suivants avec vos mains.
** - Déplacez votre masse préférée en diagonale (comme le coin d'un shogi. Nous l'appellerons ** mouvement diagonal **) ** ** - Tournez 3 fois vers le haut, le bas, la gauche et la droite (la "distance de Manhattan" peut se déplacer vers un carré à moins de 3 $. Nous l'appellerons ** mouvement Super Ryoma **) **
Puisque les coordonnées de départ et de but sont données, veuillez indiquer le nombre de coups que vous pouvez effectuer dans "Super Ryoma".
Considération
Il semble que cela n'a pas beaucoup de sens. ** Je ne suis pas sûr, donc pour le moment, j'aimerais écrire un programme qui calcule et affiche honnêtement le nombre de mouvements pour trouver la règle. Vous pouvez l'écrire sur papier, mais il est plus facile et moins sujet aux erreurs de le programmer. ** (Pour référence, j'ai dépensé 5 $ pour écrire ce code, et j'ai eu beaucoup de mal à l'écrire sur papier pendant le concours)
def change(a, b, p): for c in range(K): for d in range(K): if (a + b) == (c + d) or (a - b) == (c - d) or (abs(a - c) + abs(b - d)) <= 3: if grid[c][d] == -1: grid[c][d] = p + 1 K = 41 grid = [[-1] * K for _ in range(K)] grid[K // 2][K // 2] = 0 for i in range(10): for a in range(K): for b in range(K): if grid[a][b] == i: change(a, b, i) for row in grid: print(*row)Ensuite, la sortie ressemblera à ceci.
1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 0 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1** Apparemment, j'ai l'impression de pouvoir le déplacer avec un maximum de 3 $, alors réfléchissons à pourquoi cela se produit. ** **
Supposons que vous ayez un échiquier noir et blanc et que vous commenciez par un carré noir. ** Déplacez-vous en diagonale $ 2 $ Vous pouvez vous déplacer à la main sur n'importe quelle case noire de l'échiquier. Cependant, il n'est pas possible de se déplacer vers un carré blanc simplement en se déplaçant en diagonale. Si le but est un carré blanc, vous pouvez le déplacer vers le carré noir juste à côté du but de 2 $ $, puis le déplacer de 1 $. De cette façon, vous pouvez vous déplacer vers n'importe quelle case de l'échiquier pour moins de 3 $. ** Pour cette raison, 2 $ et 3 $ sont disposés comme un échiquier. (Commentaire officiel a également un chiffre)
Maintenant que nous savons que nous n'avons qu'à penser à 3 $ $, considérons les expressions conditionnelles qui déterminent le nombre de mains que nous aurons.
Quand tu as 0 mains
Vous n'avez pas besoin de bouger uniquement lorsque le départ et l'objectif sont au même endroit. Gentiment, il met un étui à main de 0 $ dans l'échantillon.
Si vous en avez un
Vous pouvez bien sûr déplacer 1 $ à la main si vous pouvez déplacer de 1 $. (?) $ 1 $ Les conditions d'un endroit où vous pouvez vous déplacer à la main sont écrites dans l'énoncé du problème, donc si vous rencontrez l'un des 3 $ $, vous pouvez vous déplacer de 1 $.
a+b = c+d a-b = c-d |a-c| + |b-d| \le{3} Si vous avez deux mains
Est difficile. Tout d'abord, rappelez-vous que "Super Ryoma" peut déplacer 2 $.
** - Mouvement diagonal ** ** - Super Ryoma Move **
Le mouvement de la main à 2 $ est une combinaison des types de mouvement à 2 $. Il existe les modèles de 3 $ suivants pour la combinaison.
** - Super Ryoma déménage 2 $ fois ** ** - Mouvement diagonal 2 $ fois ** ** - Mouvement diagonal 1 $ fois et mouvement Super Ryoma 1 $ fois **
Super Ryoma Move 2 coups
Super Ryoma Move $ 1 $ Vous pouvez déplacer des carrés de 1 $ vers le haut, le bas, la gauche et la droite de 3 $ fois par main. En d'autres termes, vous pouvez déplacer Super Ryoma 2 $ à la main vers le haut, le bas, la gauche et la droite 6 $ fois.
** En termes simples, si la «distance de Manhattan» est inférieure à 6 $, vous pouvez la déplacer de 2 $. Par conséquent, la condition est la suivante. ** **
|a-c|+|b-d|\le{6} Mouvement diagonal 2 mains
Vous pouvez vous déplacer n'importe où dans la "masse de la même couleur que le point de départ" dans l'exemple de l'échiquier. Pensons un peu plus en détail pour le mettre dans la formule.
Mouvement diagonal $ 1 $ À la main, les coordonnées changent comme suit:
Par conséquent, la somme des changements dans les coordonnées $ x $ et $ y $ est soit $ + 2k $, $ 0 $ ou $ -2k $. ** Notez que la somme des changements est toujours égale. Cela signifie que peu importe le nombre de fois que vous vous déplacez en diagonale, la somme des changements ne s'arrêtera jamais dans un carré impair. (Ce concept est appelé parité / pair / impair) **
Inversement, n'importe quelle cellule avec une somme égale de changements peut être atteinte à la main, quelle que soit sa distance.
|a-c| + |b-d|Est pair (le reste après la division par 2 est égal à 0) - Mouvement diagonal $ 1 $ Main et mouvement super Ryoma 1 $ Main
Mouvement diagonal $ 1 $ Les cellules qui peuvent être déplacées à la main sont celles avec $ a + b = c + d $ ou $ a-b = c-d $. Une fois transposé, $ (a + b) - (c + d) = 0 $ et $ (a-b) - (c-d) = 0 $.
D'une place qui remplit cette condition, vous pouvez déplacer le Super Ryoma à une place avec une distance de Manhattan de 3 $ ou moins à la main.
|(a+b)-(c+d)|\le{3} |(a-b)-(c-d)|\le{3} Quand tu as 3 mains
$ 0 $ ~ $ 2 $ Si vous ne pouvez pas le déplacer à la main, c'est 3 $. Il n'y a pas besoin de juger.
la mise en oeuvre
Écrivez toutes les expressions conditionnelles. Il est plus facile de diviser la partie de jugement en fonctions et de renvoyer le moment où les conditions sont remplies.
Veuillez noter que la réponse correcte ne sera pas obtenue à moins que vous ne jugiez dans l'ordre de 0 $ main, 1 $ main, 2 $ main, 3 $ main de celle avec le moins de pas.
code
def solve(): #0 mains. Si vous ne regardez pas correctement l'échantillon, vous oublierez ce modèle. if a == c and b == d: return 0 #C'est un mouvement. Écrivez en fonction de l'énoncé du problème. if a + b == c + d: return 1 if a - b == c - d: return 1 if abs(a - c) + abs(b - d) <= 3: return 1 #Deux coups. Écrivez comme prévu. if abs(a - c) + abs(b - d) <= 6: return 2 if (abs(a - c) + abs(b - d)) % 2 == 0: # %Puisque la priorité de est élevée, ajoutez le côté gauche()Si vous ne le placez pas, ce sera WA (1 perte) return 2 if abs((a + b) - (c + d)) <= 3: return 2 if abs((a - b) - (c - d)) <= 3: return 2 #Si 2 coups ne suffisent pas, assurez-vous d'utiliser 3 coups. return 3 a, b = map(int, input().split()) c, d = map(int, input().split()) print(solve())Recommended Posts