[Explication AtCoder] Contrôlez les problèmes A, B, C, D d'ABC181 avec Python!

** Les problèmes A, B, C, D ** du ** AtCoder Beginner Contest 181 ** seront expliqués aussi soigneusement que possible avec ** Python 3 **.

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é ABC181](# abc181-Résumé) [Un problème "Rotation lourde"](# un problème de rotation lourde) [B problème "Trapezoid Sum"](#b problème trapezoid-sum) [Problème C "Colinéarité"](#c problème de colinéarité) [D problème "Hachi"](#d problème hachi)

Résumé ABC181

Nombre total de soumissions: 6643

performance

Performance AC But temps Classement(Dans les limites)
200 AB---- 300 20 min 5056(4953)Rang
400 ABC--- 600 77 minutes 4179(4077)Rang
600 ABC--- 600 28 minutes 3435(3333)Rang
800 ABCD-- 1000 95 minutes 2647(2549)Rang
1000 ABCD-- 1000 60 minutes 1918(1822)Rang
1200 ABC-E- 1100 87 minutes 1324(1230)Rang
1400 ABCDE- 1500 83 minutes 873(789)Rang
1600 ABCDE- 1500 61 minutes 558(476)Rang
1800 ABCDE- 1500 44 minutes 345(269)Rang
2000 ABCDEF 2100 103 minutes 197(139)Rang
2200 ABCDEF 2100 72 minutes 104(66)Rang
2400 ABCDEF 2100 56 minutes 52(30)Rang

Taux de réponse correct par couleur

Couleur Nombre de personnes A B C D E F
Cendre 2714 99.0 % 84.1 % 43.0 % 18.0 % 1.4 % 0.1 %
thé 1228 99.8 % 99.7 % 85.8 % 61.5 % 4.2 % 0.1 %
vert 972 99.7 % 99.7 % 96.2 % 87.7 % 37.4 % 0.4 %
eau 574 99.8 % 99.8 % 98.6 % 95.1 % 86.6 % 7.0 %
Bleu 291 99.7 % 99.7 % 100.0 % 98.6 % 98.3 % 38.5 %
Jaune 78 97.4 % 97.4 % 98.7 % 98.7 % 88.5 % 55.1 %
Orange 22 95.5 % 95.5 % 100.0 % 100.0 % 95.5 % 81.8 %
rouge 3 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

Bref commentaire

Un problème (6568 personnes AC) "Rotation lourde"
La réponse dépend du fait que le nombre de jours est pair ou impair.
Problème B (5936 personnes AC) "Trapezoid Sum"
La méthode pour ajouter de manière simple $ A $ à $ B $ n'est pas à temps. La somme de chaque plage peut être calculée à l'aide d'une formule mathématique, en utilisant le fait qu'il s'agit d'une séquence d'égalité.
Problème C (4329 personnes AC) "Colinéarité"
$ 3 $ Juge pour toutes les combinaisons de points dans une boucle lourde. La formule du jugement est les mathématiques du secondaire. J'ai cherché sur Google.
Problème D (3152 AC) "Hachi"
"Un certain entier est un multiple de 8" ⇔ "Les 3 derniers chiffres d'un certain entier sont un multiple de 8". Essayez de rendre tous les candidats à 3 chiffres possibles, et si vous pouvez en créer un, c'est OK.
E problème (1344 personnes AC) "Enseignant transformable" [non expliqué dans cet article]
Fixez la hauteur de l'enseignant et triez le nombre de hauteurs ajoutées aux élèves par ordre croissant. À ce stade, il est préférable de s'associer avec la personne suivante comme $ (1, 2), (3, 4), (5, 6), ... $. Pour tous les candidats de taille d'enseignant, découvrez le nombre d'enseignants dans la dichotomie. Il peut être résolu en calculant efficacement la somme totale des différences à ce moment en utilisant la somme cumulée.
Problème F (230 personnes AC) "Silver Woods" [non expliqué dans cet article]
Obtenir toutes les "distance entre un certain point et la ligne droite supérieure", "distance entre un certain point et la ligne droite inférieure" et "distance entre deux points" à l'avance. Utilisez UnionFind pour concaténer les composants par ordre croissant de distance. La réponse est la distance lorsque les lignes droites supérieure et inférieure ont le même composant de connexion.

Résultats de moi (Unidayo) (référence)

screenshot.308.png

Les problèmes C et D ont été recherchés sur Google. C'était un peu difficile parce que je n'étais pas doué pour mettre en œuvre le problème E, mais dans l'ensemble, c'était un bon résultat.

Un problème "Rotation lourde"

** Page de problème **: A - Rotation lourde ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 99,0% ** <font color = # 804000> Brun </ font> Taux de réponse correcte du codeur **: 99,8% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 99,7%

Considération

Si $ N $ est impair, c'est «" Noir "», et s'il est pair, c'est «« Blanc »». Si le reste de $ N $ divisé par 2 $ est égal à 0 $, c'est un nombre pair, et s'il vaut 1 $, c'est un nombre impair.

code

N = int(input())

if N % 2 == 1:
    print("Black")
else:
    print("White")

Problème B "Somme trapézoïdale"

** Page de problème **: B --Trapezoid Sum ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 84,1% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 99,7% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 99,7%

Considération

Comme indiqué dans le code ci-dessous, la méthode d'ajout d'entiers de $ A $ à $ B $ est TLE.

N = int(input())

ans = 0
for _ in range(N):
    a, b = map(int, input().split())
    for x in range(a, b + 1):
        ans += x

print(ans)

Afin de le faire à temps, il est nécessaire de calculer la somme de chaque plage avec une seule formule.

Il y a environ 2 $ dans les formules, mais les deux sont similaires.

  • $ (somme des entiers de 1 à B) - (somme des entiers de 1 à A - 1) Recherche par $ --Utilisez la formule de somme de la séquence d'égalité avec le premier terme $ A $, le nombre de termes $ B-A + 1 $ et la tolérance de $ 1 $.

Cette fois, je vais expliquer le premier simple.

Comment trouver la somme de 1 à x

$ S = (somme de 1 à x) $ est calculé par la formule suivante. Cette expression est toujours divisible en un entier.

S = \frac{x{(x+1)}}{2}

Dans le code, cela ressemble à ceci: Notez que nous utilisons // (division entière) pour tronquer après la virgule décimale.

s = x * (x + 1) // 2

** Cette formule est très souvent utilisée chez les pros de la compétition. Si vous ne vous en souvenez pas, il est toujours utile de vous en souvenir à cette occasion. ** **

code

def calc(x):
#Une fonction qui renvoie la somme de 1 à x
    return x * (x + 1) // 2


N = int(input())

ans = 0

for _ in range(N):
    a, b = map(int, input().split())
    ans += (calc(b) - calc(a - 1))

print(ans)

Problème C "Colinéarité"

** Page de problème **: C --Collinearity ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 43,0% ** <font color = # 804000> Brun </ font> Taux de réponse correcte du codeur **: 85,8% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 96,2%

Considération

Le nombre maximum de points est de 10 $ ^ 2 = 100 $, il suffit donc de juger si les trois combinaisons de points sont sur la même ligne droite ou d'utiliser une boucle lourde de 3 $.

La condition que les points $ 3 $ soient sur la même ligne droite est que l'équation suivante est vraie. (Pour plus de détails, laissez-le à Official Commentary et à la recherche Google)

(x_2-x_1)(y_3-y_1) = (x_3-x_1)(y_2-y_1)

code

def judge():
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(j + 1, N):
                x1, y1 = P[i]
                x2, y2 = P[j]
                x3, y3 = P[k]
                fx, fy = x2 - x1, y2 - y1
                sx, sy = x3 - x1, y3 - y1
                if fx * sy == sx * fy:
                    return True
    return False


N = int(input())
P = []

for _ in range(N):
    x, y = map(int, input().split())
    P.append((x, y))

if judge():
    print("Yes")
else:
    print("No")

Problème D "Hachi"

** Page de problème **: D --Hachi ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 18,0% ** <font color = # 804000> Brown </ font> Taux de réponse correcte du codeur **: 61,5% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 87,7%

Considération

Lorsque S est 1 ou 2 chiffres

Dans le cas de chiffres de 1 $, il ne peut pas être trié, vous pouvez donc simplement juger s'il est divisible par 8 $.

Dans le cas de chiffres de 2 $ $, vous pouvez déterminer s'il s'agit d'un modèle «utiliser tel quel» ou «retourner» $ 2 $, divisible par 8 $.

Lorsque S est égal ou supérieur à 3 chiffres

** "Un certain entier est un multiple de 8" ⇔ "Les 3 derniers chiffres d'un certain entier sont un multiple de 8" **. Je vais laisser les détails ailleurs, car 1000 $ est un multiple de 8 $.

Autrement dit, si vous pouvez réorganiser ** $ S $ librement et que même les 3 derniers chiffres $ sont un multiple de 8 $ $, vous pouvez en faire un multiple de 8 $ $. ** **

Il n'y a que des multiples de plus de 100 $ de 8 $ dans le chiffre de 3 $. Par conséquent, il peut être résolu par ** "déterminer s'il peut être fait pour tous les multiples de 8 $ de chiffres de 3 $" **.

Méthode de jugement

Par exemple, si vous voulez que les 3 derniers chiffres soient de 112 $ $, vous pouvez le faire si $ 1 $ vaut 2 $ ou plus et 2 $ est 1 $ ou plus dans $ S $.

Pour faire ce jugement, vous devez compter à l'avance combien de $ 1 $ à 9 $ $ sont inclus dans $ S $.

la mise en oeuvre

Compteur lors du comptage

Lors du comptage, il est plus facile d'utiliser le Compteur dans le module collections.

>>> from collections import Counter
>>> S = "181"
>>> cnt_first = Counter(S)
>>> cnt_first
Counter({'1': 2, '8': 1})  # '1'2 pièces,'8'Il existe une

Comment faire un multiple de 3 chiffres 8

for x in range(104,1000,8):
    #En traitement

Spécifiez l'argument de «plage» comme suit.

Point de départ: 3 $ Le plus petit multiple de 8 $ en chiffres 104 $ Point final: 1000 $ (moins de) Étapes: $ + 8 $ chacun

Vous pouvez maintenant énumérer 104, 112, 120, ..., 984, 992 $.

code

from collections import Counter


def judge():
    if len(S) == 1:
        if int(S) % 8 == 0:
            return True
    elif len(S) == 2:
        if int(S) % 8 == 0 or int(S[::-1]) % 8 == 0:
            return True
    else:
        for x in range(104, 1000, 8):
            cnt_current = Counter(str(x))
            ok = True
            for key, val in cnt_current.items():
                if val > cnt_original[key]:
                    ok = False
            if ok:
                return True
    return False


S = input()
cnt_original = Counter(S)  #Vous pouvez voir combien de lettres 1 à 9 sont dans S

if judge():
    print("Yes")
else:
    print("No")

De côté

Commentaire officiel est plus intelligent d'utiliser «Counter». Je pense que vous pouvez le faire de cette façon.

Nous soustrayons entre les Counters et disons que nous pouvons le faire s'il devient vide.

Recommended Posts