yukicoder No.2132 1 or X Game解説の解説

筆者（$p$進大好きbot）は★2.5がなかなかコンテスト時間内に解けるようにならないのが悩みです。最近は以前解いた問題を復習しています。

今回扱うのはyukicoder contest 369 C問題 No.2132 1 or X Gameです。ゲーム問題に要求される考察が詰まっていて非常に勉強になる問題ですが、一方で公式解説は後述する理由により強い人でないと正確に読解しにくい（筆者よりずっと強い人向けに書かれている）と思ったので、自分の勉強の意味も込めてもう少し詳しい解説を書いてみました。

問題の概要

正確な問題文はこちらです。

$2$個の正整数$N, X$が与えられます。 各正整数$n$に対し、ゲーム$n$と呼ばれる以下の$2$人ゲームを考えます。

• 最初に$n$個の石がある。先手と後手が交互に以下のいずれかの操作を繰り返し、繰り返せなくなったプレイヤーの敗北となる。
  • 石を$1$個取る。
  • 石を$X$個取る。ただしこの操作は、直前の自身の操作で石を$X$個取っていた場合は選択できない。

$N$以下の正整数$n$をわたってゲーム$n$を行い双方が最善を尽くした時、先手の勝利する回数を$998244353$で割った余りを求めてください。

$X$個取る操作に制限があることが厄介ですね。

公式解説のコピー

引用元はこちらです。

$X$ が奇数の時は自明です。

$X$ が偶数の場合、

$X$ 個減らす操作がゲーム中で行われた回数から勝敗が定まります。

また、先手が最初に行う行動を考えることで、以下の事実が導かれます。

• ゲーム $n-1$ が先手負けならば、ゲーム $n は先手勝ちである。
• ゲーム $n-1$ が先手勝ちで、かつゲーム $n-X-2$ が先手勝ちならば、ゲーム $n$ は先手負けである。
• ゲーム $n-1$ が先手勝ちで、かつゲーム $n-X-2$ が先手負けならば、ゲーム $n-2X-2$ が先手勝ちのときに限りゲーム $n$ は先手勝ちである。

$n$ の値で場合分けを行います。

• $1 \leq n \leq X$ の場合

明らかです。

• $X+1 \leq n \leq 2X-1$ の場合

$X$ を取る操作は必ず $1$ 回行われます。（先手と後手の片方は、 $X$ 個減らす操作を行いたく、これは必ず実現できるため）よって勝敗も定まります。

• $2X \leq n$ の場合

先述の事実と $2X-1$ 以下のゲームの勝敗を用いると、ゲーム $X$ 以降で $X+3$ 周期を持つことが帰納法により証明できます。

公式解説の正確な読解が難しいと感じた点を説明します。解説に何を書くかは人それぞれですし競技プログラマー向けの解説は数学の証明を書くことを必ずしも意図している場でないので解説の良し悪しを述べるつもりはなく、あくまでこれらを解消した解説を書いてみようという試みであることをご了承ください。

まず実際に勝敗がどうなるかや数え上げがどうなるかのどちらも書かれていないので、解説を読んだだけでは実際に書くべきコードが明らかになりません。また周期性は帰納法で証明できるということだけ宣言されていて証明されていないので、解説を読んだだけでは正確な証明をする方法が明らかになりません。解法の正当性を確認する時に一度は証明をしているでしょうし、ミスがないようにtester作業ご依頼時にtesterさんに解法の正当性をチェックしてもらう際はわざわざ独立に再証明してもらうわけでもないでしょうから証明を省略せずに説明したのでしょうし、それならばいちいち消さずに残せば良いのにと思ってしまう程度には非自明な議論に主観的に感じます。

次に「$X$ 個減らす操作がゲーム中で行われた回数から勝敗が定まります」という記述は双方の戦略を自由に固定するごとに成り立つ主張であるため最善戦略に限る文脈ではない一方で、「$X$を取る操作が必ず$1$回行われます」という記述は言外に最善戦略に限っているため解説中の条件設定が不明瞭になっています。正確に表現するならば「双方の任意の最適戦略において$X$個減らす操作が必ずちょうど$1$回行われる」という感じになります。この辺の用語の濫用の影響で最初は文意が分からずかなり混乱してしまいました。

