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.
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.
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 ** (②).
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.
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.
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.
(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}
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.
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)
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