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

** AtCoder Beginner Contest 182 ** ** Le problème A, B, C ** sera expliqué 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 contacter ** Commentaires ** ou ** Twitter **! Twitter: u2dayo

table des matières

[Résumé ABC182](# abc182-Résumé) [Un problème "twiblr"](#a problem twiblr) [Problème B "Presque GCD"](#b problème presque-gcd) [Problème C "à 3"](#c problème à-3)

Résumé ABC182

Nombre total de soumissions: 7497

performance

Performance AC But temps Classement(Dans les limites)
200 AB---- 300 37 minutes 5814(5649)Rang
400 ABC--- 600 96 minutes 4832(4668)Rang
600 ABC--- 600 44 minutes 3991(3829)Rang
800 ABCD-- 1000 100 minutes 3118(2956)Rang
1000 ABCD-- 1000 50 minutes 2306(2144)Rang
1200 ABCDE- 1500 96 minutes 1631(1475)Rang
1400 ABCDE- 1500 67 minutes 1117(965)Rang
1600 ABCDE- 1500 50 minutes 744(596)Rang
1800 ABCDE- 1500 37 minutes 483(341)Rang
2000 ABCDE- 1500 27 minutes 304(181)Rang
2200 ABCDEF 2100 97 minutes 185(88)Rang
2400 ABCDEF 2100 80 minutes 110(40)Rang

Taux de réponse correct par couleur

Couleur Nombre de personnes A B C D E F
Cendre 3040 99.1 % 69.9 % 42.3 % 12.5 % 2.9 % 0.0 %
thé 1461 99.5 % 97.7 % 87.7 % 51.8 % 12.7 % 0.1 %
vert 1122 99.5 % 99.5 % 97.2 % 87.5 % 50.7 % 0.6 %
eau 692 100.0 % 100.0 % 98.8 % 97.7 % 86.6 % 3.6 %
Bleu 357 100.0 % 100.0 % 99.2 % 98.9 % 97.2 % 24.4 %
Jaune 134 96.3 % 96.3 % 95.5 % 96.3 % 91.8 % 59.7 %
Orange 27 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 77.8 %
rouge 7 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 100.0 %

Bref commentaire

Un problème (7436 personnes AC) "twiblr"
Arithmétique.
Problème B (6249 AC) "Presque GCD"
$ A_i $ peut aller jusqu'à 1000 $ $. $ 1000 $ n'est jamais divisible par des nombres supérieurs à $ 1001 $. Vous pouvez en fait essayer combien de $ 2 $ à $ 1000 $ sont divisibles et afficher le nombre maximum.
Problème C (5077 personnes AC) "To 3"
$ N $ est inférieur à 10 $ ^ {18} $. Autrement dit, il n'y a que jusqu'à 18 $ de chiffres. Il existe des moyens de 2 $ pour effacer des chiffres, jusqu'à 18 $ pour chaque chiffre, avec ou sans effacement. Les rues $ 2 ^ {18} $ représentent environ 26 $ 10 000 $ rues, vous pouvez donc essayer d'effacer tous les chiffres et voir s'il s'agit d'un multiple de 3. Il s'agit de l'algorithme dit ** bit full search **. Notez que vous n'êtes pas autorisé à tout effacer jusqu'à $ 0 $, auquel cas vous imprimerez $ -1 $.
Problème D (3419 personnes AC) "Wandering" [non expliqué dans cet article]
Utilisez la somme cumulée. Vous pouvez le comprendre en l'écrivant sur papier.
E problème (1988 AC) "Akari" [non expliqué dans cet article]
Il est trop tard pour vérifier l'espace que la lumière atteint pour toutes les ampoules jusqu'à 50 millions de dollars. ** "Je sais que l'avenir est déjà illuminé" ** Si vous vous arrêtez à ce stade, le montant du calcul sera de $ O (HW + N + M) $ et ce sera à temps.
Problème F (233 personnes AC) "Paiements valides" [non expliqué dans cet article]
Cela semble être une méthode de planification dynamique.

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

screenshot.351.png

Je pense que j'aurais dû réfléchir au problème D un peu plus calmement.

Un problème "twiblr"

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

Considération

C'est une simple arithmétique, mais c'est un gaspillage d'obtenir une pénalité avec élan, donc ce peut être une bonne idée de s'arrêter un moment et de la vérifier.

code

A, B = map(int, input().split())
print(2 * A + 100 - B)

Problème B "Presque GCD"

** Page de problème **: B --Almost GCD ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 69,9% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 97,7% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 99,5%

Considération

** Supposons que vous ayez un entier positif $ K $. $ K $ n'est jamais divisible par des nombres supérieurs à $ K $. ** Par exemple, 6 $ $ n'est jamais divisible par des nombres supérieurs à 7 $.

Étant donné que la valeur maximale de la colonne numérique dans ce problème est fixée à 1 000 $, il est certain que les nombres supérieurs à 1001 $ ne sont pas divisibles par 1 $ donné.

De 2 $ à 1000 $, candidats à la réponse, vous pouvez essayer tous les nombres divisibles de la séquence.

code

N = int(input())
A = list(map(int, input().split()))

ans = 0
current_max = 0

for x in range(2, 1001):
    score = 0  #C'est un nombre divisible (degré GCD)
    for a in A:
        if a % x == 0:
            score += 1
    if score > current_max:
        ans = x
        current_max = score

print(ans)

Problème C "à 3"

** Page de problème **: C --To 3 ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 42,3% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 87,7% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 97,2%

Considération

Cela peut sembler être un problème qui nécessite une considération mathématique, mais en fait, il peut être résolu sans imaginer ** "Rechercher toutes les manières possibles d'effacer les chiffres et juger" **.

La contrainte $ N $ est inférieure à 10 $ ^ {18} $. Il comporte un maximum de 18 $ de chiffres. Pour chaque chiffre, il y a $ 2 $ façons d'effacer ou de ne pas effacer. Par conséquent, il existe jusqu'à $ 2 ^ {18} $ façons d'effacer des chiffres. 2 $ ^ {18} = 262 144 $. Vous pouvez tous les essayer à temps.

(La méthode $ 1 $ pour effacer tous les chiffres n'est pas autorisée, donc c'est en fait $ 2 ^ {18} -1 = 262,143 $, mais elle est incluse pour plus de simplicité)

la mise en oeuvre

"Utiliser / Ne pas utiliser" est une "recherche peu complète"

Lorsque vous voulez rechercher toutes les rues $ 2 $ de "utiliser / ne pas utiliser" comme ce problème, utilisez la méthode dite ** "recherche complète de bits" **.

Je vais omettre les détails de la recherche peu complète. (En fait, je veux écrire en détail, mais il est difficile d'écrire en détail chaque fois qu'une recherche complète sort, donc je peux le résumer quelque part)

En python, la recherche de bits complets est plus facile avec le product du module itertools.

from itertools import product
product((True, False), repeat=l)

Si vous écrivez ceci, toutes les combinaisons qui peuvent être faites avec «True» ou «False» pour chaque élément d'une longueur de $ l $ seront générées.

Méthode de jugement des multiples de 3

** "Effacer les nombres, les coller ensemble et les reconvertir en nombres entiers pour déterminer s'ils sont divisibles par 3 $" semble évidemment ennuyeux. ** **

Par conséquent, il peut être facilement implémenté en utilisant ** "un certain entier $ N $ est un multiple de $ 3 $" ⇔ "la somme des nombres dans chaque chiffre de $ N $ est un multiple de $ 3 $". ** **

(Exemple: 18 $ → 1 + 8 = 9 $, 762 $ → 7 + 6 + 2 = 15 $)

Plus précisément, créez une liste de $ N $ décomposée par des chiffres $ 1 $. Par exemple, $ 1234567 $ serait «[1,2,3,4,5,6,7]». Si vous souhaitez utiliser un certain chiffre sans l'effacer, ajoutez-le à la somme des chiffres, et si vous l'effacez, ne l'ajoutez pas. Enfin, vous pouvez déterminer si la somme des chiffres est un multiple de 3 $.

Tu ne peux pas tout effacer

Si vous effacez tous les chiffres, la somme des chiffres sera de 0 $, donc ce sera toujours un multiple de 3 $. Cependant, ce problème n'est pas autorisé.

Il est difficile de l'exclure, donc si la réponse est la valeur par défaut, vous pouvez afficher $ -1 $.

code

from itertools import product

#Pour le moment, il est plus facile à gérer si vous faites une liste de nombres chiffre par chiffre A après l'avoir reçue sous forme de chaîne de caractères S.
# N = 6227384 -> A = [6,2,2,7,3,8,4]

S = input()
A = [int(x) for x in S]

l = len(S)  #Le nombre de chiffres dans S (puisque S a été reçu sous forme de chaîne, len(S)Peut être utilisé)
ans = l

for bits in product((True, False), repeat=l):
    digit_sum = 0  #C'est la somme des chiffres non effacés
    score = 0  #Le nombre avec les chiffres effacés, plus le nombre est petit, mieux c'est
    for i, bit in enumerate(bits):
        if bit:
            #Utiliser sans effacer le i-ème chiffre du haut
            digit_sum += A[i]
        else:
            #Effacez le i-ème chiffre du haut
            score += 1

    if digit_sum % 3 == 0:
        #Si la méthode d'effacement est un multiple de 3, mettez à jour la valeur minimale.
        ans = min(ans, score)

if ans == l:
    #Ce n'était pas un multiple de 3, donc-Sortie 1
    print(-1)
else:
    print(ans)

Recommended Posts