[PYTHON] AtCoder Beginner Contest 080 Revue des questions précédentes

Temps requis

Impressions

Je sens que tout a été résolu correctement pour la première fois depuis longtemps. Cependant, comme le problème D a été trompé par la forme et a décidé de l'algorithme, je le regrette.

Problème A

Sortez simplement le plus petit

answerA.py

n,a,b=map(int,input().split())
print(min(a*n,b))

Problème B

Pour trouver la somme de chaque chiffre, divisez par 10 dans l'instruction while.

answerB.py

n=int(input())
k=n
f=0
while k!=0:
    f+=(k%10)
    k//=10
print("Yes" if n%f==0 else "No")

Problème C

Le problème d'un tel modèle donne envie de douter de DP etc., mais même si vous décidez à l'avance d'ouvrir ou non dans chaque fuseau horaire et de faire une recherche complète, au plus $ 2 ^ {10} -1 = 1023 $ (toujours une fois) (Parce qu'il est ouvert), donc je sais que je serai à temps. Pour voir ce qu'il advient de vos bénéfices lorsque vous décidez d'ouvrir ou non dans chaque fuseau horaire, vérifiez si n magasins du quartier commerçant sont ouverts dans le fuseau horaire que vous avez décidé d'ouvrir (jusqu'à 10). Puisqu'il est enregistré, il est O (n), et comme il calcule le profit correspondant au nombre de magasins vérifiés, il est O (n), vous pouvez donc voir qu'il est à temps pour le montant du calcul.

answerC.py

n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
ma=-10000000000000
for i in range(1,2**10):
    check=[0]*n
    for j in range(10):
        if (i>>j) & 1:
            for k in range(n):
                check[k]+=f[k][j]
    ma_sub=0
    for i in range(n):
        ma_sub+=p[i][check[i]]
    ma=max(ma,ma_sub)
print(ma)

Problème D

Au début, je doutais de la planification des sections parce que je pensais au chevauchement des sections, mais il n'est pas approprié pour la planification des sections de réfléchir au ** combien de sections se chevauchent ** (il convient de choisir de manière à ce qu'elles ne se chevauchent pas). J'ai pensé. En conséquence, ce changement de politique a réussi. En fin de compte, il a été possible de penser à ** combien de sections sont couvertes au maximum **, donc en d'autres termes, ** combien de programmes télévisés sont diffusés à chaque fois **. Après cela, il est efficace d'utiliser la méthode imos lors de la mise à jour de la valeur de ** intervalle **, j'ai donc utilisé imos. De plus, dans ce problème, ** la même chaîne peut être enregistrée en continu même si les heures de fin et de début d'un certain programme TV sont les mêmes **, assurez-vous donc d'utiliser la méthode imos pour chaque chaîne et lors du comptage du nombre final. J'ai essayé de calculer tous ensemble.

answerD.py

n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))