Je vais vous expliquer comment résoudre le ** problème C "Many Requirements" ** du ** AtCoder Beginners Contest 165 ** avec ** Python 3 ** aussi soigneusement que possible.
C'était si long que je n'ai divisé que le problème C.
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) --Depth Priority Search (DFS) (Méthode PDF d'explication, ennuyeux)
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.
Quand j'ai réussi à déchiffrer l'énoncé du problème, il semble que ce que je veux que nous fassions soit une séquence de $ N $ de longueur. La longueur $ N $ est de 2 à 10. Si la colonne numérique remplit les conditions, vous obtiendrez un score, donc je veux que vous donniez la valeur maximale de ce score.
Les nombres dans la colonne des nombres sont supérieurs ou égaux à 1 $ et inférieurs ou égaux à $ M $. La limite supérieure de $ M $ est de 1 à 10. Et le nombre doit être identique ou supérieur au nombre précédent. Cela signifie que le nombre ne doit pas diminuer au milieu.
Par exemple, supposons $ N = 4 $ et $ M = 3 $.
Permettez-moi de vous donner un exemple du nombre de colonnes autorisé.
Permettez-moi de vous donner un exemple de mauvaise séquence de nombres. 1,1,3,2 $ (2 $ est supérieur à 3 $, vous ne pouvez donc pas venir après 3) 1,2,3,4 $ (4 $ dépassent la limite supérieure M $ = 3 $) 0,1,2,3 $ ($ 0 $ n'est pas bon car il est supérieur à 1 $) 1,1,1 $ (longueur $ N = 4 $) 1,1,1,1,1 $ (comme ci-dessus)
Enfin, il existe des conditions $ Q $. Il y a un maximum de 50 conditions, et une condition se compose de quatre entiers $ a, b, c, d $.
La condition est
($ b $ th dans la séquence créée) - ($ a $ th dans la séquence créée) = $ c $
Est d'être. Si tel est le cas, vous obtiendrez un score de $ d $.
Par exemple, la condition est
Par exemple, 1,1,2,3 $ et 1,2,3,3 $ vous donneront 5 $ points, mais 1,2,2,2 $ et 2,2,3,3 $ Je ne reçois pas de dollars.
J'aimerais que vous trouviez la valeur maximale du score total obtenu en vérifiant ceci pour toutes les conditions.
Le seul problème avec ce problème est de créer toutes les séquences possibles et de calculer chaque score pour trouver la valeur maximale. Par conséquent, vous ne pouvez jamais le résoudre à moins de vous rendre compte que vous pouvez tout atteindre.
La longueur maximale de la séquence de nombres est de 10 et le nombre maximal de 10, donc je ne pense pas qu'il y ait beaucoup de nombres qui puissent être créés. Si vous demandez le nombre exact tel qu'écrit dans le PDF d'explication, ce sera ~~ 20C10 = 184756 ~~ $ \ _ {19} C_ {10} = 92378 $. (Corrigé le 5/3. Merci @forzaMilan!)
Et comme la condition pour obtenir des points est de 50 au maximum, il semble que ce sera à temps même si vous vérifiez tous les chiffres que vous avez faits.
Eh bien, même si vous réalisez que vous pouvez faire un round-robin, vous ne pouvez pas le résoudre à moins de savoir comment faire toutes les séquences.
Le problème de la création de tels nombres et chaînes se pose parfois, vous pouvez donc le comprendre si vous résolvez des problèmes similaires. Cependant, si vous ne le savez pas, il sera difficile de le trouver pendant le concours.
Il existe plusieurs façons de créer une séquence de nombres.
--Utilisez itertools.combinations_with_replacement (le plus simple) --Créer avec une file d'attente récursive (méthode très polyvalente)
Le moyen le plus simple est d'utiliser la fonction combinaisons_with_replacement () du module ʻitertools`. Comme je l'ai appris plus tard, vous pouvez simplement utiliser cette fonction pour énumérer toutes les séquences de ce problème.
Le nom est long et difficile à retenir, mais c'est une fonction utile. Pour l'utiliser, vous devez importer le module ʻitertools`.
combinaisons_with_replacement () est une fonction qui énumère les "combinaisons en double". La différence avec les «combinaisons» habituelles «combinaisons ()» est que cela vous permet de sélectionner le même élément plusieurs fois.
Il y a deux entrées: un élément "itérable" et le nombre de fois que l'élément est récupéré (longueur de colonne). «Iterable» est «iterable» en anglais, ce qui signifie «répété». Ceux qui peuvent être utilisés après l'entrée de la boucle for, tels que "list", "taple", "range ()", et "character string".
La sortie est toutes les "combinaisons en double" qui peuvent être faites dans les conditions d'entrée. Chaque sortie sort dans "l'ordre des éléments d'entrée". C'est important.
Voyons ce qui est créé avec la boucle for et print (). Supposons qu'il y ait trois éléments, «range (1,4)», c'est-à-dire «(1,2,3)», et la longueur est de 2.
#Parce que c'est long, peigne_Importer avec le nom rplc
from itertools import combinations_with_replacement as comb_rplc
for seq in comb_rplc(range(1, 4), 2):
print(seq)
(1, 1)
(1, 2)
(1, 3)
(2, 2)
(2, 3)
(3, 3)
Il comprend également ceux dans lesquels le même élément apparaît plusieurs fois, tels que (1, 1) et (2, 2). Puisque l'entrée est de l'ordre de 1,2,3, il n'y a pas de numéro suivant plus petit que le nombre précédent comme (2, 1) et (3, 2).
Comparez avec la combinaison habituelle «combinaisons ()».
from itertools import combinations
for seq in combinations(range(1, 4), 2):
print(seq)
(1, 2)
(1, 3)
(2, 3)
Il n'y a certainement pas (1, 1) ou (2, 2) qui sélectionnent deux fois le même élément.
Essayez de régler l'entrée sur "CBA". Comme pour, il est considéré comme trois éléments: "" C ", " B ", et " A "`.
for seq in comb_rplc("CBA", 2):
print(seq)
('C', 'C')
('C', 'B')
('C', 'A')
('B', 'B')
('B', 'A')
('A', 'A')
Puisque je saisis dans l'ordre de C, B, A, la sortie est également organisée dans cet ordre. Veuillez noter qu'ils n'apparaissent pas dans l'ordre ABC.
La condition de la séquence de numéros créée dans ce problème est que le numéro suivant n'est pas inférieur au numéro précédent. Si l'entrée est dans l'ordre croissant, la sortie sera également dans l'ordre croissant, donc cette condition sera satisfaite sans autorisation.
La longueur de la séquence est $ N $ et la limite supérieure du nombre est $ M $, donc combinaisons_with_replacement (range (1, m + 1), n) peut énumérer toutes les séquences possibles.
Importez avec une abréviation telle que from itertools import combinaisons_with_replacement as comb_rplc pour éviter d'encombrer votre code.
from itertools import combinations_with_replacement as comb_rplc
n, m, q = list(map(int, input().split()))
#req est[[a1,b1,c1,d1],[a2,b2,c2,d2]……]C'est une liste de la liste contenant
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
#seq est un taple de longueur n
for seq in comb_rplc(range(1, m + 1), n):
score = 0
for a, b, c, d in req:
#Le kème de la colonne numérique écrite dans l'énoncé du problème est k s'il s'agit d'un index-Notez que ce sera 1
if seq[b - 1] - seq[a - 1] == c:
score += d
ans = max(ans, score)
print(ans)
«avec remplacement» signifie «remplacer». «Remplacer» est plus souvent utilisé pour signifier «remplacer» ou «remplacer», mais ce n'est pas le cas.
Supposons que vous ayez une balle numérotée dans votre sac. Dans une «combinaison» normale, c'est-à-dire «sans remplacement», la balle retirée n'est pas remise dans le sac. Dans la «combinaison en double» «avec remplacement», notez le nombre de balles retirées puis remettez-les dans le sac.
Il peut être plus facile de se souvenir de cette fonction si vous en comprenez la signification.
J'ai pu créer une séquence de nombres avec combinaisons_with_replacement () pour ce problème, mais à mesure que les conditions deviennent plus complexes, je dois l'implémenter moi-même.
Lorsque vous souhaitez créer toutes les chaînes de caractères et les nombres qui satisfont à certaines conditions, il existe une méthode très polyvalente appelée «file d'attente récursive».
Comme son nom l'indique, il utilise une structure de données (tableau) appelée file d'attente. À quoi ressemble une file d'attente, c'est un tableau qui "retire ce que vous mettez en premier" (FIFO: First In, First OUT). C'est un élément majeur qui ressort de l'étude des algorithmes.
Il répète en prenant les chaînes qui sont encore en cours de création à partir de la file d'attente, en leur ajoutant un caractère et en les ajoutant à la file d'attente.
Ensuite, tous les nombres que vous souhaitez créer sont finalement générés.
Pour utiliser les files d'attente en Python, vous devez importer le deque () du module collections.
"deque" est un acronyme pour "double-end-queue" et est un type de données appelé "les deux extrémités de la file d'attente". La prononciation est "deck".
Le deque peut extraire et ajouter des éléments du début ou de la fin. Autrement dit, il est compatible avec les piles et les files d'attente.
Il existe deux méthodes pour ajouter et récupérer des éléments à deque.
ʻAppend () : Ajouter un élément à droite (fin) ʻAppendleft () : Ajouter un élément à gauche (en premier)
pop () Extraire l'élément droit (fin)
popleft (): Extraire le (premier) élément gauche
"Sortez ce que vous avez mis en premier" dans la file d'attente est paraphrasé comme "lorsque vous le mettez par la droite" et "lorsque vous le sortez par la gauche".
En d'autres termes, si vous utilisez ʻappend () pour insérer et popleft () `pour extraire, vous pouvez réaliser la file par elle-même.
Dans le cas d'une pile, "sortez ce que vous avez mis plus tard", donc quand vous le sortez avec ʻappend () , c'est pop () `.
Jetons un coup d'œil au style pseudo-code de la récurrence de la file d'attente et voyons ce qu'il fait.
from collections import deque
que = deque()
que.append(Etat initial) # Etat initialを入れないと、while queを素通りします
while que:
État actuel= que.popleft() #Sortez depuis le début
#Faire quelque chose
répondre à la condition if:
#Faire quelque chose
else:
État suivant=État actuel+ α #Dans certains cas, for for crée plusieurs "états suivants"
que.append(État suivant) #Ajouter à la fin
while que signifie que si que n'est pas vide, il sera jugé comme True, et s'il est vide, il sera jugé comme False, donc il bouclera jusqu'à ce que le contenu de que soit vide.
Si les conditions sont remplies, une boucle infinie se produira si aucune action n'est entreprise sans ajouter à la file d'attente.
Cela permettra à la file d'attente d'être redémarrée.
from collections import deque
#Une fonction qui calcule le score d'une séquence de nombres
def calc(seq):
score = 0
for a, b, c, d in req:
if seq[b - 1] - seq[a - 1] == c:
score += d
return score
n, m, q = list(map(int, input().split()))
req = [list(map(int, input().split())) for _ in range(q)]
ans = 0
que = deque()
#Premier dans la colonne des nombres,[1]～[m]Sera ajouté à la file d'attente,
#En fait, ce problème se situe au début de la séquence[1]Il peut être résolu en ne considérant que le cas de.
for i in range(1, m + 1):
que.append([i])
while que:
seq = que.popleft()
if len(seq) == n:
#Maintenant que la longueur est n, calculez le score
score = calc(seq)
ans = max(ans, score)
else:
#Le nombre suivant à ajouter est que la limite inférieure est le dernier nombre de la séquence actuelle et la limite supérieure est m.
for i in range(seq[-1], m + 1):
seq_next = seq + [i]
que.append(seq_next)
print(ans)
J'écrirai comment le contenu de la file d'attente change lorsque m = 3 et n = 3.
[1], [2], [3](état initial) [2],[3],[1,1],[1,2],[1,3] [3],[1,1],[1,2],[1,3],[2,2],[2,3] [1,1],[1,2],[1,3],[2,2],[2,3],[3,3] [1,2],[1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3] [1,3],[2,2],[2,3],[3,3],[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3] …… (Omis) [2,3,3],[3,3,3] [3,3,3] Aucun (fin)
Vous enlevez celui à l'extrême gauche, ajoutez-y un numéro et ajoutez-le à droite. De cette façon, vous pouvez créer toutes les séquences.
Une longueur de 3 signifie que la séquence est terminée, donc vous calculez simplement le score et n'ajoutez aucun nouvel état à la file d'attente. En conséquence, la file d'attente sera finalement vide et vous ne tomberez pas dans une boucle infinie.
Ce problème peut également être résolu avec la pile «insérer de droite et retirer de droite» au lieu de la file d'attente «insérer de droite et sortir de gauche».
À propos, la pile peut être une liste régulière au lieu d'un deque. C'est parce que les méthodes ʻappend () et pop () `sont également dans la liste régulière.
Cependant, en gros, il est recommandé de traiter deque () comme une file d'attente et de la résoudre. Il y a trois avantages.
--Deque fonctionne plus rapidement à mesure que le nombre d'éléments augmente ――Lors de l'utilisation de files d'attente, il est parfois utile que les nombres et les chaînes de caractères apparaissent dans "l'ordre lexical". ――Il existe des possibilités d'utiliser deque autre que l'énumération de chaînes de caractères / chaînes de nombres, il est donc avantageux de s'y habituer.
La récurrence de la file d'attente est la "recherche de priorité de largeur" (BFS) elle-même. La récursivité de la pile entraîne une «recherche de priorité en profondeur» (DFS).
Vous pouvez faire l'un ou l'autre si vous créez simplement toutes les chaînes et tous les nombres, mais l'ordre dans lequel ils apparaissent est différent.
La dernière consiste à utiliser la recherche prioritaire en profondeur décrite dans le PDF du commentaire officiel. Utilisez "fonction récursive".
Vous pouvez faire beaucoup plus que la reconnaissance de file d'attente ou de pile, mais si vous souhaitez simplement créer des chaînes ou des nombres, la récursivité de la file d'attente suffit.
L'avantage de la recherche prioritaire en profondeur est
――Facile à mettre en œuvre "traitement en cours" et "traitement de retour" ――J'ai l'impression d'écrire un algorithme si je peux
L'inconvénient est
L'argument de la fonction dfs est la séquence courante seq (taple). La limite inférieure du nombre suivant est seq [-1] car c'est le dernier de la séquence actuelle.
Par exemple, supposons que vous ajoutiez 3 à la séquence 1,1 pour obtenir 1,1,3. Le prochain nombre à ajouter doit être 3 ou plus, donc (la limite inférieure du nombre suivant) est le 3 que nous venons d'ajouter.
Si la longueur de la colonne numérique actuelle est inférieure à n, ajoutez (limite inférieure du nombre) à (limite supérieure du nombre m) et ajoutez à nouveau toutes les nouvelles colonnes numériques à dfs (chaîne numérique actuellement créée, longueur de la colonne numérique créée maintenant, La valeur minimale des nombres suivants).
Si la colonne numérique actuelle est 1,1,3 et la limite supérieure est $ M = 4 $, 1,1,3,3 1,1,3,4 Doit être transmis à dfs.
Lorsque la longueur est n et qu'elle est terminée, le score est calculé. Lorsque vous obtenez un score, mettez à jour la valeur maximale avec ʻans = max (ans, score) `. C'est la même chose qu'un problème normal.
Quand tout est fait, toutes les valeurs maximales seront retournées dans le code du corps principal, donc imprimez ceci et vous avez terminé.
def dfs(seq):
#La valeur de retour est le score maximum ans pour toutes les colonnes.
ans = 0
if len(seq) == n:
#Maintenant que la séquence est terminée, calculez le score
score_ret = 0
for a, b, c, d in req:
if seq[b-1] - seq[a-1] == c:
score_ret += d
return score_ret #Renvoie le score de cette séquence de nombres
else:
#Le nombre de lignes n'est pas encore terminé
for i in range(seq[-1], m + 1):
seq_next = seq + (i,) #Taple de longueur 1(i,)Enchaîner
score = dfs(seq_next) # seq_Renvoie le score maximum dans toutes les séquences dérivées de next
ans = max(ans, score) #Mettre à jour le score maximum
#Renvoie le score maximum
return ans
n, m, q = list(map(int, input().split()))
#req est[[a1,b1,c1,d1],[a2,b2,c2,d2]……]C'est une liste de la liste contenant
req = [list(map(int, input().split())) for _ in range(q)]
#Assurez-vous d'obtenir la réponse à la fin. Tout le traitement est effectué par la méthode dfs.
#Si c'est une liste, j'ai peur de réécrire la valeur par erreur quelque part, alors je vais en faire un taple
#Vous n'avez pas à y penser sauf lorsque le premier est 1.(1,)Je ne ferai que
ans = 0
score = dfs((1,))
ans = max(ans, score)
print(ans)
J'ai écrit à plusieurs reprises que je n'ai pas à y penser sauf lorsque le premier dans la colonne des nombres est 1. Dans la recherche de priorité de profondeur du code 3, seul le début de 1 est réellement recherché complètement.
La raison en est que le "b-ième élément et le a-ième" "différence" "est important, et le nombre lui-même peut être n'importe quoi.
Par exemple, 2,3,3,4 a la même différence que 1,2,2,3 et 3,3,3,3 a la même différence que 1,1,1,1. Comme vous pouvez le voir, il existe toujours une séquence de nombres équivalente commençant par 1 dans toute séquence autre que 1 commençant.
Vous pouvez tout faire séparément, mais si vous le remarquez, cela peut être un peu plus facile à mettre en œuvre. Au fait, le temps d'exécution sera divisé par deux, mais cela n'a pas d'importance car il ne devient pas TLE même si vous recherchez tous les endroits sauf le début de 1.
Voici quelques problèmes similaires. Le problème principal est juste le bon niveau de difficulté auquel s'habituer. 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
Recommended Posts