[PYTHON] Critique du concours AtCoder Débutant 180

Les résultats de cette fois

Impressions de cette époque

C'était une bonne note. Ce F était difficile et je n'avais pas l'impression de pouvoir le résoudre du tout. Je l'ai compris en regardant la réponse, mais il semble qu'elle ne peut pas être appliquée, donc je ne vais pas procéder à une résolution ascendante cette fois. J'ai réalisé que le problème E était typique. C'était un schéma typique que je n'avais jamais résolu auparavant, alors j'aimerais le revoir souvent.

Problème A

Je pensais que le problème n'était pas établi lorsque $ n <a $, mais $ n \ geqq a $ tient à cause de la contrainte.

A.py

n,a,b=map(int,input().split())
print(n-a+b)

Problème B

Mettez-le simplement en œuvre conformément à l'énoncé du problème. En fait, il n'y a aucun problème si vous convertissez l'entrée en valeur absolue telle quelle.

B.py

n=input()
x=list(map(lambda y:abs(int(y)),input().split()))
print(sum(x),sum([i*i for i in x])**0.5,max(x))

Problème C

J'ai mal interprété que c'était correct d'avoir des choux à la crème supplémentaires lorsque je l'ai distribué, et j'ai mal compris que c'était un problème de trouver des candidats pour la valeur de $ [\ frac {n} {k}] $.

Tout ce que vous avez à faire est de lister les fractions au fur et à mesure qu'elles seront distribuées afin qu'il n'y ait pas d'excédent.

C.py

def m():
    n=int(input())
    d=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            d+=[i]
            if i!=n//i:d+=[n//i]
    d.sort()
    return d
for i in m():print(i)

Problème D

Il s'agit simplement de classer calmement les cas, mais j'ai émis 2WA ... En conséquence, c'était décevant car c'était une performance bleue si 1WA suffisait.

Choisissez entre multiplier A et ajouter B. Le premier et le second font le meilleur choix, mais ** une fois que le premier n'est plus optimal, le second est toujours le meilleur après cela **. Vous pouvez également le voir en comparant le montant de la variation entre $ \ fois A $ et $ + B $.

Par conséquent, considérons le cas où il est préférable de multiplier $ x $ par A (lorsque la valeur de $ x $ multipliée par A est inférieure à la valeur de $ \ leftrightarrow $$ x $ plus B). À ce stade, il est naturel d'utiliser $ x \ times A \ leqq x + B $ dans l'expression conditionnelle de comparaison, mais il est également nécessaire de définir la condition ** de manière à satisfaire ** $ x \ <y $. Si vous l'implémentez soigneusement à l'intérieur de la boucle, le calcul de l'ajout de $ B $ après la sortie de la boucle ne nécessitera que $ ans + [\ frac {y-x-1} {b}] $.

D.py

x,y,a,b=map(int,input().split())
ans=0
while True:
    if x*a<=x+b:
        if x*a>=y:
            print(ans)
            exit()
        else:
            ans+=1
            x*=a
    else:
        #D'ici+
        #x*a>x+b
        #x<y
        break
print(ans+(y-x-1)//b)

E problème

Il semble que ce soit un problème typique, mais quand je le regarde après l'avoir résolu, je pense que c'est aussi le cas.

Le processus d'examen du concours est décrit ci-dessous. De plus, les coordonnées tridimensionnelles du sujet doivent être étirées sur l'axe $ x $, l'axe $ y $ et l'axe $ z $.

Tout d'abord, le maximum est $ n = 17 $, donc ** $ n! $ N'est pas à temps **. Je n'ai pas pu essayer de l'appliquer car le problème le plus courant avec $ 2 ^ n $ est une énumération à moitié complète. Ensuite, j'ai réfléchi à ** si cela pouvait être bien décidé en regardant la formule de coût **, mais lors de la connexion des deux sommets, il semble préférable de se connecter de la plus grande coordonnée $ z $ à la plus petite Je sais seulement. Ici, si vous regardez la contrainte, vous remarquerez qu'elle passe ** si c'est bitDP car c'est ** $ 2 ^ {17} $. Par conséquent, compte tenu du DP qui gère l'ensemble des villes arrivées, c'est comme suit.

$ dp [i] [j]: = $ (somme des coûts minimaux lorsque les villes contenues dans le sous-ensemble $ i $ ont été atteintes et sont dans la ville $ j $)

** Si vous voulez représenter l'ensemble des villes que vous avez atteint en bits, vous pouvez y penser tant que vous vous souvenez que ce sera bitDP **. Ce numéro est également une variante du fameux TSP (Circular Salesman Problem).

Ici, l'ordre des transitions DP doit être le suivant dans l'ordre des petits états $ i $ (entier) ** (✳︎). L'initialisation est effectuée uniquement pour $ dp [1] [0] = 1 $. (Considérez la transition vers la ville $ k $ lorsque vous êtes dans la ville $ j $ pour un certain $ i $. Vous n'avez pas à penser lorsque $ j = k $. De plus, $ dist [j] [k] $ est $ Le coût du passage de j $ à $ k $.)

dp[i|(1\<\

D'après ce qui précède, $ dp [1 \ <\ <n-1] [0] $ est la réponse car ** revient finalement à la ville 1.

(✳︎)… Je vais prouver que vous pouvez le faire par ordre croissant. En d'autres termes, il est montré ici que toute forme de mouvement peut être exprimée.

En passant de l'état de $ i $ à $ j $ → $ k $, l'état devient $ i $ → $ i | (1 \ <\ <k) $. En d'autres termes, en prenant ** bit à bit ou, l'état (représentant un entier) est non décroissant **. Par conséquent, si vous effectuez une transition (mise à jour) ** dans l'ordre croissant de l'état ** (indicateur représentant), vous pouvez exprimer toutes les méthodes de mouvement. De plus, lorsque la transition est vue comme un côté orienté avec chaque état $ i $ comme sommet, elle peut être mise à jour à partir du plus petit ** $ i $ if ** trié topologiquement, et cela est vrai pour bitDP. Je pense que cela peut être interprété. De plus, vous pouvez comprendre que l'entier qui représente l'état dans la transition n'est pas décroissant, car $ j $ plus petit que ** $ i $ n'inclut pas $ i $ **.

[Mis à jour le 18 octobre 2020]

La discussion ci-dessus utilise implicitement ** qu'il est plus court de ne pas traverser une autre ville lors du déplacement d'une ville à une autre **, mais c'est parce que l'inégalité du triangle ** est une formule de coût. Cela peut être démontré par le fait qu'il tient **. De plus, s'il est plus court de passer par d'autres villes, vous pouvez ** d'abord trouver le coût entre toutes les villes avec Worshall Floyd, puis ** faire le même bitDP.

E.py

n=int(input())
tos=[list(map(int,input().split())) for i in range(n)]
#Coût de 1 à j
def co(i,j):
    return abs(i[0]-j[0])+abs(i[1]-j[1])+max(0,j[2]-i[2])
inf=10**12
dp=[[inf for j in range(n)] for i in range(1<<n)]
dp[1][0]=0
for i in range(1,1<<n):
    for j in range(n):
        #Ne reviens jamais à moi
        for k in range(n):
            if j==k:continue
            dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+co(tos[j],tos[k]))
ans=inf
for i in range(n):
    ans=min(ans,dp[(1<<n)-1][i]+co(tos[i],tos[0]))
print(ans)

Problème F

Je ne résoudrai pas cette fois.