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

** Les problèmes A, B, C, D ** du ** AtCoder Beginner Contest 183 ** 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é ABC183](# abc183-Résumé) [Un problème "ReLU"](#a problem relu) [B problème "Billiards"](#b problème de billard) [C problem "Travel"](#c problem travel) [D problème "Chauffe-eau"](#d problème de chauffe-eau)

Résumé ABC183

Nombre total de soumissions: 7199

performance

Performance AC But temps Classement(Dans les limites)
200 AB---- 300 32 minutes 5526(5365)Rang
400 ABC--- 600 99 minutes 4586(4426)Rang
600 ABC--- 600 38 minutes 3791(3632)Rang
800 ABCD-- 1000 88 minutes 2963(2807)Rang
1000 ABCD-- 1000 46 minutes 2194(2038)Rang
1200 ABCD-- 1000 21 minutes 1554(1399)Rang
1400 ABCDE- 1500 70 minutes 1060(911)Rang
1600 ABCDEF 2100 122 minutes 700(557)Rang
1800 ABCDEF 2100 77 minutes 440(315)Rang
2000 ABCDEF 2100 59 minutes 273(164)Rang
2200 ABCDEF 2100 46 minutes 161(78)Rang
2400 ABCDEF 2100 37 minutes 100(35)Rang

Taux de réponse correct par couleur

Couleur Nombre de personnes A B C D E F
Cendre 2960 99.5 % 69.2 % 35.0 % 12.5 % 1.9 % 0.8 %
thé 1377 99.7 % 91.7 % 87.5 % 57.4 % 5.8 % 2.5 %
vert 1086 99.6 % 96.9 % 97.0 % 90.7 % 26.4 % 7.6 %
eau 664 99.8 % 97.4 % 99.5 % 98.6 % 69.7 % 34.5 %
Bleu 333 100.0 % 99.7 % 100.0 % 100.0 % 94.6 % 76.0 %
Jaune 124 95.2 % 94.3 % 94.3 % 95.2 % 96.0 % 91.9 %
Orange 28 100.0 % 100.0 % 100.0 % 100.0 % 100.0 % 96.4 %
rouge 9 88.9 % 88.9 % 88.9 % 88.9 % 88.9 % 100.0 %

Bref commentaire

Un problème (7152 personnes AC) "ReLU" Utilisez l'instruction
if pour séparer les cas.
Problème B (5919 AC) "Billard"
Vous pouvez voir cela en considérant le rapport entre "vitesse dans la direction $ x $" et "vitesse dans la direction $ y $".
Problème C (4633 AC) "Voyage"
Maximum $ (8-1)! = 7! = 5040 $ Essayez toutes les commandes de visites de rue. En Python, vous pouvez facilement générer toutes les séquences en utilisant `itertools.permutations`.
Problème D (3400 personnes AC) "Chauffe-eau" En utilisant la somme cumulée
(méthode imos), vous pouvez savoir combien d'eau chaude est utilisée à chaque fois par $ O (N) $.
E problème (1393 personnes AC) "Queen on Grid" [non expliqué dans cet article]
Somme cumulée DP.
Problème F (789 personnes AC) "Confluence" [non expliqué dans cet article] Utilisez
Unionfind et $ N $ Counters. Si vous ajoutez le compteur de taille plus petite à la taille plus grande du composant de liaison, ce sera à temps.

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

screenshot.381.png

C'était un codeur bleu ** pendant seulement ** 23 heures.

Un problème "ReLU"

** Page de problème **: A --ReLU ** <font color = # 808080> Gris </ font> Taux de réponse correcte du codeur **: 99,5% ** <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,6%

La fonction ReLu est une fonction souvent utilisée comme fonction de transfert pour l'apprentissage en profondeur.

code

x = int(input())
if x >= 0:
    print(x)
else:
    print(0)

Problème B "Billard"

** Page de problème **: B --Billiards ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 69,2% ** <font color = # 804000> Marron </ font> Taux de réponse correcte du codeur **: 91,7% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 96,9%

Considération

$ G_x --S_x = T_x $, $ S_y + G_y = T_y $. À partir du Diagramme de commentaire officiel, vous pouvez penser au triangle ci-dessous.

abc183b.png

La relation suivante tient à la similitude et au rapport des triangles.

Δx = \frac{S_y}{T_y}・ T_x

La réponse est $ S_x + Δx $ car $ Δx $ est la longueur de $ S_x $ au point de réflexion sur le mur. Notez que $ T_x $ et $ Δx $ sont négatifs lorsque la cible est sur le côté gauche (direction moins de l'axe $ x $). Par conséquent, il n'est pas nécessaire de séparer les affaires.

code

sx, sy, gx, gy = map(int, input().split())

tx = gx - sx
ty = sy + gy
dx = tx * sy / ty
print(sx + dx)

Problème C "Voyage"

** Page de problème **: C --Travel ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 35,0% ** <font color = # 804000> Brown </ font> Taux de réponse correcte du codeur **: 87,5% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 97,0%

Considération

** * Il est plus facile de comprendre s'il correspond à l'indice du tableau, donc nous partirons de la ville $ 0 $. ** **

La ville 0 $ au début et la ville 0 $ à la fin sont fixes quel que soit l'ordre dans lequel vous visitez la ville.

Il y a un total de $ (N-1)! $ Façons de visiter la ville de 1 $ à $ N -1 $. Le maximum est $ N = 8 $, il n'y a donc que 7 $! = 5040 $.

** Par conséquent, il suffit d'essayer toutes les commandes de visite et de compter le nombre de choses qui ne valent que $ K $. ** **

la mise en oeuvre

Si vous souhaitez générer toutes les séquences possibles en Python, vous pouvez utiliser les permutations du module itertools.

Dans ce numéro, je souhaite créer toutes les séquences qui peuvent être triées par (1, 2, 3, ..., N -1). Pour ce faire, passez range (1, N) comme argument pour permutations.

Plus précisément, vous pouvez écrire comme suit.

for per in permutations(range(1, N)):
    #En traitement

code

from itertools import permutations

N, K = map(int, input().split())
T = []

for _ in range(N):
    s = list(map(int, input().split()))
    T.append(s)

ans = 0

for per in permutations(range(1, N)):
    score = 0  #C'est le temps pris dans l'ordre de cette visite
    prev = 0  #Premier départ de la ville 0
    for i in range(N - 1):
        cur = per[i]
        score += T[prev][cur]  #Tête de ville précédente à ville cur
        prev = cur
    score += T[prev][0]  #Allez enfin en ville 0

    if score == K:
        #Si vous pouvez vous déplacer avec juste K, la réponse+1
        ans += 1

print(ans)

D problème "Chauffe-eau"

** Page de problème **: D - Chauffe-eau ** <font color = # 808080> Gray </ font> Taux de réponse correcte du codeur **: 12,5% ** <font color = # 804000> Brun </ font> Taux de réponse correcte du codeur **: 57,4% ** <font color = # 008000> Vert </ font> Taux de réponse correcte du codeur **: 90,7%

Considération

Les heures sont séparées par des nombres entiers et ont un maximum de 200 000 $. Par conséquent, envisagez de créer un tableau qui enregistre la quantité d'eau chaude consommée chaque heure. Bien sûr, ajouter $ P_i $ à chaque section de personnes $ N $ n'est pas suffisant.

Par conséquent, nous utilisons la somme cumulée. ** "Ajouter $ P_i $ de $ S_i $ à $ T_i --1 $" ** peut être paraphrasé de cette façon.

  • ** "$ + P_i $ de $ S_i $ à la fin du tableau" **
  • ** "$ -P_i $ de $ T_i $ à la fin du tableau" **

Si vous ne faites que la première opération avec la somme cumulative habituelle, $ P_i $ sera ajouté après $ T_i $. Par conséquent, si vous soustrayez $ P_i $ après $ T_i $ pour l'annuler, vous pouvez ajouter à l'intervalle par somme cumulative.

Faites ces opérations de 2 $ sur un tableau de 1 $ de personnes chacune. Enfin, trouvez la somme cumulée et voyez si la consommation d'eau chaude est inférieure à $ W $ à tout moment. Pour ce faire, vous pouvez utiliser la fonction max pour déterminer si la somme cumulative maximale est inférieure ou égale à $ W $.

Notez que ** "l'algorithme qui ajoute des intervalles à l'aide de sommes cumulées" ** utilisé dans ce problème est parfois appelé la ** méthode imos ** du nom du développeur. Si vous le faites pour un tableau à une dimension, c'est un algorithme simple qui ne fait que l'opération de somme cumulative $ 2 $ fois.

code

À partir du commentaire de @ c-yan, il a été amélioré d'utiliser la fonction max pour le jugement final. Merci!

from itertools import accumulate

C = 200005  #La longueur C de la séquence de somme cumulée. Définissez le nombre de manière appropriée supérieur à 200 000.

N, W = map(int, input().split())
seq_a = [0] * C

for _ in range(N):
    s, t, p = map(int, input().split())
    seq_a[s] += p
    seq_a[t] -= p

S = list(accumulate(seq_a))

if max(S) <= W:
    print('Yes')
else:
    print('No')

Recommended Posts