AtCoder Grand Contest 044 Critique

Impressions de cette époque

R Le problème était difficile (je ne pouvais pas analyser la quantité de calcul), et quand je me demandais comment le mettre en œuvre, le temps était écoulé. Peut-être que c'est correct de le faire passer, alors ce serait peut-être une bonne idée de le lancer. En conséquence, NoSub a été retiré ... Aussi, j'aimerais résoudre le problème B pendant mon temps libre cette semaine.

Problème A

Tout d'abord, je voudrais mentionner les méthodes envisagées lors du concours. Je pensais que +1 et -1 étaient pour l'ajustement, et je pensais qu'il pourrait être uniquement déterminé en ** répétant n'importe lequel de 2x, 3x et 5x. Par conséquent, je pensais que $ n $ devrait être considéré comme un numéro de base $ k $ ($ \ in $ {$ 2,3,5 $}), mais bien sûr, cela n'est pas décidé en se référant à l'échantillon (1 sans le remarquer) Il a fondu pendant plus d'une heure. Si vous vous précipitez, vous ne pourrez pas penser logiquement ...).

Quoi qu'il en soit, si vous ne pouvez pas le résoudre, prenez le courage de changer votre politique! !!

D'ailleurs, avant de m'en tenir à cette politique, j'ai essayé de penser à DP ** qui a noté le nombre de pièces requises de ** $ n $ à 0, et j'ai décidé que c'était impossible car le nombre d'éléments DP est de $ n $. C'était. ** Vous pouvez accélérer DP en utilisant un dictionnaire au lieu d'un tableau **, vous pouvez donc le résoudre par cette méthode (proche de) que vous avez trouvée ...

Maintenant, envisagez d'utiliser $ n $ pour +1, -1, ÷ 2, ÷ 3, ÷ 5 pour le rendre 0. Premièrement, lorsque vous connaissez le nombre de pièces dont vous avez besoin pour un certain $ l $, utilisez +1, -1, ÷ 2, ÷ 3, ÷ 5 pour réduire le nombre de destinations ** (** état) Limited ** est la base comme DP) Par exemple, supposons que vous vouliez faire $ l $ ÷ 5. Puisque $ l $% 5 = 0 est requis pour que cette réponse soit un entier, laissez $ l $ agir +1, -1 pour la rendre divisible par 5.

Ici, si vous appliquez +6 ou plus ou -6 ou moins à $ l $, vous utiliserez des pièces de 6 $ \ fois D $ ou plus à ce stade, mais dans ce cas, ** 6 ou plus ou -6 ou moins. Il est clair qu'il est plus efficace de le casser avant de le casser après l'avoir laissé fonctionner **. 11 → 10 → 1 ("-1" × 1 → "÷ 5" → "-1" × 1) est meilleur que (par exemple 11 → 5 → 1 ("-1" × 6 → "÷ 5")) Vous dépenserez moins de pièces.) (Vous pouvez probablement le prouver en faisant quelque chose de similaire, mais je vais l'omettre ici.)

De même, si le nombre de pièces nécessaires pour faire un certain l et le nombre à diviser $ k $ ($ \ in $ {$ 2,3,5 $}) sont déterminés, le nombre minimum de pièces sera obtenu. Dans une telle opération, déplacez-vous vers un multiple du nombre que vous souhaitez diviser (2,3,5) proche de ** $ l $ ** (← Notez qu'il y en a deux, il s'écrit * le plus proche * dans le code) Puis divisez et effectuez le calcul suivant. À ce moment, une structure récursive (structure fractale) apparaît, vous pouvez donc implémenter la récurrence, et vous pouvez implémenter le mémorial DFS (également considéré comme DP).

Notez également que dans certains cas, il est préférable de faire simplement -1 et de passer de $ l $ à $ 0 $ sans utiliser la division. (← Jusqu'à présent, si vous voulez viser 0 avec ** ÷ 2, ÷ 3, ÷ 5, vous ne pensez qu'à **, donc si vous voulez viser 0 avec ** -1, vous devez considérer ** Bien sûr.)

A.py


def dfs(n):
    global b,check,d
    #ttf est 235, cha est abc
    #2,3,Dans le cas de 5, chacun
    for ttf,cha in zip([2,3,5],b):
        #-En allant un par un
        if check[0]>check[n]+n*d:
            check[0]=check[n]+n*d

        #Au plus proche-Si tu fais
        x1,x2=n//ttf,n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

        #Au plus proche+Quand 1
        x1,x2=n//ttf+1,ttf-n%ttf
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

Recommended Posts

AtCoder Grand Contest 041 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
AtCoder Grand Contest 046 Critique
Critique du concours AtCoder Beginner Contest 152
Revue du concours régulier AtCoder 105
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
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
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
concours yukicoder 261 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
Concours Atcoder Débutant 153
concours yukicoder 263 avis
yukicoder contest 268 avis
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes