[PYTHON] Critique du concours AtCoder Débutant 180

Les résultats de cette fois

スクリーンショット 2020-10-18 10.35.02.png

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.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
Critique du concours AtCoder
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes