[PYTHON] 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. É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.