ARC087 E : Prefix-free Game(700)
作成日：2017.12.17
最終更新日：2017.12.17
問題概要
2つの文字列がprefix-freeであるとは、一方の文字列がもう一方の文字列の接頭辞になっていないことをいう。
また良い文字列集合とは、文字$0,1$からなる長さ$1$以上$L$以下の文字列からなり、相異なる文字列のペアがすべてprefix-freeであるような文字列集合である。
良い文字列集合$S$が与えられ、二人で交互に操作「$S$に新しい文字列を1つ追加」を行う。
但し、操作後も$S$は良い文字列集合でなくてはならない。
操作が先に行えなくなった方が負けである時、二人が最適に行動すると先攻・後攻のいずれが勝つかを答えよ。
制約
$1 \leq N \leq 10^5$
$1 \leq L \leq 10^{18}$
$\sum{|S_i|} \leq 10^5$
考え方
まずはどのような文字列を$S$に追加できるかを考える。
簡単のために$S$が1要素$s$からなるとする。
条件より追加する文字列$t$は、任意の空でない文字列$x$について$s+x=t$も$s=t+x$も成り立ってはいけない。
すなわち、$t$は$i$文字目$(0 \leq i < |s|)$までは$s$と同じであり$(i+1)$文字目は$s$と異なる長さ$(i+1)$以上$L$以下の文字列でなければならない。
$S$が2要素以上からなる時も、その要素全てに対してこの条件を満たしていれば良い。
二人で交互に同じ操作を行い勝敗を決めるゲームであるから、Grundy数を考えたい。
状態は$S$に追加できる文字列の集合、すなわち先の考察における「先頭$(i+1)$文字が決められた長さ$L$以下の文字列の集合」の和集合である。
各「文字列の集合」は1つの整数$L-i$で特徴づけることができ、これは$1$以上の整数になる。
状態のGrundy数は「文字列の集合」それぞれが状態の時のGrundy数の$xor$であるから、整数$z$で特徴づけられた「文字列の集合」のGrundy数$g_z$を求めることを考える。
そのために「文字列の集合」中の要素の1つをを$S$に追加することで状態がどのように変化するかを知る必要がある。
長さ$(i+1)$の文字列を$S$に追加すると、状態は空になる。
長さ$(i+1+j)$$(j>0)$の文字列を$S$に追加すると、先の考察から状態には$L-i-j$から$L-i-1$で特徴づけられる「文字列の集合」が1つずつ存在するようになる。
このことから$g_z$を再帰的に求めていくと、$1$,$2$,$1$,$4$,$1$,$2$,$1$,$8$,$...$となる。
これは$g_z$が$z$を割り切る最大の$2$の累乗であることを示唆している。
あとは初期状態に含まれている「文字列の集合」それぞれを特徴づける整数が求められれば良い。
これは文字列を先頭から決めていき、$S$中に該当する文字列がないものを見つけていくことで達成できる。
但し先頭から決めていった結果$S$の要素の1つと一致したら、条件を満たさなくなるので中断する必要がある。
計算量はTrie木を構築すれば$O(N)$、文字列を先頭から決めた時に該当する$S$の要素を事前に$S$をソートした上で二分探索を用いて保持していけば$O(N \: log \: N)$となる。
いずれにしても十分高速である。
ソースコード
マクロ等はこちら
const int MC = 100010;
int N;
LL L;
string S[MC];
LL ans = 0;
int BS(int x , int y ,int d){
if(y-x<2) return x;
int z = (x+y)/2;
return S[z][d] == '0' ? BS(z,y,d) : BS(x,z,d);
}
void dfs(int x , int y , LL d){
if(x==y){
LL z = L - d;
ans ^= (z&-z);
return;
}
if(x+1==y && S[x].size() == d+1) return;
int z = BS(x-1,y,d+1);
dfs(x,z+1,d+1);
dfs(z+1,y,d+1);
}
int main(){
cin >> N >> L;
repp(i,0,N) cin >> S[i];
sort(S,S+N);
int z = BS(-1,N,0);
dfs(0,z+1,0);
dfs(z+1,N,0);
cout << (ans ? "Alice" : "Bob") << endl;
return 0;
}解法まとめ
文字列を先頭から決めていく。(dfs)
その際、境界は二分探索で求める。(BS)
$d+1$文字決めた時に$S$中に該当する要素がなければ、初期状態のGrundy数に$g_{L-d}$を$xor$する。(14-18行)
$S$の要素でこれまで決めた文字列に一致するものがあれば中断する。(19行)
初期状態のGrundy数が$0$なら後攻(Bob)、そうでなければ先攻(Alice)が勝つ。(32行)