AtCoder Grand Contest 045 Critique

Impressions de cette époque

J'ai décidé de ne pas me retirer de NoSub cette fois et j'ai participé au concours, mais par conséquent, il était 0 complet. Cependant, cette fois, je n'ai pas dit que la considération était insatisfaisante, et c'était un type de problème que je n'avais jamais fait en premier lieu, donc je pense que cela ne peut pas être aidé. De plus, je voulais résoudre non seulement un problème, mais aussi un problème en C, mais je n'ai pas pu le résoudre car la dernière implémentation n'a pas pu être terminée. Cela me paraissait impossible même si j'y pensais pendant un jour, alors je vais l'oublier une fois parce que je manque de capacité. Les articles ont été mis à jour récemment, je ferai donc de mon mieux pour accélérer le rythme des mises à jour.

Problème A

Aperçu du problème

Le problème est de répéter l'opération de remplacement (ou non de remplacement) de $ x $ par $ x \ oplus A_i $ par $ i = 1 $ ~ $ n $, et enfin de considérer s'il peut être mis à 0.

Prémisse de considération

Gagner ou perdre est décidé dans un jeu de type bataille à deux joueurs, alors considérez ** ce qui arrivera à l'état final ** (①). Il convient également de noter que XOR peut ** calculer chaque bit indépendamment ** (②).

Politique 1

Tout d'abord, j'ai remarqué que c'est un cas particulier que $ x = 0 $ car tous les bits sont 0. Par conséquent, j'ai pensé qu'il serait assez difficile d'atteindre l'objectif de ** personnes 0 et j'ai décidé d'explorer ce cas. Cependant, comme chaque bit se déplace indépendamment de la prémisse (2), j'ai pensé qu'il serait difficile de le trouver de manière découvrable, j'ai donc rejeté cette politique.

Politique 2

Si $ x = 0 $ est considéré comme l'état de la valeur de $ x $, l'état de $ x $ à chaque tour $ i $ est au plus de 10 $ ^ {18} $, donc $ m = 10 ^ {18} Je pensais que si c'était $, il pourrait être calculé par $ O (mn) $. De plus, lorsqu'elle est combinée avec l'hypothèse (1), la personne avec le numéro 0 considère un candidat pour la valeur de $ x $ au moment du tour $ i $, qui deviendra finalement $ x = 0 $, et le numéro 1 Je me demande si je peux faire une valeur de $ x $ qui n'est pas un candidat pour **. → Cependant, comme le nombre de candidats de valeur $ m $ à chaque tour est grand, je n'ai pas pu faire le calcul à temps, et j'ai essayé de réduire $ m $, mais je ne pouvais pas bien le considérer.

De là, c'est une considération après avoir vu la réponse

Politique 3

En fait, si vous développez Policy 2, vous pouvez vous rapprocher de la bonne solution. La stratégie 2 ci-dessus est une transition de l'état **, vous pouvez donc penser à DP ** et préparer un tableau pour enregistrer l'état de $ DP $ comme indiqué ci-dessous.

$ DP [i] = $ (un ensemble de $ t $ tel que $ x = t $ avant le $ i $ ème tour et le jeu continue à partir de là jusqu'à $ x = 0 $)

Compte tenu de la transition de DP [i] sous ceci, c'est comme suit.

(1) Lorsque $ S_i = 0 $ ** La personne numéro 0 veut penser à autant de candidats $ x $ que possible **, donc tout ce qu'il a à faire est de lister tous les candidats $ x $ possibles au moment de ce tour $ i $. Par conséquent, la transition de $ DP $ est la suivante.

DP[i]=DP[i+1] \cup \\{v\oplus A_i|v \in DP[i+1]\\}

(2) Lorsque $ S_i = 1 $ ** La personne numéro 1 veut gagner $ x $ qui n'est pas inclus dans les candidats $ x $ possibles ($ DP [i + 1] $) au moment du prochain tour $ i + 1 $ ** Quand on y pense, il est facile de distinguer les cas. Maintenant, considérant $ x (\ in DP [i]) $, qui est $ x \ notin DP [i + 1] $, la personne avec le numéro 1 dans le tour $ i $ ne fait rien et le dernier $ Puisque x $ peut être différent de zéro, il doit être $ x \ in DP [i + 1] $. De plus, il est possible que $ x \ in DP [i + 1] $ soit aussi $ x \ oplus A_i \ notin DP [i + 1] $, donc la transition de $ DP $ à ce moment est la suivante. ..

\begin{cases}
DP[i]=DP[i+1] \ \ \ \  ( ^∀ x\in DP[i+1])(x \oplus A_i \in DP[i+1])\\
DP[i]=0 \ \ \ \  (^∃ x \in DP[i+1])(x \oplus A_i \notin DP[i+1])\\
\end{cases}

Politique 4

La <Politique 3> est une clarification de ma <Politique 2> et je n'ai pas encore été en mesure de réduire le montant du calcul, mais j'envisagerai de réduire l'état à partir d'ici. Considérons que nous représentons $ DP [i] $ sans conserver tous les éléments du ** $ DP [i] $ set **.

Tout d'abord, je pense qu'il va de soi que ** exprimé sous forme de formules mathématiques ** et $ DP [i] $ peuvent s'écrire comme suit.

DP[i]=\\{a_iA_i \oplus a_{i+1}A_{i+1} \oplus … \oplus a_nA_n\\}(a_{i},a_{i+1},…,a_n \in \\{0,1 \\})

Dans l'expression ci-dessus, $ a_ {i}, a_ {i + 1},…, a_n $ est un multiple constant, et $ A_ {i}, A_ {i + 1},…, A_n $ est divisé en bits et $ En supposant que l'ensemble de produits direct de \ {0,1 \} $ est utilisé, $ A_ {i}, A_ {i + 1},…, A_n $ peuvent être considérés comme des vecteurs, respectivement.

Par conséquent, ** $ DP [i] $ peut être considéré comme un espace vectoriel ** qui peut être représenté par une combinaison linéaire des vecteurs $ A_ {i}, A_ {i + 1},…, A_n $ par XOR. De plus, comme MSB (bit le plus significatif) est au plus 59 de $ 1 \ leqq A_i \ leqq 10 ^ {18} <2 ^ {60} $, la dimension de cet espace vectoriel est au plus de 60.

Par conséquent, ** il suffit d'avoir une base pour représenter cet espace vectoriel **, et il suffit de stocker au plus 60 entiers. Par conséquent, envisagez de préserver la base dans la transition DP. Normalement, vous pouvez utiliser la méthode de balayage pour penser à la base **, mais la méthode de balayage ne suffit pas en termes de montant de calcul.

En fait, il n'est pas trop difficile de trouver la base en utilisant les fonctionnalités XOR. ** Lorsqu'il y a des bases dans un espace vectoriel avec XOR comme connexion linéaire, chaque base peut être définie comme un entier de MSB différents ** (si $ \ car $ MSB prend ces XOR pour la même base) Un MSB peut être réduit). … (✳︎)

Selon cela, la transition de DP peut être pensée comme suit: $ DP [i] = $ (un ensemble de bases de l'espace vectoriel représenté par $ A_i $ ~ $ A_n $). (Il est facile à comprendre en comparant avec <Policy 3>.)

(1) Lorsque $ S_i = 0 $ Pour tout $ v (\ in DP [i]) $, si $ A_i $ est linéairement indépendant, alors $ DP [i] = DP [i + 1] \ cup \ {A_i \} $ Pour tout $ v (\ in DP [i]) $, si $ A_i $ est linéairement dépendant, alors $ DP [i] = DP [i + 1] $

(2) Lorsque $ S_i = 1 $ $ DP [i] = 0 $ si $ A_i $ est linéairement indépendant pour tout $ v (\ in DP [i]) $ Pour tout $ v (\ in DP [i]) $, si $ A_i $ est linéairement dépendant, alors $ DP [i] = DP [i + 1] $

Aussi, pour déterminer s'il est linéairement indépendant ou linéairement dépendant, il est facile de l'implémenter en utilisant la propriété de (✳︎) pour ** stocker des bases avec différents MSB dans $ DP [i] $ **. Autrement dit, il devrait être défini comme $ DP [i] [j] = $ (MSB de l'espace vectoriel représenté par $ A_i $ ~ $ A_n $ est la base de $ j $). Pour déterminer si $ A_i $ est linéairement indépendant de ces bases sous ceci, remplacez $ A_i $ par $ A_i $ et le XOR de cette base si la même base MSB que $ A_i $ existe. ** ($ \ car $ (✳︎)) est répété, et si $ A_i = 0 $ à la fin, $ A_i $ est linéairement dépendant et il n'y a pas de base où MSB est égal à "MSB of $ A_i $". Dans ce cas, $ A_i $ peut être déterminé comme étant linéairement indépendant.

En déterminant si elle est linéairement indépendante ou linéairement dépendante par l'opération ci-dessus, la transition de DP dans (1) et (2) peut être exprimée, et $ O (t \ fois n \ fois (\ log {A_ {) max}}) ^ 2) Vous pouvez écrire un programme avec un montant de calcul de $.

A.py


import numpy as np
#0-indexed,Lorsque MSB est inférieur ou égal à ma
def msb(x,ma=59):
    for i in range(ma,-1,-1):
        if (x>>i)&1:
            return i
    return len()
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    s=input()
    #Indépendant, personne n'est pareil
    #Au contraire, s'ils sont différents, ils deviennent indépendants.
    msbs=[0 for i in range(60)]
    for i in range(n-1,-1,-1):
        now=a[i]
        m=59
        #Lorsqu'il est indépendant, f est Vrai, lorsqu'il n'est pas indépendant, f est Faux
        while True:
            m=msb(now,m)
            if msbs[m]==0:
                f=True
                break
            now=msbs[m]^now
            if now==0:
                f=False
                break
        if s[i]=="0":
            if f:
                msbs[m]=now
        else:
            if f:
                print(1)
                break
    else:
        print(0)

Problème après B

Je ne peux pas le résoudre cette fois car je ne suis pas assez bon et j'ai passé beaucoup de temps sur le problème A.

Recommended Posts

AtCoder Grand Contest 041 Critique
AtCoder Grand Contest 048 Critique
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
AtCoder Grand Contest 046 Critique
Critique du concours AtCoder Beginner Contest 152
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
Critique du concours AtCoder Débutant 181
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
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
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
AtCoder Grand Contest 041 Rapport de participation
AtCoder Grand Contest 040 Rapport de participation
AtCoder Grand Contest 047 Rapport de participation
AtCoder Grand Contest Past Question Challenge 2
AtCoder Grand Contest Défi des questions passées 1
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 177
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
concours yukicoder 261 avis
concours yukicoder 267 avis
Concours AtCoder Débutant 173
concours yukicoder 266 avis
Concours Atcoder Débutant 153
concours yukicoder 263 avis
yukicoder contest 268 avis
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
AtCoder Beginner Contest 119 Revue des questions précédentes