そして公式解説においてゲーム$n$が定義されるのは$n$が正整数の時のみです。例えば「ゲーム$n$が～ならば…」などの条件分岐が出てきた時、「$n>0$ならば『ゲーム$n$が～ならば…』」という解釈と「『$n>0$かつゲーム$n$が～』ならば…」という解釈の$2$通りが可能で曖昧です。今回は後者で解釈すると矛盾することが確認できたので、前者で解釈しました。この辺の非自明な考察が文章の意図を推測する際にすら要求されるのもかなり読解を難しくしていると思います。

ターン数と勝敗

勝ち星の数え上げ問題なので、非負整数$n$に対する$(n,X)$のデータからゲーム$n$の勝者の決定が高速に（何らかの明示式や周期計算で）処理できることが推測されます。というか数え上げにして初めて意味のある問題設定がないので本当にヒントのためだけに数え上げにしたのかもしれませんね。わざわざ$998244353$を法としている理由も同様に、余りを求める演算子を知っているかを問う以上の深い意味があるのかもしれません。

というわけでまずはゲーム内容を観察して規則を見つけましょう。

なお問題では$n$が正の場合しか扱いませんが、考察に漸化式や帰納法を多用するゲーム問題では問題を拡張する（ゲームの初期状態としては現れないが途中経過で現れる状態を初期状態に許す）方が処理しやすいこともあり、必要に応じて$n=0$のようなケースを許して考察しましょう。

戦略の選択肢がない場合

もし双方が$X$個を取る操作を一度も行わないという追加の縛りがあれば、双方に戦略の選択肢がないので初期状態だけで以下のように勝敗が決まります。

1. $n$ が偶数ならば後手の勝利。
2. $n$ が奇数ならば先手の勝利。

これだけであれば厳密な証明をせずとも石を交互に取っていく状況を思い浮かべることで容易に分かりますが、$X$個を取る操作を行う場合の勝敗を決める際の手掛かりとするためにきちんと証明の仕方を考えてみます。

それぞれの操作によって石が$1$個ずつ減り、ターン$1$開始時点で石の個数が$n$であることから、ターン数とそのターン開始時点の石の個数の和が$n+1$固定であることが分かります。従って最終局面はターン$n+1$です。

各ターンのアクティブプレイヤー（そのターンに操作を行うプレイヤー）はターン数が奇数ならば先手、偶数ならば後手なので、最終局面のアクティブプレイヤーは$n+1$が奇数ならば先手、$n+1$が偶数ならば後手です。以上より

1. $n+1$ が奇数ならば後手の勝利。
2. $n+1$ が偶数ならば先手の勝利。

となることが分かりました。これは示したかった内容と同値です。

戦略の選択肢がある場合

以上のように、戦略の選択肢がない場合（特に$X=1$の場合）はターン数の計算から簡単に勝敗を決定できました。以下では$X > 1$として$X$個を取る操作を許す場合を考えますが、先程と同様に最終局面のターン数の計算に帰着できれば楽ですね。一般に交互に操作を行う$2$人ゲームでは最終局面のターン数の偶奇だけで勝敗が決まるので、ターン数に注目する考えが自然です。

そこで、ゲーム$n$を実際に行った時の双方の戦略$s$（双方が各ターンにどの選択をしたかの情報を並べた列、形式的には$1,X$の列）を固定して、最終局面のターン数を算出してみましょう。ここで$s$は実際のゲームの進行を可能とする戦略なら何でも良く、双方の最善戦略でなくてもよいです。

$s$中で$1$を取る操作が行われた回数の合計を$a$、$X$を取る操作が行われた回数の合計を$b$と置きます。取られた石の数の合計が$n$であることから$a+Xb = n$すなわち$a = n-Xb$となるので、最終局面のターン数は$a+b+1 = n+1-(X-1)b$です。従って$b$が確定すれば$s$における勝敗が以下のように決まります。

