AtCoderBeginnerContest183 Review & Résumé

AtCoder ABC183 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 183 qui a eu lieu le 15/11/2020 (dimanche), en commençant par le problème A et en tenant compte des considérations. 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

Problème A ReLU

Énoncé du problème La fonction ReLU est définie comme suit. image.png Étant donné l'entier $ x $, trouvez $ ReLU (x) $.

Fonction ReLU familière avec la fonction d'activation.

abc183a.py


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

Problème B Billard

Énoncé du problème Takahashi fait du billard sur le plan de dimension $ 2 $. L'axe $ x $ est un mur, et lorsque vous frappez la sphère, la sphère rebondit de sorte que l'angle d'incidence et l'angle de réflexion soient égaux. Maintenant la balle de Takahashi est en $ (S_x, S_y) $. Lorsque vous frappez une sphère à une certaine coordonnée, la sphère roule linéairement vers cette coordonnée. Après avoir reflété exactement la sphère $ 1 $ sur l'axe $ x $, où devrions-nous viser sur l'axe $ x $ pour passer $ (G_x, G_y) $?

Puisque la contrainte était $ 0 <S_y, G_y \ leq 10 ^ 6 $, nous avons mis $ G_y $ à négatif et l'avons résolu comme l'intersection de l'équation de la ligne droite et de l'axe $ x $.

x = S_x - S_y × (G_x - S_x) ÷ (G_y - S_y)

abc183b.py


s_x, s_y, g_x, g_y = map(int, input().split())
g_y = -g_y
print(s_x - s_y * (g_x - s_x) / (g_y - s_y))

C problème Voyage

Énoncé du problème Il y a des villes $ N $. Il faut $ T_ {i, j} $ pour passer de la ville $ i $ à la ville $ j $. Combien d'itinéraires partent de la ville à 1 $, visitent toutes les villes exactement 1 $ chacune, puis reviennent à la ville à 1 $, avec un temps de trajet total de seulement $ K $? ??

Comme la contrainte est aussi petite que $ 2 \ leq N \ leq 8 $, j'ai pu la résoudre dans le délai d'exécution même si je cherchais tout, mais quand j'ai vu le problème pour la première fois, $ 1 \ to 2 \ to 3 \ to 4 \ to La route 1 $ et la route $ 1 \ à 4 \ à 3 \ à 2 \ à 1 $ ont le même temps de trajet total en raison de la contrainte de $ T_ {i, j} = T_ {j, i} $. , Je pensais que je pourrais réduire la quantité de calcul si j'utilisais une fonction récursive, donc il m'a fallu beaucoup de temps pour commencer à résoudre.

abc183c.py


import itertools
import numpy as np
n, k = map(int, input().split())
matrix = np.zeros((n, n), dtype=int) 
for i in range(n):
    x_list = list(map(int, input().split()))
    for j in range(n):
        matrix[i, j] = x_list[j]
no_list = range(1, n)
count = 0
for temp_list in itertools.permutations(no_list):
    no = 0
    total = 0
    for next_no in temp_list:
        total += matrix[no, next_no]
        no = next_no
    total += matrix[no, 0]
    if total == k:
        count += 1
print(count)

D problem chauffe-eau

Énoncé du problème Il existe un chauffe-eau à 1 $ qui peut fournir des litres d'eau chaude à la minute. Il y a des gens $ N $. La $ i $ ème personne prévoit d'utiliser $ P_i $ litres d'eau bouillie dans ce chauffe-eau à partir du moment $ S_i $ à $ T_i $ (en excluant juste le temps $ T_i $). L'eau chaude refroidit rapidement et ne peut pas être stockée. Est-il possible de fournir de l'eau chaude à tous comme prévu?

Pour une raison quelconque, je l'ai résolu avec dict pendant le concours, mais je peux aussi le résoudre avec list. En premier lieu, c'est du gaspillage et c'est regrettable car il n'est pas nécessaire de gérer séparément en augmentant et en diminuant.

abc183d.py


n, w = map(int, input().split())
start_dict = {}
end_dict = {}
for i in range(n):
    s, t, p = map(int, input().split())
    if s in start_dict:
        start_dict[s] += p
    else:
        start_dict[s] = p
    if t in end_dict:
        end_dict[t] += p
    else:
        end_dict[t] = p
now = 0
flag = 1
for i in range(2 * 100000):
    if i in start_dict:
        now += start_dict[i]
    if i in end_dict:
        now -= end_dict[i]
    if now > w:
        flag = 0
        break
if flag == 1:
    print("Yes")
else:
    print("No")

Code modifié en référence à l'explication.

abc183d.py


n, w = map(int, input().split())
a_list = [0] * 200001
for i in range(n):
    s, t, p = map(int, input().split())
    a_list[s] += p
    a_list[t] -= p
for i in range(1, 200001):
    a_list[i] += a_list[i - 1]
if max(a_list) > w:
    print("No")
else:
    print("Yes")

Le problème E s'est terminé sans sortir de "TLE". J'aimerais l'ajouter quand j'aurai le temps.

Merci d'avoir lu jusqu'à la fin.

Recommended Posts

AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
Résumé de Django
Résumé de python-pptx
Résumé Linux
Résumé Python
Résumé de Django
résumé pyenv
Résumé de la chaîne de caractères 1
résumé pytest
Résumé matplotlib
Examen des fonctions