yukicode No.8 N言っちゃだめゲーム

問題

昔，古畑任三郎というドラマの中で古畑さんが犯人とやっていたのを見たのが，私のこのゲームとの初めての出会いであった。詳細は以下。

No.8 N言っちゃダメゲーム - yukicoder

考察１（後ろから考える）

n=30,k=5だとしよう。

1からはじめていって，5以下の数字を交互に宣言し，30を宣言した方が負けである。相手に30を宣言させれば勝ちともいえる。ということは29を自分が宣言すれば勝ちである。29を自分が宣言するためには，24～28のいずれかで自分に回ってくれば，29を宣言できるので勝ちである（k=5なので，24->5，25->4，というように1～5の中から適切な数字を選ぶことで29を宣言することが可能）。

この考察を１までずっとさかのぼっていけば答えは導けるが，もう少し考察を進めよう

考察２（最初にさかのぼっていく）

考察を続ける。29を宣言するために，24～28で自分のターンにしたいので，23で相手のターンにすれば，相手は24～28のいずれかしか宣言することができない。つまり23を自分が宣言すればよい。

では，23を宣言するためには，23-1～23-5つまり，22～18のいずれかで自分のターンであればよい。つまり17で相手のターンにすればよいので，自分が17を宣言すればよい。

これを続けると，29,23,17,11,5のいずれかを自分が宣言すれば勝つことできるとわかる。このリストの最初は5であり，先行の自分は初手で5を宣言することができるので，n=30,k=5のときは勝利することができる。

考察3（一般化）

nを宣言させるためには，n-1を自分が宣言すればよい。n-1を宣言するためには，最大でもn-k-2で相手にまわせばよい（相手は最大でもn-k-2+k=n-2しか宣言できず，そのあとで自分はn-1を宣言できる）。したがって，自分はn-k-2を宣言すればよい。同様に，n-k-2を宣言するためにはn-2k-3で相手に回すために，n-2k-3を宣言すればよい。

まとめ

宣言したときに勝てる数字
n-1
n-k-2 = n-(k+1)-1
n-2k-3 = n-2(k+1)-1
n-3k-4 = n-3(k+1)-1
,,,,,
n-i(k+1)-1

先攻のプレイヤーには0が与えられるということは，相手が0を宣言したことと同じである。したがって，n-i(k+1)-1=0となるiが存在するときに自分は負け，そうでないとき勝ちとなることがわかる。この式を整理すると

n-1=i(k+1)となるので，求める条件は(n-1)%(k+1)==0とすればよい。

以下，提出したコード

P = int(input())
for _ in range(P):
   n,k = map(int,input().split())
   if n <= k:
       ans = "Win"
   elif (n-1)%(k+1)==0:  #n%(k+1) == 1:でもよい
       ans = "Lose"
   else:
       ans = "Win"
   print(ans)