箸ゲーム

手番のプレイヤーの 1 本指の手と 2 本指の手の数を $a,c$、相手の対応する数を $b,d$ とし、$n=a+c$、$m=b+d$ とおく。

1 本指の手に重み $2$、2 本指の手に重み $1$ を与えると、攻撃のたびに両者の重みの合計が減る。したがって引き分けはない。手がないプレイヤーは負けであり、この重みについての強い帰納法により次の条件を同時に示せる。

• $n>m$ なら勝ち。
• $m\geq n+2$ なら負け。
• $n=m$ なら、$b=m$ かつ が奇数のときに限り負け。

$n>m$ では、相手の手を消せるなら消す。相手は手が少なくとも二つ少ない状態になり負ける。消せない場合は両者の手がすべて 1 本指である。相手の手を一つ 2 本指にすると、相手は手が少なく、かつ 2 本指の手を持つため、一つ少ない場合の例外的な勝ち条件も満たさない。

$m\geq n+2$ ではどの攻撃後も相手の手の方が多く、相手が勝つ。

$m=n+1$ では、手を消さない攻撃後は相手の方が多い。勝つには一つ消して同数にし、次のプレイヤーを同数での負け状態にする必要がある。そのためには自分の手がすべて 1 本指でなければならない。この場合は相手の 2 本指の手しか消せず、相手の 1 本指の手の数は変わらない。よって上記の三条件が必要十分である。

$n=m$ で相手に 2 本指の手がある場合は、相手を一つ少ない場合の負け状態にできる。相手の 2 本指の手が二つ以上なら、その一つを消す。一つしかなく、自分に 2 本指の手があり、相手に 1 本指の手もあるなら、相手の 1 本指の手を消す。自分の手がすべて 1 本指なら相手の 2 本指の手を消せばよい。残る場合は相手の唯一の手を消して直ちに勝てる。

相手の手がすべて 1 本指の場合、自分の 2 本指の手で一つ消す手は $a$ が偶数のときに限り勝ちにつながる。1 本指同士の攻撃は、自分の手もすべて 1 本指で $n$ が偶数のときに限り勝ちにつながる。したがって $a$ が奇数の場合に限り負ける。

小課題 1 は四つの手の個数を状態とするメモ化探索で解ける。各攻撃後に両者の役割を交換する。初期の手数の最大値を $K$ とすると状態数は $O(K^4)$ である。提供実装は順序付きマップを使い、時間は $O(K^4\log(K+1))$、空間は である。 なら十分である。

小課題 2 は、$N>M$ または $N=M$ かつ $N$ が偶数のときに限り先手の勝ちとなる。全体問題では $n=N,m=M,a=a_1,b=b_1$ を上記の条件に代入する。どちらも時間・空間計算量は である。入力と の計算には 64 ビット整数を使う。

各テストケースを独立に処理する。全体の時間は $O(T)$、追加空間は $O(1)$ である。全探索実装はケース間でメモを共有するため、全体の時間は $O(T+K^4\log(K+1))$、空間は である。手を個別に展開しないので、手数の総和に制限は不要である。

Solution written by GPT