1. $n+1-(X-1)b$が奇数ならば後手の勝利。
2. $n+1-(X-1)b$が偶数ならば先手の勝利。

偶奇の計算はmod $2$に翻訳すると分かりやすいので、翻訳してみると以下のようになります。以下合同式の法は全て$2$です。

1. $X \equiv 0$かつ$n \equiv b$ならば後手の勝利。
2. $X \equiv 0$かつ$n \equiv b-1$ならば先手の勝利。
3. $X \equiv 1$かつ$n \equiv 0$ならば後手の勝利。
4. $X \equiv 1$かつ$n \equiv 1$ならば先手の勝利。

というわけで、以下では$X \equiv 0$の場合に絞って先手が$n \equiv b-1$を確実に実現可能（後手がどのような操作をしてもそれに合わせて先手が適切に操作することで実現可能）か否かを判定すればよいです。

ここまでが、公式解説の「$X$ 個減らす操作がゲーム中で行われた回数から勝敗が定まります」で述べられていることです。

小さいケースでの勝敗

$n < X$の場合は$X$個取るという操作が$1$回も行えないため、戦略の選択肢がない場合に帰着されます。

$X \leq n < 2X$の場合は$X$個取るという操作が高々$1$回しか行えませんが、双方の最善戦略に限れば必ずちょうど$1$回行われます。このことは公式解説だと「先手と後手の片方は、 $X$ 個減らす操作を行いたく、これは必ず実現できるため」という先手と後手の気持ち（？）に寄り添った非形式的な説明しか書かれていませんが、以下のように$n$に関する帰納法で証明できます。（$n = X$を場合分けのどこに含めるかが公式解説とはずれていますが、そこは大きな問題ではありません）

$n = X$の場合

$X$個取る操作を$1$回も行わない場合の勝敗は戦略の選択肢がない場合に帰着され、$X$が偶数であることから後手の勝利となります。一方で先手がターン$1$に$X$個取った場合、ターン$2$で石がなくなるので先手の勝利となります。

以上より、$X$個取る操作を$1$回も行わない戦略は先手にとって最善の戦略でなく、すなわち先手にとって最善の戦略ならば$X$個取る操作を$1$回行います。

$X < n < 2X$の場合

$s$を双方の最善戦略とします。$s$において$X$個取る操作が$1$回行われることを示します。

$s$の先頭（ターン$1$における先手の操作）で先手が$X$個取る場合は良いので、$s$の先頭で先手が$1$個取る場合を考えます。

$s$が双方の最善戦略であることと$s$の先頭が$X$個取る操作でないこと（先頭以降の戦略に追加の制限を与えないこと）から、$s$から先頭を削除して得られる双方の戦略$s’$はゲーム$n-1$において先手と後手を入れ替えたものの双方の最善戦略となります。

$X \leq n-1 < 2X$であるので、帰納法の仮定から$s’$において$X$個取る操作が$1$回行われます。

以上より、$s$において$X$個取る操作が$1$回行われることが示されました。

勝敗のまとめ

以上をまとめると、以下のようになります：

1. $n < X$かつ$n$が奇数ならば、先手の必勝。
2. $n < X$かつ$n$が偶数ならば、後手の必勝。
3. $X \leq n < 2X$かつ$n$が奇数ならば、後手の必勝。
4. $X \leq n < 2X$かつ$n$が偶数ならば、先手の必勝。

$n$が大きい場合の勝敗

同一のプレイヤーが$X$個取るという操作を連続して行えないという制限が厄介ですが、例えばゲームの状態を

1. 現在の石の数$n$
2. アクティブプレイヤーが$X$個取るという操作を直前に行ったか否か$p$（${0,1}$値）
3. 非アクティブプレイヤーが$X$個取るという操作を直前に行ったか否か$q$（${0,1}$値）

の$3$つ組$(n,p,q)$として管理しましょう。初期状態としては$p=q=0$しか許されませんが、先述したようにゲームの初期状態としては現れないが途中経過で現れる状態を初期状態に許す方がここでも考察はしやすくなります。

愚直解による実験

