[PYTHON] Critique du concours AtCoder
Les résultats de cette fois
Impressions de cette époque
Le problème C semblait être grave et ce n'était pas si difficile, alors j'aurais dû le considérer correctement. J'ai essayé de créer un problème E, mais je ne pouvais pas y penser assez et ne pouvais pas finir de le résoudre pendant le concours. Je suis très déçu.
Problème A
Quand j'ai pensé que j'avais changé la politique parce que la phrase for apparaissait dans le problème A, je manquais tout simplement de ma propre considération. Tout ce que vous avez à faire est de vous assurer que a à b sont des multiples de k, donc le code ressemble à ceci: Il est également plus facile d'écrire avec la fonction any.
A.py
k=int(input())
a,b=map(int,input().split())
for i in range(a,b+1):
if i%k==0:
print("OK")
break
else:
print("NG")
Problème B
Répétez l'opération de multiplication par 1,01 et de dévaluation jusqu'à ce qu'elle devienne X yen ou plus, et comptez le total des opérations.
B.py
import math
ans=0
x=int(input())
y=100
while y<x:
ans+=1
y=math.floor(1.01*y)
print(ans)
Problème C
Cette fois, ce sera un problème C grossier.
Premièrement, dès que vous le voyez, s'agit-il d'une Union Find pondérée? Cependant, cette considération est ** basée sur un algorithme **, donc cela ne devrait jamais être fait. Dans ce numéro, j'ai pu réaffirmer les bases (je veux être bâclé ...).
Aussi, à première vue, ce problème nécessite une recherche complète de $ M ^ {10} $ rues, mais la contrainte de $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M $ peut être assez serrée. Évidemment (vous pouvez le dire en expérimentant avec de petits N, M. ** J'ai négligé cette expérience pendant le concours. **), $ A_1, A_2,…, A_N $ est inférieur à $ M ^ {10} $ rues Vous pouvez vous en douter. Par conséquent, pour le moment, je vais essayer de le résoudre avec la politique de recherche complète. Vous pouvez découvrir le nombre de façons possibles en regardant Explication, mais je pense que c'est un peu difficile à considérer jusqu'à présent pendant le concours.
Ici, ** si vous pouvez sélectionner la politique de recherche complète **, le reste n'est pas si difficile. Puisque $ A_1, A_2,…, A_N $ peuvent être définis dans l'ordre à partir de l'avant, DFS peut être utilisé ici (vous pouvez créer des instructions for nested, mais ** beaucoup de fors comme ça. Si vous êtes susceptible d'avoir une instruction imbriquée **, vous pouvez facilement ** écrire un processus similaire dans DFS **).
Dans le cas de DFS, préparez un tableau (ou une chaîne de caractères ← décrite plus loin) qui a jusqu'à $ A_1, A_2,…, A_d $, et une fonction qui prend trois arguments, d et $ A_d $, et d arrive à N. Si c'est le cas, le score de la séquence de nombres est calculé, et si N n'est pas atteint, la valeur au-dessus de $ A_d $ et en dessous de M peut être le prochain $ A_ {d + 1} $, donc toutes sont des fonctions récursives. Appelez simplement l'affaire. À ce stade, il peut être plus facile de comprendre si vous enregistrez jusqu'à $ A_1, A_2,…, A_d $ sous forme de chaîne de caractères. En d'autres termes, le même résultat peut être obtenu en changeant $ 1 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M \ leqq 10 $ en $ 0 \ leqq A_1 \ leqq A_2 \ leqq… \ leqq A_N \ leqq M-1 \ leqq 9 $. Par conséquent, chaque numéro peut être unifié par un chiffre, et le code au moment de la récurrence devient plus facile à voir lorsqu'il est considéré comme une chaîne de caractères.
Aussi, après le concours, je l'ai découvert en regardant le tweet de maspy, mais en Python ** structure de données itérable x Il semble qu'il existe une fonction ** combinaisons_with_replacement qui permet de dupliquer des éléments et renvoie une sous-chaîne d'éléments de longueur r (le premier argument est x et le second argument est r). De plus, les combinaisons sont générées dans l'ordre lexical, de sorte que si la structure de données itérable d'origine est triée, les combinaisons peuvent être obtenues sous forme de taples triés. Par conséquent, dans ce problème, si vous spécifiez range (1, m + 1) '' pour x et `` n``` pour r, le tuple qui correspond au tableau (ou chaîne) généré par DFS sera Peut être généré. Je voudrais vérifier une fois les fonctions autour d'itertools comme celle-ci.
C.py
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
R=[range(i,m) for i in range(m)]
def dfs(s,d,l):
global n,m,Q,ans
if d==n:
ans_=0
for k in Q:
a,b,c,e=k
if int(s[b-1])-int(s[a-1])==c:
ans_+=e
ans=max(ans,ans_)
else:
for i in R[l]:
dfs(s+str(i),d+1,i)
dfs("",0,0)
print(ans)
C.py
from itertools import combinations_with_replacement
n,m,q=map(int,input().split())
Q=[list(map(int,input().split())) for i in range(q)]
ans=0
for s in combinations_with_replacement(range(1,m+1),n):
ans_=0
for k in Q:
a,b,c,d=k
if s[b-1]-s[a-1]==c:
ans_+=d
ans=max(ans_,ans)
print(ans)
Problème D
Personnellement, c'était facile, mais beaucoup de gens semblaient trouver cela difficile. Après tout, ** la première politique est importante **, je souhaite donc améliorer ma compréhension.
Premièrement, en considérant le cas où x est un multiple de B, il devient 0, et j'ai pensé que ** si le reste de B est petit, le résultat du calcul serait petit **. En dessous, si $ x = k \ fois B + l \ (0 \ leqq l \ leqq B-1)
De plus, l'hypothèse de $ 0 \ leqq l \ leqq B-1 $ et $ [\ frac {Al} {B}] $ augmente de façon monotone par rapport à $ l $ (au sens large), donc $ l = B-1 $ est le maximum. Sera. De plus, dans le cas de $ n \ leqq B-1 $, n est le maximum, donc la réponse que vous voulez est $ [\ frac {A \ times min (B-1, n)} {B}] $.
answerD.py
a,b,n=map(int,input().split())
print(a*min(b-1,n)//b)
J'ai joué un peu de golf codé. C'était le plus court.
answerD_shortest.py
a,b,n=map(int,input().split());print(a*min(b-1,n)//b)
E problème
Après avoir réfléchi au problème C pendant le concours, ** je le faisais avec une politique appropriée **, donc je ne pouvais pas bien diviser le cas quand n était pair. J'ai trouvé le tweet de yuma sur Twitter et j'ai pu AC par ma propre méthode, alors j'ai commencé à écrire un commentaire, mais Je n'ai pas été en mesure d'expliquer le modèle avec même n. </ font> Je pense que je vais bientôt écrire la suite de l'explication, mais pardonnez-moi s'il vous plaît. En outre, ceux énumérés dans le commentaire officiel sont brièvement expliqués.
Pour des problèmes de construction comme celui-ci, vous devez ** déplacer votre main en premier ** (expérimenter) pour trouver l'attribution de numéros au champ de bataille. Ensuite, à la suite de l'expérience, j'ai pensé que les combinaisons suivantes seraient pratiques et que n'importe quelle combinaison de M et N pouvait exister.
Cette combinaison semble bonne à première vue. Car, au début, les participants avec le numéro 1 se déplacent à la place du nombre M dans l'ordre (** vous ne toucherez pas le même participant pendant ce temps ), et lorsque le nombre augmente à NM, revenez dans l'ordre inverse ( ** Vous ne toucherez pas le même participant pendant ce temps **) C'est bien. Ainsi, une fois que je l'ai soumis, tous les cas de test de la seconde moitié sont devenus WA.
Personnellement, je pense que la politique d'ici était fausse. ** Si vous clarifiez le cas où la combinaison précédente ne tient pas **, alors ** vous pouvez modifier la combinaison ci-dessus afin qu'elle soit toujours valable **. Maintenant, considérons le cas où la combinaison ci-dessus ne tient pas. Ensuite, les considérations suivantes peuvent être faites.
Premièrement, lorsque la personne avec le numéro 1 est A et la personne avec le numéro N-M est B, Lorsque M est pair, vous combattrez B au moment où A devient le numéro M (indiqué en rouge sur la figure), alors ne combattez pas B lorsque A est le numéro N-M ou plus. De plus, lorsque B est le numéro M, A est le numéro N, donc lorsque A est le numéro N-M, B est le numéro 2N-M. Par conséquent, lorsque A devient le nombre N-M ou plus tard, il ne combat pas B lorsque A est impair, et ** N est impair **. Au contraire, lorsque M est impair, il ne combat pas B jusqu'à ce que A devienne le numéro M, il doit donc combattre B lorsque A devient le numéro N-M ou plus tard. De plus, lorsque A est le numéro NM, B est le numéro 2N-M, et lorsque A est le numéro NM ou plus tard, B se bat lorsque A est pair, ** N est impair *. Il devient *.
Par conséquent, la même chose peut être faite pour n'importe quelle personne (∵ ** n'utilisez que les cotes et les cotes pour juger du schéma de combat ou de ne pas se battre **), donc quand N est impair, n'importe qui peut faire la même combinaison On peut dire que vous ne jouerez pas contre le même participant. Par conséquent, je voudrais considérer le moment où le N restant est pair, mais à partir de là, c'est la porte du démon.
Trop de porte démoniaque! </ Font>
→ Je suis désolé, mais l'explication d'ici ne me suffit pas. Il serait grandement apprécié que vous puissiez le compléter avec des commentaires ou des demandes de modification.
De là, j'ai essayé d'expliquer la méthode décrite dans Explication officielle, mais je n'ai pas le temps de l'écrire, donc une explication légère. Je vais terminer avec.
Comme vous pouvez le voir à partir des deux modèles ci-dessus (le chiffre dans Explication officielle), ** la distance de la combinaison de nombres ** (Dans la première figure, 1 et 5 sont des distances de 4, 2 et 4 sont de 2, et ainsi de suite.) Vous pouvez voir qu'ils sont tous différents. Par conséquent, vous pouvez organiser n numéros et les prendre de sorte qu'ils aient tous des distances différentes ** ($ \ thererefore $ Si cette distance est différente, le même participant ne jouera pas plusieurs fois). Comme le montre la figure ci-dessus, si vous le divisez au milieu et que vous le récupérez de sorte que la distance soit paire sur le côté gauche et impaire sur le côté droit, vous pouvez voir que vous pouvez récupérer un ensemble de nombres avec des distances différentes sans gaspillage. Notez également que la distance maximum est $ [\ frac {n} {2}] $ ($ \ car $ maximum est supérieur à $ [\ frac {n} {2}] $ L'ensemble des nombres ne correspond pas au sujet, car certains peuvent sortir avec la même distance.)
… C'est une explication légère. Pour plus d'informations, veuillez demander dans les commentaires.
✳︎ Il a fallu quelques heures pour capturer à la fois Python et PyPy le plus court et le plus rapide (au 3 mai 2020). Surtout, je pense que la personne la plus petite a appliqué un excellent code à sa manière. Je joue avec, donc je ne vais pas expliquer le code, mais je pense que j'ai pu utiliser efficacement les opérations sur les bits.
answerE_bymyself.py
#Code de politique que j'ai élaboré pendant le concours
n,m=map(int,input().split())
if n%2==1:
for i in range(m):
print(i+1,n-i)
else:
for i in range(m):
if i<m/2:
print(i+1,n-i)
else:
print(i+1,n-i-1)
answerE_editorial.py
n,m=map(int,input().split())
if n%2==1:
l=n//2
for i in range(m):
if i%2==1:
print(i//2+1,l-i//2)
else:
print(l+i//2+1,n-i//2)
else:
l=n//2
for i in range(m):
if i%2==0:
print(i//2+1,l-i//2)
else:
print(l+i//2+2,n-i//2)
answerE_shortest.py
n,m=map(int,input().split())
for i in range(m):print(i+1,n-i-((i>=m/2)&~n))
answerE_fastest.py
def main():
n,m=map(int,input().split())
if n%2==1:
x=[f"{i+1} {n-i}" for i in range(m)]
print(" ".join(x))
else:
x=[f"{i+1} {n-i}" if i<m/2 else f"{i+1} {n-i-1}" for i in range(m)]
print(" ".join(x))
if __name__ == "__main__":
main()
Problème F
J'ai passé trop de temps sur d'autres sujets et il y a un concours aujourd'hui, donc je ne le passerai pas en revue une seule fois. Je l'examinerai à un autre moment.
Recommended Posts