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

Temps requis

Impressions

Je l'ai résolu avec ABC088 que je donnerai en même temps. C'est en fait 70 minutes, mais j'étais content parce que j'ai pu résoudre les deux concours en 120 minutes au total. Le problème D était bien plus qu'un casse-tête et était similaire au problème AGC que j'avais résolu auparavant, donc je pouvais le trouver.

Problème A

J'ai mis un peu de temps à penser que le billet illimité ne pouvait pas être moins cher que le billet régulier.

answerA1.py

a,b,c,d=[int(input()) for i in range(4)]
print(min(a,b)+min(c,d))

Problème B

Au lieu de compter un par un, nous déterminerons si les participants mangent du chocolat chaque jour. Puisque nous mangeons $ 1, A_i + 1,2 A_i + 1,… $, nous devrions juger si le reste divisé par $ A_i $ est de 1 jour, mais seulement lorsque A_i vaut 1, le reste devient 0. Par conséquent, vous devez être prudent.

answerB.py

n=int(input())
d,x=map(int,input().split())
a=[int(input()) for i in range(n)]
ans=0
for i in range(1,d+1):
    for j in range(n):
        if a[j]==1:
            ans+=(i%a[j]==0)
        else:
            ans+=(i%a[j]==1)
print(ans+x)

Problème C

Je ne l'ai pas remarqué pendant le concours, mais il est facile de penser à ajouter $ A_0 = 0 $ et $ A_ {n + 1} = 0 $ à l'entrée $ A_1, A_2,…, A_n $ **. Ici, comme chaque site touristique est annulé un par un, j'ai pensé qu'il serait préférable de considérer la différence lorsqu'un site touristique était annulé par rapport au montant total du voyage initial. A ce moment, si le total lors de la visite de tous les sites touristiques dans l'ordre est de S, la formule suivante peut être établie. De plus, si vous ne visitez pas le i-ème site touristique d'ici, le montant total à ce moment-là fera la différence, compte tenu de la différence.S-|A_i-A_{i-1}|-|A_{i+1}-A_i|+|A_{i+1}-A_{i-1}|Sera. Si vous pensez à cela avec i = 1 ~ n, vous pouvez trouver la réponse.

answerC.py

n=int(input())
a=list(map(int,input().split()))
base=0
for i in range(n+1):
    if i==0:
        base+=abs(a[0])
    elif i==n:
        base+=abs(a[n-1])
    else:
        base+=abs(a[i]-a[i-1])
ans=[]
for i in range(n):
    if i==0:
        ans.append(base+abs(a[1])-abs(a[0])-abs(a[1]-a[0]))
    elif i==n-1:
        ans.append(base+abs(a[n-2])-abs(a[n-1])-abs(a[n-2]-a[n-1]))
    else:
        ans.append(base+abs(a[i+1]-a[i-1])-abs(a[i+1]-a[i])-abs(a[i]-a[i-1]))
for i in range(n):
    print(ans[i])

answerC_better.py

n=int(input())
a=list(map(int,input().split()))
b=[0]
b.extend(a)
b.append(0)
a=b
base=0
for i in range(n+1):
    base+=abs(a[i+1]-a[i])
ans=[]
for i in range(1,n+1):
    ans.append(base+abs(a[i+1]-a[i-1])-abs(a[i+1]-a[i])-abs(a[i]-a[i-1]))
for i in range(n):
    print(ans[i])

Problème D

Puisqu'une est sortie, il n'y a que ** pour trouver celle qui vous convient **. Ce genre de problème survient souvent dans AGC, mais si vous ne clarifiez pas ce que vous voulez faire, vous risquez d'entrer dans le labyrinthe. Tout d'abord, comme il y avait deux variables A et B dans ce problème, j'ai essayé de définir A ou B sur 0. Cependant, ** si l'un est 0, le reste sera connecté **, donc j'ai pensé que ce serait mieux s'il n'y avait pas de différence entre A et B. Par conséquent, afin d'éliminer la différence entre A et B, j'ai décidé de le diviser en ** petites structures qui peuvent ajuster librement la différence **. De plus, à ce moment-là, je pensais qu'il serait plus facile de créer une grille qui me convenait si je ** faisais la grille aussi large que possible et rendais un composant de connexion aussi petit que possible **. La première chose qui m'est venue à l'esprit était une combinaison des structures minimales suivantes.

J'ai essayé de créer une structure qui satisfait A et B en ** combinant les structures ci-dessus afin que les motifs inverses soient adjacents les uns aux autres **, mais cela n'a pas fonctionné. Cependant, lorsque le même modèle a été combiné lors de l'expérimentation de cette structure, il est devenu comme suit. Dans le cas de ce modèle, le composant de liaison blanc est de 0 à 50 au-dessus et le composant de liaison noir est de 1, j'ai donc pensé que ce serait très facile à régler. (Le motif inverse est de 0 à 50 pour le composant de lien noir et de 1 pour le composant de lien blanc)

Dans le modèle ci-dessus, il y a un peu de gaspillage de noir dans la partie où les petites structures se chevauchent, donc ** réduction des déchets et amélioration ** est la structure ci-dessous.

Ici, définissons la hauteur de la structure ci-dessus sur 100 et la largeur sur 50, et connectons les motifs inversés. Ensuite, pour la structure ci-dessus, le composant de liaison blanc est de 0 à 25 * 50 et le composant de liaison noir est de 1, et dans la structure de motif inversé, le composant de liaison blanc est 1 et le composant de liaison noir est de 0 à 25 * 50. Je vais. Par conséquent, une fois connecté, le composant de liaison blanc est de 1 à 25 * 50 et le composant de liaison noir est de 1 à 25 * 50. Par conséquent, si 1 <= A <= 500 et la limite de 1 <= B <= 500, la grille peut être créée par cette méthode.

answerD.py

a,b=map(int,input().split())
print("100 100")
a-=1
b-=1
for i in range(100):
    if i%2==0:
        print("."*50+"#"*50)
    else:
        for j in range(50):
            if j%2==0 or j==49:
                print(".",end="")
            else:
                if b>0:
                    print("#",end="")
                    b-=1
                else:
                    print(".",end="")
        for j in range(50):
            if j%2==0 or j==49:
                print("#",end="")
            else:
                if a>0:
                    print(".",end="")
                    a-=1
                else:
                    print("#",end="")
        print("")