まずは愚直な動的計画法を考えます。状態$(n,p,q)$でのアクティブプレイヤーが必勝であることの真偽$\textrm{dp}(n,p,q)$は、

1. アクティブプレイヤーが$1$個取るという操作をした後で次のアクティブプレイヤーが必勝でないこと（$n \geq 1$かつ$\neg \textrm{dp}(n-1,q,0)$）。
2. アクティブプレイヤーが$X$個取るという操作をした後で次のアクティブプレイヤーが必勝でないこと（$n \geq X$かつ$p=0$かつ$\neg \textrm{dp}(n-X,q,1)$）。

の論理和

\[ (n \geq 1 \land \neg \textrm{dp}(n-1,q,0)) \lor (n \geq X \land p=0 \land \neg \textrm{dp}(n-X,q,1)) \]

と同値です。より一般に、ゲームの状態遷移が整礎な（無限長の道を持たない）有向グラフで実現される$2$人ゲームのアクティブプレイヤーの必勝性は、現時点の状態に対応する頂点を始端とする有向辺の終端に対応する状態のアクティブプレイヤーの必勝性の否定の論理和と同値です。

この漸化式から愚直解が書けるので、必要ならばデバッグと実験用に愚直解を書いてみるのもいいですね。

愚直解のC++での実装例

筆者はこの手の実験コードを有向グラフで抽象化してライブラリにしています。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <typename Edge , typename T>
const bool& IsWinningState( Edge& edge , const T& t , const bool& reset = false )
{

  static_assert( is_invocable_v<Edge,const T&> );
  static map<T,bool> g{};

  if( reset ){

    g.clear();

  }

  if( g.count( t ) == 1 ){

    return g[t];

  }

  bool b = false;

  for( auto&& u : edge( t ) ){

    b |= !IsWinningState( edge , u );

  }

  return ( g[t] = b );

}

int main()
{
  constexpr const int bound = 20;
  for( int X = 2 ; X <= bound ; X += 2 ){
    auto edge = [&]( const tuple<ll,bool,bool>& v ){
      auto& [i,p,q] = v;
      vector<tuple<ll,bool,bool>> answer{};
      if( i >= 1 ){
        answer.push_back( {i-1,q,0} );
      }
      if( i >= X && p == 0 ){
        answer.push_back( {i-X,q,1} );
      }
      return answer;
    };
    IsWinningState( edge , tuple<ll,bool,bool>{ bound , false , false } , true );
    vector<bool> win( bound + 1 );
    for( int n = 0 ; n <= bound ; n++ ){
      win[n] = IsWinningState( edge , tuple<ll,bool,bool>{ n , false , false } );
    }
    cout << "X = " << X << ": ";
    for( int n = 0 ; n <= bound ; n++ ){
      cout << win[n] << " \n"[n==bound];
    }
  }
}

X = 2: 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0
X = 4: 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1
X = 6: 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0
X = 8: 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0
X = 10: 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1
X = 12: 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1
X = 14: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1
X = 16: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1
X = 18: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1
X = 20: 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1

ここまでで、どうも$n = X-2$から周期$X+3$のループがありそうなことが推測できます。

この推測が正しいと仮定して$n$が小さい場合の結果と合わせると、改めて$X$が奇数の場合も考慮した数え上げの答えは$N-(X-2)+1 = N-X+3$を$X+3$で割った余り$r$を用いて以下のようになりそうです。

