AtCoderBeginnerContest166 Review & Summary (second semestre)

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

D problème je déteste la factorisation

É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

E problème Ce message s'autodétruit dans 5s

É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.

Problème F Jeu des trois variables

É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

AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
Résumé du didacticiel Django Girls Première moitié