問題一覧 > 通常問題

No.2658 L-R Nim

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 18
作問者 : hamamu / テスター : 👑 Nachia てんぷら
3 ProblemId : 10560 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-02-29 02:31:23

問題文

石の山が NN 個あり、 ii 番目の山には石が AiA_i 個あります。
これらの山を使ってAliceとBobがゲームをします。

まずBobが2つの整数 L,RL,R (1≤L≤R≤N)(1 \le L \le R \le N) を選び、 LL 番目から RR 番目までの R−L+1R-L+1 個の山を残してそれ以外の山を取り除きます。
その後、残った R−L+1R-L+1 個の山を使い、Aliceを先手としてNimで勝敗を決めます。
Nimのルールは以下のとおりです：

  • 先手から順に交互に以下の操作を行う
    • 操作：石の山を 11 つ選び、そこから 11 個以上の石を取り除く
  • 操作を行えなくなった方が負け、負けなかった方が勝ち

Aliceはこのゲームに勝ちたいので、Bobがどのような L,RL,R を選んでも勝てるように 以下の細工を一度だけすることにしました。

  • 整数 i(1≤i≤N)i (1 \le i \le N) を 11 つ選び、ii 番目の山に以下の二つの操作のいずれかを行う
    • 石を xx 個加える (0≤x≤K)(0 \le x \le K)
    • 石を xx 個取り除く (0≤x≤min⁡(K,Ai−1))(0 \le x \le \min(K,A_i-1))

Aliceが必ず勝てる細工の仕方が存在するか判定してください。

制約

  • 入力はすべて整数
  • 1≤N≤500001 \le N \le 50000
  • 1≤K≤1001 \le K \le 100
  • 1≤Ai≤1061 \le A_i \le 10^6

入力

以下の形式で標準入力から与えられます。 
N KN\ K
A1 A2⋯ANA_1\ A_2 \cdots A_N

出力

存在する場合はYesを、 そうでない場合はNoを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 1
1 1
出力
Yes

Aliceが 11 番目の山に石を 11 個追加すると A1=2,A2=1A_1=2,A_2=1 になります。 Bobが選択する L,RL,R と、そのときにゲームで使う山の石の個数は以下のとおりです。

  • L=1,R=1L=1,R=1 のとき・・・山の石の個数 (2)(2)
  • L=1,R=2L=1,R=2 のとき・・・山の石の個数 (2,1)(2,1)
  • L=2,R=2L=2,R=2 のとき・・・山の石の個数 (1)(1)
どの場合でもAliceが勝つことができるので、答はYesです。

サンプル2
入力
7 100
10 10 10 10 10 10 10
出力
No

Aliceがどの山に細工しても、 Bobは石の個数 1010 の二つの山が残るよう L,RL,R を選択することができます。 以降Bobは常に二つの山の石の個数が同じになるよう操作することができ、 勝つことができます。よって答はNoです。

サンプル3
入力
5 3
3 1 2 3 6
出力
No
サンプル4
入力
5 6
1 5 4 2 2
出力
No
サンプル5
入力
1 2
3
出力
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。