\[ \left\{ \begin{array}{ll} \lfloor \frac{N+1}{2} \rfloor & (X \equiv 1 \lor N < X-2) \\
\frac{X-2}{2} + \left( \frac{X}{2} + 2 \right) \left\lfloor \frac{N - X + 3}{X + 3} \right\rfloor + \lfloor \frac{r+1}{3} \rfloor & (X \equiv 0 \land N \geq X-2 \land r \leq 2) \\
\frac{X-2}{2} + \left( \frac{X}{2} + 2 \right) \left\lfloor \frac{N - X + 3}{X + 3} \right\rfloor + \lfloor \frac{r+1}{2} \rfloor & (X \equiv 0 \land N \geq X-2 \land r \geq 3) \\
\end{array} \right. \]

推測結果のcLayでの実装例

推測が正しいか否かはさておき、推測結果の実装は非常に簡単なので、証明より前に試しに提出してみましょう。

今回のようなシンプルな処理はcLayを使うと特に楽に実装することができるのでおすすめです。

ll@T;rep(T){ll@N,@X,d=N-X+3,p=X+3,r=d%p;wt((X&1|N<X-2?N/+2:X/2-1+d/p*(X/2+2)+(r+1)/(r>2?2:3))%998244353);}

提出結果はACでした。

ところで同じくcLayで書かれたtailsさんの提出コードさっぱりなのですがどうなってるんですのこれ。

$\textrm{dp}(n,0,0)$の漸化式

再び$X$が偶数の場合に絞り$n = X-2$から周期$X+3$のループがあることを確認していきたいのですが、そのためには$\textrm{dp}(n,p,q)$の漸化式から$\textrm{dp}(n,0,0)$の漸化式を得る必要があります。

ここで注目すべきは、$X$個取る操作が連続できないという制約です。これにより、$\textrm{dp}(n,p,q)$の漸化式を展開して$n$が小さい値に帰着させていった時、$p=1$となる式を展開した式では（先後反転するので$p,q$の位置も変わることに注意して）元の$q$が$p$となり$q=0$となり、更にそこで$p=1$となる式を展開した式では元の$q=0$が$p$となり$q=0$となります。つまり高々$2$段階の式変形を漸化式に沿って行うことで、$\textrm{dp}(n,0,0)$の漸化式が得られます。

bool値の相等は本来$\Leftrightarrow$などで書くものですが${0,1}$値とみなして等式で書くと、具体的には以下のようになります：

\[ \begin{align} & \ \ \textrm{dp}(n,0,0) \\
= & \ \ (n \geq 1 \land \neg \textrm{dp}(n-1,0,0)) \lor (n \geq X \land \neg \textrm{dp}(n-X,0,1)) \\
= & \ \ (n \geq 1 \land \neg \textrm{dp}(n-1,0,0)) \lor \\
& \ \ (n \geq X \land \neg((n-X \geq 1 \land \neg \textrm{dp}(n-X-1,1,0)) \lor (n-X \geq X \land \neg \textrm{dp}(n-2X,1,1)))) \\
= & \ \ (n \geq 1 \land \neg \textrm{dp}(n-1,0,0)) \lor \\
& \ \ ( \\
& \ \ \ \ n \geq X \land \\
& \ \ \ \ \neg( \\
& \ \ \ \ \ \ (n-X \geq 1 \land \neg(n-X-1 \geq 1 \land \neg \textrm{dp}(n-X-2,0,0))) \lor \\
& \ \ \ \ \ \ (n-X \geq X \land \neg(n-2X \geq 1 \land \neg \textrm{dp}(n-2X-1,1,0))) \\
& \ \ \ \ ) \\
& \ \ ) \\
= & \ \ (n \geq 1 \land \neg \textrm{dp}(n-1,0,0)) \lor \\
& \ \ ( \\
& \ \ \ \ n \geq X \land \\
& \ \ \ \ \neg( \\
& \ \ \ \ \ \ (n-X \geq 1 \land \neg(n-X-1 \geq 1 \land \neg \textrm{dp}(n-X-2,0,0))) \lor \\
& \ \ \ \ \ \ (n-X \geq X \land \neg(n-2X \geq 1 \land \neg(n-2X-1 \geq 1 \land \neg \textrm{dp}(n-2X-2,0,0)))) \\
& \ \ \ \ ) \\
& \ \ ) \\
= & \ \ (n \geq 1 \land \neg \textrm{dp}(n-1,0,0)) \lor \\
& \ \ ( \\
& \ \ \ \ (n = X \lor (n \geq X+2 \land \neg \textrm{dp}(n-X-2,0,0))) \land \\
& \ \ \ \ (X \geq n < 2X \lor (n = 2X+1 \lor (n \geq 2X+2 \land \textrm{dp}(n-2X-2,0,0)))) \\
& \ \ ) \end{align} \]

便宜的に$n$が負の場合の$\textrm{dp}(n,p,q)$を偽と定めれば、$n$が正の場合の漸化式はよりシンプルに

\[ \begin{align} \textrm{dp}(n,0,0) = & \ \ \neg \textrm{dp}(n-1,0,0) \lor n = X \lor \\
& \ \ (n > X \land \neg \textrm{dp}(n-X-2,0,0) \land (n < 2X \lor \textrm{dp}(n-2X-2,0,0))) \end{align} \]

と書き表せます。これの一部を取り出したものが公式解説の関係式ですね。ただし公式解説では一切$\textrm{dp}(n,p,q)$を考えず直接$\textrm{dp}(n,0,0)$だけで漸化式を立てていることに注意しましょう。後者だけで漸化式を立てるには、先手がターン$1$に$X$個取るか否かを場合分けして、$X$個取る場合は更に後手が$X$個取るか否かで場合分けをする考察が必要になります。要するに$2$ターンや$4$ターンまとめて処理することで、$X$個取る操作が連続できないという制約にうまく対処することができるわけです。

一般に操作の連続回数に制限がある場合に、そのような数ターン分まとめての考察が有効です。やっていることはどちらも結果的に同じですが、一気に頭の中で全部計算するのが難しい場合は今回のように$\textrm{dp}(n,p,q)$の漸化式を展開していくのが良いですね。

周期性の証明に移るために、$\textrm{dp}(2X,0,0), \textrm{dp}(X+3,0,0), \textrm{dp}(3,0,0)$を求めておきます。まず上の漸化式から

\[ \textrm{dp}(2X,0,0) = \neg \textrm{dp}(2X-1,0,0) \lor (\neg \textrm{dp}(X-2,0,0) \land \textrm{dp}(-2,0,0)) = \neg \textrm{F} \lor (\neg \textrm{F} \land \textrm{F}) = \textrm{T} \]

となります。

$\textrm{dp}(3,0,0)$は$X>2$と同値です。このことは$n$が小さい場合の結果を$X = 2$か否かで場合分けして適用すれば従います。

$\textrm{dp}(X+3,0,0)$は偽です。このことは$X = 2$ならば実験コードの出力結果から従い、$X \geq 4$ならば$n$が小さい場合の結果から従います。

周期性の証明

周期性を証明するには、$n \geq X-2$を満たす任意の非負整数$n$に対し

\[ \textrm{dp}(n,0,0) = \textrm{dp}(n+(X+3),0,0) \]

となることを示せば良いです。

ここで、$n \geq X-2$より$n+(X+3) \geq 2X+1$となるので、先程の漸化式から

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \end{align} \]

が成り立ちます。この関係式を用いて、$\textrm{dp}(n,0,0) = \textrm{dp}(n+(X+3),0,0)$となることを$n$に関する数学的帰納法で示します。

$n = X-2$の場合

漸化式と先程の計算結果から、

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \\
= & \ \ \neg \textrm{dp}(2X,0,0) \lor (\neg \textrm{dp}(X-1,0,0) \land \textrm{dp}(3,0,0)) \\
= & \ \ \neg \textrm{T} \lor (\neg \textrm{T} \land (X>2)) \\
= & \ \ \textrm{F} \\
\textrm{dp}(n,0,0) = & \ \ \textrm{dp}(X-2,0,0) = \textrm{F} \end{align} \]

となります。すなわち

\[ \textrm{dp}(n,0,0) = \textrm{F} = \textrm{dp}(n+(X+3),0,0) \]

です。

$X-2 < n \leq 2X-2$の場合

この時

• $X-2 \leq n-1 < n$
• $X \leq n+1 < 2X$
• $0 \leq n-X+1 < X$
• $-3 \leq n-X-2 \leq X-4 < X$
• $n-2X-2 \leq -4$

であるので、漸化式と帰納法の仮定から

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \\
= & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor (\neg \textrm{dp}(n+1,0,0) \land \textrm{dp}(n-X+1,0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg (n+1 \equiv 0) \land (n-X+1 \equiv 1)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (n \equiv 0) \\
\textrm{dp}(n,0,0) = & \ \ \neg \textrm{dp}(n-1,0,0) \lor n = X \lor \\
& \ \ ((n > X) \land \neg \textrm{dp}(n-X-2,0,0) \land (n < 2X \lor \textrm{dp}(n-2X-2,0,0))) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor n = X \lor ((n > X) \land \neg (n-X-2 \equiv 1)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (n \equiv 0) \\
\end{align} \]

となります。すなわち

\[ \textrm{dp}(n,0,0) = \neg \textrm{dp}(n-1,0,0) \lor (n \equiv 0) = \textrm{dp}(n+(X+3),0,0) \]

です。

$n = 2X-1$の場合

この時

• $X-2 < 2X-2 = n-1 < n$

であるので、漸化式と先程の計算結果と帰納法の仮定から

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \\
= & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor (\neg \textrm{dp}(2X,0,0) \land \textrm{dp}(X,0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{T} \land \textrm{T}) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor \textrm{F} \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \\
\textrm{dp}(n,0,0) = & \ \ \neg \textrm{dp}(n-1,0,0) \lor n = X \lor \\
& \ \ ((n > X) \land \neg \textrm{dp}(n-X-2,0,0) \land (n < 2X \lor \textrm{dp}(n-2X-2,0,0))) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(X-3,0,0) \land \textrm{dp}(-3,0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{T} \land \textrm{F}) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \end{align} \]

となります。すなわち

\[ \textrm{dp}(n,0,0) = \neg \textrm{dp}(n-1,0,0) = \textrm{dp}(n+(X+3),0,0) \]

です。

$2X \leq n < 3X$の場合

この時

• $X-2 \leq 2X-1 \leq n-1 < n$
• $X-2 \leq n-X-2 < n$
• $X+1 \leq n-X+1 \leq 2X$
• $-2 \leq n-2X-2 < X-2 < X$

であるので、漸化式と帰納法の仮定から

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land \textrm{dp}(n-X+1,0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land n \equiv 1) \\
\textrm{dp}(n,0,0) = & \ \ \neg \textrm{dp}(n-1,0,0) \lor n = X \lor \\
& \ \ ((n > X) \land \neg \textrm{dp}(n-X-2,0,0) \land (n < 2X \lor \textrm{dp}(n-2X-2,0,0))) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land (n \geq 2X+2) \land (n-2X-2 \equiv 1)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land n \neq 2X+1 \land n \equiv 1) \end{align} \]

