ARC229 D - Nim_k ?

考え方

Nim ではあるのだが、ルールがかなり特殊であるため、普通の Nim の勝敗判定は使えない。
バックトレースで、決着状態から考えていく。

まず、$1$ ターン目でもう先手が負けるパターンを考える。
とりあえず自ターンを消化するだけ考えるなら、石を $1$ 個取ることを $K$ 回繰り返せばよい。
それすら不可能な状況というのは、石の個数合計が $K$ 個未満ということである。
逆に、石の個数合計が $K$ 以上あるならこのターンはしのげる。

ΣA[i] が K 未満なら、先手負け

続いて、$2$ ターンで決着する場合を考える。
これは、$1$ ターン負けの形にできる状況全部である。
つまり、石の数が $K$ 個以上あり、どこかの山が $K$ 個未満という状況である。
その $K$ 個未満の山以外を全部取ってしまえばよい。

ΣA[i] が K 未満なら、先手負け
ΣA[i] が K 以上、かつ、K 未満の山があるなら、先手勝ち

続いて、$3$ ターンで決着する場合を考える。
これは、どうやっても先手勝ちの形になってしまう状況である。
そもそも全ての山が $K$ 以上ある状況で、各山の $K$ 個を超える余剰分合計が $K$ 未満である場合である。
手をつけなかった山だけで $K$ 個以上あるし、絶対に $K$ 個未満の山ができてしまう。

ΣA[i] が K 未満なら、先手負け
ΣA[i] が K 以上、かつ、K 未満の山があるなら、先手勝ち
全ての山が K 以上、かつ、Σ(A[i]-K) が K 未満なら、先手負け

以下、繰り返すと、帰納的に以下のようになる。

最小個数の山に $m$ 個あるとし、この $m$ 以下で最大の $K$ の倍数を基準個数とする。
基準個数からの余剰分が、合計 $K$ 個以上あれば先手の勝ち、$K$ 個未満であれば後手の勝ち。

計算量は $1$ ケース当たり $O(K)$ である。

入力例1での動作

入力例1には $3$ 個のテストケースがある。

まず、$1$ 番目のテストケースを考える。

入力を受け取る。

k: 2
a: {1, 2, 3}

最小値は $1$ なので、これ以下で最大の $K=2$ の倍数は $0$ である。
したがって基準個数を $0$ とすると、余剰分の合計は $1+2+3=6$ となる。
これは $K=2$ 以上なので、Alice の勝ちである。

次に、$2$ 番目のテストケースを考える。

入力を受け取る。

k: 1
a: {4, 4}

最小値は $4$ で、これ以下で最大の $K=1$ の倍数も $4$ である。
したがって基準個数を $4$ とすると、余剰分の合計は $(4-4)+(4-4)=0$ となる。
これは $K=1$ 未満なので、Bob の勝ちである。

最後に、$3$ 番目のテストケースを考える。

入力を受け取る。

k: 9
a: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

最小値は $1$ なので、これ以下で最大の $K=9$ の倍数は $0$ である。
したがって基準個数を $0$ とすると、余剰分の合計は $1+2+\cdots+10=55$ となる。
これは $K=9$ 以上なので、Alice の勝ちである。

よって、順に Alice, Bob, Alice となる。

注意点

石の個数の合計は int 型からはみ出る。
long long 型を用いること。

別解

特になし。