ARC038 C. 茶碗と豆

その他 過去問

問題

N個の茶碗が並んでおり、茶碗iには豆がA[i]個と、整数C[i]が書かれている。
ただし、C[0]は書かれておらず、A[0]=0。

2人のプレイヤーが豆を一つ選んで、その豆が入っている茶碗iから、茶碗(i-1)〜(i-C[i])のどれかに移す、ということを繰り返す。茶碗0に入った豆はそこから動かすことはできない。
交互に繰り返した場合、自分のターンで選べる豆がなくなったプレイヤーが負けとなる。

2人が最適戦略で勝ちを目指した場合、どちらのプレイヤーが勝つか、答える。

2<=N<=10^5
1<=C[i]<=i
0<=A[i]<=10^9

考え方

解説ガン見。
2人で交互に状態を推移させ、引き分けなくどちらかが勝つことが決まるようなゲームでは、「grundy数」というゲームの状態に番号を付ける方法で最適解を得られる。


豆が全体で1つの場合を考え、豆がjにある場合、「そこから移動できる状態のgrundy数に無い非負整数」をgrundy[j]とする。
豆がi=0にある場合は最終状態なのでgrundy[0]=0とし、再帰的に求めることができる。
すると、grundy[j]!=0となっているところでは次に0となる状態に移すことができるので、相手を負けさせることができる、ということがわかる。
grundy[現在の状態]=0ならば、先手の負け、0以外の整数ならば先手が勝てる。
さらに、grundy数には、ゲームを平行で進行する場合は、各状態のgrundy数のxorを取ることでゲーム全体でのgrundy数を求めることができる、という特徴がある。


grundy数を使うと、この問題を解くことができる。
豆が1つだけある場合を考えてgrundy数を求めておく。
複数豆があるが、それぞれ別のゲームを平行に進行していると考えられるので、すべての豆に対してgrundy数のxorを取ったものが答えになる。


上記の制約の場合、「xorを高速に取る」ことと、「grundy数を高速に求める」ことが求められる。


豆の数が全部で10^14程度ありえるので、1つずつxorを取っていては間に合わない。
しかし、xorの性質として、「A xor A = 0」になることから、A[i]がいくら多くても、偶数ならば0、奇数ならばgrundy[i]になるので、A[i]の大きさは関係なくなる。


茶碗の数が10^5あるので、愚直な方法でgrundy数を求めると間に合わない。
今回のゲームの場合は、ゲーム状態を列として考えることができ、かつ、遷移できる状態はある範囲になっていることを利用する。
「整数iがgrundy数として使われた一番最後のインデクス」を持つ配列vを用意する。すると、この配列において0〜Kの範囲で一番小さいインデクスがi-C[i]未満となる最小のKの値が求められるとそのKが
(i-C[i])〜(i-1)で使われていない最小の非負整数となっている。
「0〜Kの範囲で一番小さいインデクス」はRMQ(SegTree)で求められ、「i-C[i]未満の最小K」は二分探索で求められる。

反省

RMQに二分探索を実装してなかったので、RMQと二分探索を分けてO(log N * log N)で計算したけど、これでも特に問題なさそう。
配列vを二分探索のために-1〜Nに範囲を拡張し、この範囲を探索する。

  RMQ rmq(N+1); //配列vのRMQを考えるが、-1を含めるために、インデクス全体を+1して扱う(二分探索でlbが必ず条件を満たし、ubが必ず条件を満たさない、という状態を作るため)
  
  grundy[0] = 0;
  rmq.update(0, INF); //v[-1] = INF
  rmq.update(1, 0); //v[0] = 0

  REP(i,1,N){
    //二分探索でi-C[i]未満となるとなる最小のKを求める
    int lb = 0, ub = N+1;
    while(ub-lb>1){
      int mid = (lb+ub)/2;
      if(rmq.query(0,mid+1) < i-C[i]) ub = mid; //v[-1]以上v[mid]未満での最小インデクス
      else lb = mid;
    }
    rmq.update(ub, i); //v[ub-1] = i

    grundy[i] = ub-1;
  }