Examen du concours AtCoder pour débutants 159, jusqu'à la question E (Python)

Ceci est un article de synthèse pour les débutants des professionnels de la compétition.

La solution que j'écris ici est écrite en regardant les commentaires et les soumissions d'autres personnes. Ce n'est peut-être pas ce que vous avez réellement soumis.

A - The Number of Even Pairs La question est de répondre au nombre de combinaisons de N boules avec des nombres pairs et M boules avec des nombres impairs, pour lesquels le total est pair.

La réponse est simplement de combiner la combinaison paire $ N (N-1) / 2 $ et la combinaison impaire $ M (M-1) / 2 $.

N, M = map(int, input().split())
print((N*(N-1))//2 + (M*(M-1))//2)

B - String Palindrome

C'est un problème de juger si la chaîne de caractères donnée est une "phrase circulaire qui combine deux phrases circulaires".

Il est jugé en tournant les quatre chaînes de caractères de la première moitié sur le côté gauche, la seconde moitié sur le côté gauche, la première moitié sur le côté droit et la seconde moitié sur le côté droit à 1/4 de la chaîne de caractères N.

s = input()
n = len(s)
for i in range((n-1+3)//4):# +3 est pour arrondir
    if not(s[i] == s[(n-1)//2-i-1] and s[(n+3)//2 + i-1] ==  s[-i-1] and s[i] == s[-i-1]):
        print('No')
        exit()
print('Yes')

Quand j'ai regardé d'autres réponses et explications, il y avait une manière plus propre d'écrire.

s = input()
n = len(s)
sl = s[:n//2]
sr = s[n//2+1:]
if sl == sr and sr ==  sr[::-1]:
    print('Yes')
else:
    print('No')

Divisez la chaîne de caractères entre gauche et droite, et si le côté droit sr '' est une récitation, le sl '' correspondant est également une récitation. Puisque sl et `` sr sont la même circonstance, c'est une circonstance même si les deux sont combinés. Seules deux conditions étaient requises.

C - Maximum Volume La hauteur, la largeur et la hauteur totales sont le problème de la réponse au volume maximum d'un L carré.

Lorsque height = width = height, le volume est le maximum, donc la longueur de chacun est $ L / 3 $. Cube simplement ceci.

L = int(input())
print((L/3)**3)

Je ne pourrais pas expliquer pourquoi c'est le maximum quand les longueurs des côtés correspondent, donc je vais écrire une explication mathématique pour le moment. Voici la formule de la moyenne synergique additive à trois variables. $ {a＋b+c\over 3}\geq (abc)^{1/3}$ Considérant que la hauteur est $ a $ et la largeur est $ b $ et $ c $, le volume du corps rectangulaire peut être calculé par $ abc . $ ({a＋b+c\over 3})^3\geq abc$$ Quand $ a = b = c $, l'égalité de cette formule est vraie, donc c'est le volume maximum.

D - Banned K

C'est un problème de penser au nombre de combinaisons pour sélectionner le même nombre parmi N boules avec des nombres écrits dessus, à l'exclusion des boules.

Tout d'abord, trouvez le nombre total de combinaisons $ S $ de toutes les boules. À partir de là, lorsqu'il y a des boules $ m $ avec le nombre $ n $, si vous retirez une boule avec le nombre $ n $, le total $ S $ sera réduit de $ m-1 $. Le nombre $ n $ est appliqué à chaque balle à retirer et à sortir.

import collections
N = int(input())
li = list(map(int, input().split()))
cn = collections.Counter(li)
sumC = sum([n*(n-1)//2 for n in cn.values()])
for k in range(N):
    print(sumC-cn[li[k]] + 1)

E - Dividing Chocolate

Il s'agit de répondre au nombre de fois à diviser pour que la quantité de chocolat blanc dans la plaque de chocolat soit inférieure à un certain niveau.

J'ai abandonné car je ne comprenais ni «l'idée d'exploration» ni «comment compter le nombre de chocolats blancs dans la scission».

J'ai vu le commentaire. Puisqu'il existe une spécification de plage étroite de $ H \ leq 10 $, la division horizontale peut être simple pour rechercher toutes les rues $ 2 ^ {H-1} $. Pour une recherche complète, utilisez ʻitertools.product () `pour créer une séquence complète de longueur H-1 contenant 0 ou 1. La recherche est OK avec cela.

Les chocolats qui sont divisés horizontalement sont stockés dans le tableau bidimensionnel «SW» comme un tableau unidimensionnel qui compte le nombre de chocolats blancs verticalement, et sont comptés à partir de la gauche. Si le nombre de chocolats dans une colonne dépasse le nombre spécifié «K», divisez les chocolats verticalement et ramenez le nombre à 0. Vous pouvez également compter le chocolat avec cela. Cependant, si la valeur de la matrice unidimensionnelle dépasse "K", il est impossible de diviser le chocolat plusieurs fois, donc la situation doit être refaite à partir de la division latérale.

Donc, le code ressemble à ceci:

import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)        

Cet article se termine par la question E pour le moment.