TT?が含まれない場合

SSii文字までを取り出した物をSiS_iとし、SiS_iを2進数として解釈した値をkik_iとする。また、

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

とする。

iiが奇数の場合

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

iiが偶数の場合

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

TT?が含まる場合

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

計算量について

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

質問・誤りがある場合

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