[PYTHON] Examen du concours de programmation HHKB 2020
Les résultats de cette fois
Impressions de cette époque
C'était le deuxième meilleur joueur, mais je suis déçu car je ne vise pas ici. C'est bien de sauter le problème D et de passer au problème E, mais ** je suis déçu parce que le problème D aurait dû être résolu si je réfléchis bien **
Problème A
S'il est égal à Y, convertissez-le avec la méthode supérieure.
A.py
s,t=input(),input()
if s=="Y":
print(t.upper())
else:
print(t)
Problème B
J'étais impatient car je ne pouvais pas lire le texte de la question. En résumé, le problème est de trouver le nombre de carrés qui ne sont pas encombrés lorsque vous sélectionnez 2 carrés verticaux ou 2 carrés horizontaux.
Sélectionnez 2 carrés verticaux ou 2 carrés horizontaux. À ce stade, si vous y pensez inversé, vous pouvez considérer 2 cellules verticales comme 2 cellules horizontales, déterminez donc les 2 cellules horizontales de la matrice d'origine et les 2 cellules horizontales de la matrice inversée pour obtenir la somme.
B.py
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
for j in range(w):
t[j][i]=s[i][j]
ans=0
for i in range(h):
for j in range(w-1):
if s[i][j]=="." and s[i][j+1]==".":
ans+=1
for i in range(w):
for j in range(h-1):
if t[i][j]=="." and t[i][j+1]==".":
ans+=1
print(ans)
Problème C
C'est un problème de trouver $ mex $ qui apparaît souvent dans Kodofo. Le tableau $ check $ qui stocke le nombre qui apparaît jusqu'au $ i $ th et la solution au $ i $ th point (la valeur minimale parmi les nombres qui n'apparaissent pas) sont stockés dans $ mi $.
À ce stade, ** $ mi $ augmente de manière monotone **, donc quand $ check [mi]! = 0 $, incrémentez jusqu'à ce que $ mi $ soit trouvé, ce qui est $ check [mi] = 0 $, puis $ check. Lorsque [mi] = 0 $, $ mi $ doit être affiché.
(Je ne pense pas que ce soit aussi simple, mais je suis surpris que beaucoup de gens passent par là.)
C.py
n=int(input())
p=list(map(int,input().split()))
check=[0]*200001
mi=0
for i in range(n):
check[p[i]]+=1
while True:
if check[mi]>0:
mi+=1
else:
break
print(mi)
Problème D
Tout d'abord, j'ai mal lu ** que je mettrais plusieurs carrés rouges et bleus **. Puisqu'il y a un carré rouge et un carré bleu, envisagez de trouver ** comment organiser l'autre quand l'un est fixe ** et de le trouver avec $ O (1) $ en transformant la formule. Considérons maintenant ** la fixation du carré rouge et le déplacement du carré bleu ** comme (un côté du carré rouge: A) $ \ geqq $ (un côté du carré bleu: B). À ce stade, on suppose que le coin inférieur gauche du carré rouge est à $ (i, j) \ (0 \ leqq i \ <N-A, 0 \ leqq i \ <N-A) $.
Ensuite, considérez le nombre de cas où un carré bleu est inclus dans les rectangles rouge, vert, jaune et bleu ci-dessus. De plus, si chacune des quatre ** parties qui se chevauchent contient un carré bleu **, vous devez le soustraire. Ici, la partie rectangulaire et la partie superposée sont chacune ** égales à la somme de la symétrie **, donc la réponse peut être obtenue en quadruplant le rectangle rouge suivant moins le rectangle bleu.
(1) À propos du rectangle rouge Compte tenu de la largeur du carré bleu et du carré bleu, $ B \ leqq i \ leqq N-A $ est valable. À ce stade, le nombre de carrés bleus inclus est
\begin{align}
&\sum_{i,j}(N-B-1)(i-B+1)\\
&=(N-B-1)\sum_{i,j}(i-B+1)\\
&=(N-B-1)\sum_{j}(\sum_{i}(i-B+1))\\
&=(N-B-1)\sum_{j}(1,2,…,N-A-B+1)\\
&=(N-B-1)\sum_{j}\frac{(N-A-B+1)(N-A-B+2)}{2}\\
&=(N-B-1)(N-A+1)\frac{(N-A-B+1)(N-A-B+2)}{2}\\
\end{align}
(2) À propos du rectangle bleu En plus de $ B \ leqq i \ leqq N-A $, $ B \ leqq j \ leqq N-A $ est également valable. À ce stade, le nombre de carrés bleus inclus est
\begin{align}
&\sum_{i,j}(j-B-1)(i-B+1)\\
&=\sum_{i}(i-B+1)\times \sum_{j}(j-B+1)\\
&=(\frac{(N-A-B+1)(N-A-B+2)}{2})^2\\
\end{align}
Le calcul ci-dessus dépend de $ (j-B-1), (i-B + 1) $ et ** $ i, j $ respectivement **, nous allons donc utiliser la séparation comme une somme. Notez que si l'un des termes contient $ i, j $, il ne peut pas être séparé.
Vous pouvez le trouver en quadruplant ce qui précède (1) moins (2). De plus, si vous utilisez Python, vous n'avez pas à vous soucier du débordement car il s'agit d'un entier de plusieurs longueurs, et trouvez enfin le reste divisé par 10 $ ^ 9 + 7 $.
D.py
mod=10**9+7
for _ in range(int(input())):
n,a,b=map(int,input().split())
if a<b:
a,b=b,a
x=(n-a-b+1)*(n-a-b+2)//2*(n-a+1)*(n-b+1)*4
y=((n-a-b+1)*(n-a-b+2)//2)**2*4
if a+b>n:
print(0)
continue
print((x-y)%mod)
E problème
Je suis content d'avoir pu passer de D immédiatement à la production réelle. Je suis content que la mise en œuvre ait été simple sans causer trop de bogues.
Tout d'abord, puisqu'il s'agit de la somme, considérez combien de fois le carré éclairé apparaît dans la rue $ 2 ^ k $ ** (** faites attention au nombre d'éléments! **). Ici, lorsque l'éclairage est placé sur un certain carré, le carré éclairé devient un carré continu et épuré à partir de ce carré. Ici, lorsque vous illuminez certains carrés, vous pouvez éclairer les carrés avec plusieurs lumières. À ce stade, il est nécessaire d'ajouter la cellule à la solution en une seule fois, j'ai donc supposé que ** la cellule était éclairée par $ x $ lumières ** et j'ai réfléchi au nombre de fois où la cellule apparaîtrait comme la cellule éclairée. .. Ici, si l'une des lumières ** $ x $ est allumée, ce carré sera illuminé **. Par conséquent, il existe $ 2 ^ k $ façons de choisir les carrés pour mettre la preuve, et $ 2 ^ {kx} $ façons de ne choisir aucun des $ x $ carrés, donc au moins un choix est $ 2 ^ k-2 ^ {kx} $ street ($ \ parce que $ principe d'encapsulation).
Par conséquent, la somme peut être calculée par $ O (HW) $ en calculant le nombre de carrés éclairés par chaque carré et en effectuant le calcul pré-carré. Ici, ** les cellules qui éclairent une certaine cellule partagent une ligne ou une colonne **, et il en va de même si la matrice est transposée, alors combien de cellules ** qui partagent une ligne ** sont éclairées? Réfléchissons d'abord.
Ici, s'il y a $ y $ cellules épurées consécutives dans une ligne, ** le nombre de cellules qui sont partagées et illuminées pour n'importe quelle cellule contenue sera $ y $ **. .. Par conséquent, utilisez la fonction itertools groupby (reference) pour créer une masse continue et épurée. En résumant, $ O (HW) $ peut être utilisé pour trouver $ y $ dans chaque cellule. De même, découvrez combien de carrés qui partagent une colonne sont illuminés et soustrayez 1 de la valeur ajoutée à $ y $ ($ \ car $ ** compte ce carré deux fois **). Oui) Vous pouvez trouver $ x $ dans chaque cellule.
E.py
mod=10**9+7
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
k=0
for i in range(h):
for j in range(w):
if s[i][j]==".":
k+=1
t=[["" for j in range(h)] for i in range(w)]
for i in range(h):
for j in range(w):
t[j][i]=s[i][j]
po=[0]*(k+1)
po[0]=1
for i in range(1,k+1):
po[i]=po[i-1]*2
po[i]%=mod
#La partie reliée par une ligne
from itertools import groupby
check=[[0]*w for i in range(h)]
for i in range(h):
now=0
for key,group in groupby(s[i]):
l=len(list(group))
if key=="#":
now+=l
else:
for j in range(now,now+l):
check[i][j]+=l
now+=l
for i in range(w):
now=0
for key,group in groupby(t[i]):
l=len(list(group))
if key=="#":
now+=l
else:
for j in range(now,now+l):
check[j][i]+=l
now+=l
ans=0
for i in range(h):
for j in range(w):
#print(k,k-check[i][j])
if check[i][j]!=0:
ans+=(po[k]-po[k-check[i][j]+1])
ans%=mod
print(ans)
Problème F
Je vais sauter cette fois.
Recommended Posts