$T$に?が含まれない場合

$S$の$i$文字までを取り出した物を$S_i$とし、$S_i$を2進数として解釈した値を$k_i$とする。また、

• 先手必勝の場合、$f_i(k_i)=1$
• 後手必勝の場合、$f_i(k_i)=0$

とする。

$i$が奇数の場合

0か1のうちどちらかに先手必勝となる手があれば先手必勝であり、どちらでも後手必勝でれば後手必勝である。 よって、$f_{i}(k_i)=f_{i+1}(2k_i)\ {\rm or}\ f_{i+1}(2k_i+1)$である。

$i$が偶数の場合

0と1のどちらも先手必勝となる場合のみ先手必勝であり、どちらかに後手必勝となる手があれば後手必勝である。 よって、$f_{i}(k_i)=f_{i+1}(2k_i)\ {\rm and}\ f_{i+1}(2k_i+1)$である。

$T$に?が含まる場合

以下の表を用いてandやorの演算を行う。 $\ \ \begin{array}{c|ccc} {\rm and} & 0 & 1 & ? \\ \hline 0 & 0 & 0 & 0\\ 1 & 0 & 1 & ?\\ ? & 0 & ? & ?\\ \end{array}\ \$ $\begin{array}{c|ccc} {\rm or} & 0 & 1 & ? \\ \hline 0 & 0 & 1 & ?\\ 1 & 1 & 1 & 1\\ ? & ? & 1 & ?\\ \end{array}$

計算量について

$k_i$の値は$2^i$通りなので、$f_{i}(k_i)$の計算回数は$2^1+2^2+\cdots+2^{n-1}=2^n-2$である。よって、計算量は$O(2^n)$であり、この制約下では十分時間内に間に合う。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378