となります。$n = 2X+1$ならば

\[ \textrm{dp}(n-X-2,0,0) = \textrm{dp}(X-1,0,0) = \textrm{T} \]

となるので、$\neg \textrm{dp}(n-X-2,0,0) \land n \neq 2X+1$と$\neg \textrm{dp}(n-X-2,0,0)$は同値です。以上より

\[ \textrm{dp}(n,0,0) = \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land n \equiv 1) = \textrm{dp}(n+(X+3),0,0) \]

です。

$3X \leq n$の場合

この時

• $X-2 \leq 3X-1 \leq n-1 < n$
• $X-2 \leq 2X-2 \leq n-X-2 < n$
• $X-2 \leq n-2X-2 < n$

であるので、漸化式と帰納法の仮定から

\[ \begin{align} \textrm{dp}(n+(X+3),0,0) = & \ \ \neg \textrm{dp}((n-1)+(X+3),0,0) \lor \\
& \ \ (\neg \textrm{dp}((n-X-2)+(X+3),0,0) \land \textrm{dp}((n-2X-2)+(X+3),0,0)) \\
= & \ \ \neg \textrm{dp}(n-1,0,0) \lor (\neg \textrm{dp}(n-X-2,0,0) \land \textrm{dp}(n-2X-2,0,0)) \\
= & \ \ \textrm{dp}(n,0,0) \end{align} \]

となります。以上より、全ての場合で

\[ \textrm{dp}(n,0,0) = \textrm{dp}(n+(X+3),0,0) \]

となることが示せました。$\Box$