[PYTHON] Examen du concours de programmation HHKB 2020

Les résultats de cette fois

スクリーンショット 2020-10-11 10.32.48.png

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) $.

IMG_0686.jpg

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.

IMG_0685.jpg

(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

Examen du concours de programmation HHKB 2020
Examen du concours de programmation Keyence 2020
Notes pour le concours de programmation HHKB 2020
Rapport de participation au concours de programmation AtCoder HHKB 2020
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours de programmation Acing 2020
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Bilan 2019 du concours de programmation Sumitomo Mitsui Trust Bank
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
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
AtCoder Grand Contest 048 Critique
Critique du concours AtCoder Débutant 181
Après le "Concours de programmation Diverta 2019"
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
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
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
Concours de programmation Atcoder Acing Python
atcoder Review of Panasonic Programming Contest 2020, jusqu'à la question E (Python)
Rapport de participation au concours de programmation AtCoder Acing 2020
AtCoder Beginner Contest 066 Revoir les questions précédentes
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
AtCoder Beginner Contest 102 Revue des questions précédentes
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 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes