問題概要

ある数字ゲームの勝者を求める問題。参加者は Louise と Richard の二名。下記のルールに従い勝者を判断する関数を実装する。なお最初のターンプレイヤーは Louise である。

1. $n$ は $0$ を含まない自然数である。始めに任意の $n$ が与えられる。
2. ターンプレイヤーは $n$ が $2$ の冪であれば、$n$ に $n/2$ を代入する。
3. ターンプレイヤーは $n$ が $2$ の冪でなければ、$n$ に $\min(n-2^m)$ を代入する。
4. $n$ が $1$ であれば、現ターンプレイヤーの勝利である。
5. $n$ が $1$ でなければ、ターンプレイヤーを変更し 2. に戻る。

解答

Python 3

def counterGame(n):
    c = sum([b == "1" for b in bin(n-1)[2:]])
    if c & 1:
        return "Louise"
    else:
        return "Richard"

解説

$n$ が $2$ の冪である場合、ターンごとに $n$ は次表のように更新される。$n=2^1$ のときのターンプレイヤーが勝者であり、$m$ が奇数であれば Louise が、偶数であれば Rechard が勝者となる。

\[ \begin{aligned} \def\arraystretch{1.5} \begin{array}{c:c:c} \text{turn} & n & (n)_2 \\ \hline \text{Louise} & 2^m & 1000\cdots 000 \cr \text{Rechard} & 2^{m-1} & 100\cdots 000 \cr \vdots & \vdots & \vdots \cr \vdots & 2^2 & 100 \cr \text{? (winner)} & 2^1 & 10 \end{array} \end{aligned} \tag{1} \]

$n$ が $2$ の冪ではない場合、ターンごとに $n$ は次表のように更新される。途中で $2$ の冪 $2^{m_2}$ が得られ、 $2^{m_2}$ だけに限れば $(1)$ より $m^2$ の偶奇から勝者を推測できる。最終的な勝者は $n$ が $2^{m_2}$ となるまでのターンの切り替えを考慮しなければならない。次表より、$m_1$ が奇数の場合はターンが切り替わり、$m_1$ が偶数の場合はターンが元に戻ることが確認できる。よって $m_1+m_2$ が奇数のときは Louise が、偶数のとき Rechard が勝者となる。

\[ \begin{aligned} \def\arraystretch{1.5} \begin{array}{c:c:c} \text{turn} & n & (n)_2 \\ \hline \text{Louise} & n & 1010\cdots 1100 \cr \text{Rechard} & \min(n-2^{k_1}) & 10\cdots 1100 \cr \vdots & \vdots & \vdots \cr \vdots & \min(n-\sum_{i\in[m_1]}2^{k_i}) & 1100 \cr \text{?} & 2^{m_2} & 100 \end{array} \end{aligned} \tag{2} \]

$(1),(2)$ より、$m$ と $m_1+m_2$ の偶奇により勝者を判断できる。しかし $n$ の二進数表記から $m,m_1+m_2$ の値を得ようとすると、数える対象が $\lbrace 0,1\rbrace$ と混在しているため手間がかかる。そこで $n-1$ の二進数表記 $1$ の出現回数を数えることで、 $m,m_1+m_2$ の値の数え上げを容易にする。

\[ \def\arraystretch{1.5} \begin{array}{c:c:c} & (n)_2 & (n-1)_2 \\ \hline n=2^m & 1\underbrace{000\cdots 0000}_{0:m} & 0\underbrace{111\cdots 1111}_{1:m} \cr n\ne 2^m & \underbrace{1010\cdots 1}_{1:m_1}1\underbrace{00}_{0:m_2} & \underbrace{1010\cdots 1}_{1:m_1}0\underbrace{11}_{1:m_2} \cr \end{array} \]

参考文献

• Counter game | HackerRank