Never Be Nabeatsu

解説

このゲームはなんとなくニムに近いなぁと感じると思います。よって各盤面のGrundy数を考えたいのですが、そもそも操作が出来なくなるのは $X$ がいくつのときか分からないのでどこから推移を始めたら良いのかわかりません。

そこで、まず操作が出来なくなる $X$ の値の取っ掛かりを考えます。ゲームのルールより、$X$ の10進法での表記に $3$ を含むことができない点に着目します。 このとき、任意の非負整数 $c$ について $K \leq 10^c \Longleftrightarrow X = 3 \times 10^c -1 で操作ができなくなる$ が成り立ちます。なぜなら、

任意の整数 $i(1 \leq i \leq K)$ に対して、 $X+1 = 3 \times 10^c \leq X+i \leq X+K \leq 4 \times 10^c - 1 = 399...999$ となり、どのように $i$ を定めても $3$ を $X+i$ が含んでしまうからです。なるべく狭い範囲で考える方が良いので、以後 $c$ は $K \leq 10^c$ を満たす最小の整数として話を進めます。

よって、$Grundy(3 \times 10^c -1) = 0$ が分かりました。よって、あとは $3$ の倍数でなく、10進法での表記に $3$ を含まない $3 \times 10^c -1$ 以下の全ての正整数 $z$ について $Grundy(z) = 0$ となるような $z$ のうち、$K$ 以下のものを求めれば良いです。しかし、全ての $z$ についての $Grundy(z)$ の値を逐次調べていては到底間に合いません。

そこで、$Grundy(z) = 0$ となるような $z$ が現れる条件を考えてみます。現時点までに見つかった　$Grundy(z) = 0$ となるような $z$ のうち最小のものを $m$ とおきます。このとき、 $z+K < m$ を満たす $z$ の最大値 $z_{max}$ は 必ず $Grundy(z_{max}) = 0$ を満たします。なぜなら、 $Grundy(z_{max}) = Mex(Grundy(z_{max}+1),Grundy(z_{max}+2), ... , Grundy(z_{max}+K))$ (条件を満たす $z$ のみ考える) であり、$Mex()$ の中には必ず $0$ が含まれないからです。

$z_{max}$ の値は、まず $z_{max} = m-K-1$ とし、

• $z_{max}$ が $3$ の倍数なら $-1$ する
• $z_{max}$ が10進法での表記に $3$ を含むなら$3$ である一番左の桁を $2$ に、その桁よりも右の桁をすべて $9$ にする
• $z_{max}$ が $3$ の倍数なら $-1$ する

という操作をこの順に行うことで具体的に構築できます。あとはこれを $z_{max} \leq K$ となるまで行い、最終的に $0 < z_{max}$ であれば $z_{max}$ の値を、そうでなければ $-1$ を出力すればよいです。

ところで、$K = 2$のとき、$3 \times 10^c -1 = 29$ で操作ができなくなることになりますが、実際には $Grundy(11) = 0$ であるため($11 \rightarrow 12,13$ はどちらも不可能より) 間違った答えを出しそうです。しかし実際には正しく $2$ を出力します。これは、$z = 29$ からのGrundy数が $0$ になる数の推移の中で $z = 11$ を通過するからです。

1クエリ当たりの計算量を考えます。

$Grundy(z) = 0$ となるような $z$ の列挙にかかる時間計算量はどれくらいでしょうか? $Z = 3 \times 10^c -1$ から最低でも $K+1$ を $Z \leq K$ を満たすまで引き続ける回数(= $Grundy(z) = 0$ となるような $z$ の個数)は、計算量が最悪となる $K = 10^{p-1}+1$ とおいても $\displaystyle \frac{3 \times 10^p-1}{10^{p-1}+1} \rightarrow 30$ より、$z$ の列挙1回で $3$ を含む場合の処理が入ったとしても、列挙全体としては $O(logK)$ で終わります。

よって、1クエリ当たりの計算量は $K \leq 10^c$ を満たすような $c$ を $c = 0$ から愚直に探索したとしても $O(logK)$ で済むので $O(logK + logK) = O(logK)$ であり、全体の時間計算量は $O(TlogK)$ となります。制約より、これで十分間に合います。よって、この問題を解くことができました。