yukicoder contest 268 avis

résultat

スクリーンショット 2020-10-03 11.47.56.png

Impressions

Je pense que le mouvement minimum a été fait. Je pense que c'était bien de pouvoir lire le problème D sans abandonner. J'ai pu comprendre les problèmes B et C en regardant les réponses, mais je vais sauter cette fois parce que c'était une solution qui semble difficile à apprendre.

Problème A

Normalement, j'aimerais considérer DP pour un tel problème, mais c'est difficile car $ n $ vaut au plus 10 $ ^ {18} $. Par conséquent, nous allons mener l'expérience en pensant qu'elle peut avoir une sorte de règle **.

De plus, quand aux coordonnées $ x $, $ x + 1 $ et $ x + 6 $ sont tous les deux un sur-ensemble de jeu, les deux $ x + 2 $ et $ x + 5 $ sont un sur-ensemble de jeu, $ x + 3 Si $ et $ x + 4 $ sont tous les deux un sur-ensemble de jeu, alors ce $ x $ est également un sur-ensemble de jeu. Par conséquent, si vous regardez le sur-volume de jeu ci-dessus, ** le sur-volume de jeu augmentera dans l'ordre **. ** Expérimentez pour réfléchir à la façon d'augmenter la masse excessive du jeu ** et la figure ci-dessous.

IMG_0672.jpg

Si vous l'écrivez comme ci-dessus, lorsqu'il y a un ensemble de surmasse de jeu, les cases qui sont ** 9 ou plus de la plus petite surasse de jeu (✳︎) de ce groupe seront toujours la surasse de jeu **. Par conséquent, lorsque le carré de (✳︎) existe aux coordonnées de 10 ou plus, le jeu est terminé. Par conséquent, s'il y a un carré (✳︎), No est sorti et sort. Aussi, pour déterminer l'existence d'un ensemble de surmasse de jeu, préparez une structure d'ensemble «b» qui gère le sur-ensemble de jeu, et dans l'ordre à partir de la plus grande masse de jeu $ x $, $ x + 1, x + 3, x + 5 Découvrez si l'un des $ est inclus dans le $ b $.

Ensuite, lorsque des carrés ** (squ) existent à des coordonnées de 9 ou moins **, recherchez le carré sur lequel le jeu est terminé par le carré 9 → 1, et les nouveaux jeux créés sont de l'ordre de $ b $. Tout ce que vous avez à faire est de le stocker et de déterminer finalement si $ b $ contient 1.

A.py


n,k=map(int,input().split())
a=list(map(int,input().split()))
b=set(a)
for i in range(k-1,-1,-1):
    if a[i]<=9:
        break
    else:
        if a[i]+1 in b:
            print("No")
            exit()
        if a[i]+3 in b:
            print("No")
            exit()
        if a[i]+5 in b:
            print("No")
            exit()
for j in range(9,0,-1):
    if j in b:
        if j+1 in b:
            if j-3>=1:
                b.add(j-3)
        if j+3 in b:
            if j-2>=1:
                b.add(j-2)
        if j+5 in b:
            if j-1>=1:
                b.add(j-1)
if 1 in b:
    print("No")
    exit()
print("Yes")

Problème B, C

Je vais sauter cette fois.

Problème D

Je pense que c'était le problème le plus simple cette fois.

Les scores peuvent être ** calculés pour chaque bit ** car il n'y a que des opérations et au niveau du bit ou et du bit. De plus, il n'y a que deux valeurs initiales pour chaque bit, 0 ou 1, et si vous ** pré-calculez le score pour chaque bit **, vous ne pouvez voir tous les bits que lorsque la valeur initiale est donnée ** Vous pouvez le trouver sur. Par conséquent, le tableau à enregistrer dans le pré-calcul est défini comme check et $ check [i] [j]: = $ (score lorsque la valeur initiale du bit $ i $ est $ j $, mais $ j = 0,1 $) (✳︎). Nous envisagerons de le demander ci-dessous.

Pensez maintenant à calculer le score en regardant le bit $ i $ et en regardant $ a \ _i $ dans l'ordre lorsque sa valeur initiale est $ k $. De plus, l'entier que j'ai selon l'énoncé du problème est $ x $ (bien sûr, $ x = k $ au début). Et quand vous regardez le $ j $ e entier (le bit $ i $ est représenté par $ a \ _ {ji} $), vous avez l'entier $ x $ (mais la valeur du bit $ i $) Étant donné que l'opération à effectuer est soit $ et $ soit $ ou $. À ce stade, le changement de $ x $ et le changement de $ chèque [i] [k] $ sont indiqués dans le tableau ci-dessous.

IMG_0673.jpg

En créant un tableau comme ci-dessus **, vous pouvez saisir visuellement $ x $ et le score **, et vous pouvez simplement faire une boucle autour des variables $ i, k, j $. .. De plus, si vous avez $ check [i] [j] $, vous pouvez facilement calculer la requête simplement en ajoutant et en multipliant.

(✳︎)… Pour être exact, $ check [i] [j] \ times 2 ^ i $ est le score pour ce bit.

D.py


n,q=map(int,input().split())
a=list(map(int,input().split()))
check=[[0,0] for i in range(32)]
s=list(map(int,input()))
for i in range(32):
    #Si l'état initial est 0 ou 1
    for k in range(2):
        x=k
        for j in range(n):
            if (a[j]>>i)&1:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
                else:
                    if x==0:
                        check[i][k]+=1
                        x=1
                    else:
                        check[i][k]+=0
                        x=1
            else:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=1
                        x=0
                else:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
#print(check)
t=list(map(int,input().split()))
for _ in range(q):
    z=t[_]
    ans=0
    for i in range(32):
        ans+=(check[i][(z>>i)&1]*(2**i))
        #print(ans)
    print(ans)

Après le problème E

Je vais sauter cette fois.

Recommended Posts

concours yukicoder 264 avis
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
yukicoder contest 265 Record de participation
Revue du concours régulier AtCoder 105
concours yukicoder 266 Record de participation
yukicoder contest 263 Record de participation
concours yukicoder 243 Record de participation
record de 256 entrées
yukicoder contest 273 Record de participation
Examen du concours de programmation Keyence 2020
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
Critique du concours AtCoder
concours yukicoder 249 Record de participation
concours yukicoder 271 Record de participation
AtCoder Grand Contest 048 Critique
record de participation au concours 267 de yukicoder
Critique du concours AtCoder Débutant 181
Concours yukicoder 251 Record de participation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder pour débutant 177
record du concours 264 de yukicoder
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
Revue du concours de programmation NOMURA 2020
AtCoder Grand Contest 044 Critique
yukicoder contest 245 record d'inscription
yukicoder contest 257 Record de participation
record de participation au concours yukicoder 250
Concours yukicoder 254 Record de participation
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
yukicoder contest 246 Record de participation
concours yukicoder 275 Record de participation
Critique du concours AtCoder
concours yukicoder 247 Record de participation
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Examen du concours de programmation HHKB 2020
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
yukicoder contest 261 Record de participation
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
record du concours 262
Critique du concours AtCoder
yukicoder contest 248 Record de participation
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique