AtCoder ABC166 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 166 qui a eu lieu le 2020-05-03 (dimanche), en commençant par le problème A et en tenant compte des considérations. La seconde moitié traite du problème DEF. Cliquez ici pour le premier semestre. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Afficher un ensemble d'entiers $ (A, B) $ qui satisfait $ A ^ 5 − B ^ 5 = X $. Cependant, pour un $ X $ donné, il y a une garantie qu'il y aura un ensemble d'entiers $ (A, B) $ qui satisfont la condition. Contraintes ・ $ 1 \ leq X \ leq 10 ^ 9 $ ・ $ X $ est un entier. ・ Il existe un ensemble d'entiers $ (A, B) $ qui satisfont les conditions.
Après avoir lu le problème, j'ai pensé que chaque $ X $ avait un ensemble d'entiers $ (A, B) $ qui satisfaisait la condition (trop peu ...). Même si je le saisis dans un programme qui implémente divers modèles de $ X $, il n'y avait pas de sortie, donc j'ai pensé que la plage de recherche n'était pas suffisante, donc je suis resté bloqué. Une fois le concours terminé, j'ai lu le commentaire, et j'ai pensé que c'était peut-être le cas, et lorsque j'ai soumis le programme implémenté, c'était "AC", donc j'aurais dû le soumettre ...
abc166d.py
x = int(input())
flag = 0
for a in range(-200, 201):
if flag == 1:
break
for b in range(-200, 201):
if a**5 - b**5 == x:
print(a, b)
flag = 1
break
Énoncé du problème En tant qu'agent talentueux du Royaume d'AtCoder, vous avez infiltré une partie de la salle des marchés pour empêcher que des informations top secrètes volées ne tombent entre les mains du Royaume d'Aldebaran. La fête compte des participants $ N $, chacun numéroté de 1 $ à $ N $. Le participant $ i $ mesure $ A_i $. Par interrogatoire préalable, vous savez que l'échange d'informations confidentielles est pour 2 $ de personnes qui remplissent les conditions suivantes: ・ La valeur absolue de la différence des nombres détenus par 2 $ personnes est égale à la somme des hauteurs de 2 $ personnes. Il existe $ \ frac {N (N − 1)} {2} $ façons de sélectionner $ 2 $ participants parmi $ N $ participants et de les jumeler, mais la paire qui remplit les conditions ci-dessus est Combien de façons existe-t-il? De plus, vous ne savez pas quel est le contenu des informations confidentielles.
Quand j'ai participé au concours, j'étais coincé avec le problème D et je n'ai pas pu résoudre le problème E parce que je n'avais pas beaucoup de temps, mais je veux être en mesure de résoudre ce niveau de problème. J'ai été conscient du "problème E problème F = problème difficile", et il est difficile de le résoudre pendant le concours. J'ai implémenté ce qui est écrit dans l'article de commentaire et j'ai obtenu "AC" en toute sécurité avec le code suivant.
abc166e.py
n = int(input())
a_list = list(map(int, input().split()))
l_dict = {}
ans = 0
for i in range(0, n):
a = a_list[i]
ri = i - a
if ri in l_dict:
ans += l_dict[ri]
li = i + a
if li in l_dict:
l_dict[li] += 1
else:
l_dict[li] = 1
print(ans)
J'étais déconcerté par l'expression de la valeur absolue de la différence entre les nombres de personnes à 2 $. Si vous y réfléchissez bien, vous pouvez ajouter une condition de $ i <j $ lorsque vous choisissez deux personnes. Lorsqu'elle est négative, il semble difficile de traiter la valeur absolue. Quand j'y pensais, la perte était confirmée, donc je ne veux pas penser que c'est difficile.
Énoncé du problème Dans un jeu, il y a des variables $ 3 $, représentées respectivement par $ A, B et C $. Au fur et à mesure que le jeu progresse, vous serez obligé de faire des choix $ N $. Chaque sélection est indiquée par la chaîne $ s_i $, lorsque $ s_i $ est "AB", ajoutez $ 1 $ à $ A $ ou $ B $ et soustrayez $ 1 $ de l'autre, "AC" Quand, ajoutez $ 1 $ à $ A $ ou $ C $ et soustrayez $ 1 $ de l'autre, et quand "BC", ajoutez $ 1 $ à $ B $ ou $ C $ et l'autre Signifie de soustraire 1 $ de. Ni $ A, B, C $ ne peuvent être négatifs après une sélection. Déterminez s'il est possible de terminer toutes les sélections $ N $ fois tout en satisfaisant cette condition, et si oui, indiquez une de ces méthodes de sélection.
J'ai lu le commentaire et je viens de mettre en œuvre ce qui était écrit. Il semble difficile de remarquer que vous devez faire attention au traitement uniquement lorsque $ A + B + C = 2 $ car il n'y a pas d'exemple d'entrée. Je veux pouvoir résoudre ces problèmes pendant le concours.
abc166f.py
def check(s):
if dict_x[s[0]] == 0 and dict_x[s[1]] == 0:
return "NOT"
elif dict_x[s[0]] > 0 and dict_x[s[1]] == 0:
return s[1]
elif dict_x[s[0]] == 0 and dict_x[s[1]] > 0:
return s[0]
elif dict_x[s[0]] == 1 and dict_x[s[1]] == 1:
return "EVEN"
else:
if dict_x[s[0]] > dict_x[s[1]]:
return s[1]
else:
return s[0]
def update(s, mozi):
if s[1] == mozi:
dict_x[s[0]] -= 1
dict_x[s[1]] += 1
else:
dict_x[s[0]] += 1
dict_x[s[1]] -= 1
n, a, b, c = map(int, input().split())
dict_x = {"A": a, "B": b, "C": c}
s_list = []
ans_list = []
flag = 1
for i in range(0, n):
s = input()
s_list.append(s)
if a + b + c == 0:
flag = 0
elif a + b + c == 1:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
else:
ans_list.append(x)
update(s, x)
elif a + b + c == 2:
i = 0
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
if i == len(s_list) - 1:
ans_list.append(s[0])
update(s, x)
elif s == s_list[i + 1]:
ans_list.append(s[0])
update(s, x)
else:
if s[0] in s_list[i + 1]:
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(s[1])
update(s, s[1])
else:
ans_list.append(x)
update(s, x)
i += 1
else:
for s in s_list:
x = check(s)
if x == "NOT":
flag = 0
break
elif x == "EVEN":
ans_list.append(s[0])
update(s, s[0])
else:
ans_list.append(x)
update(s, x)
if flag == 1:
print("Yes")
for ans in ans_list:
print(ans)
else:
print("No")
Quand je passe en revue le problème F et le code que j'ai écrit moi-même, je me rends compte qu'il y a encore beaucoup de gaspillage. Merci d'avoir lu la seconde moitié jusqu'à la fin.
Recommended Posts