以下の条件を満たす状態を \(P\) 状態と定義します。

\[m = \min_i A_i, m \equiv 0 \pmod{K}, \sum_i (A_i - m) \lt K\]

\(P\) 状態について以下の 3 個の命題が成り立ちます。

手番で操作を \(K\) 回行えない \(\to\) \(P\) 状態である

操作を \(K\) 回行えない時、石の数は全体で \(K\) 個未満です。これは山の個数より少ないため、山の石の個数が \(0\) 個の山が存在します。よって \(m=0\) かつ \(\sum_i (A_i - m) \lt K\) が成り立ち、状態 \(P\) の条件を満たします。

\(P\) 状態から \(P\) 状態へ移動できない

\(P\) 状態から \(P\) 状態へ移動できると仮定します。
\(P\) 状態の性質として、今の \(P\) 状態の最小値を \(tk\) とした時、\(\sum_i (A_i-tk) \lt K\) という条件から

\[\forall i, tk \leq A_i \lt (t+1)k\]

が成り立ちます。\(1\) 回の手番で \(P\) 状態から \(P\) 状態へ移動できるとした時、必ず石の個数が変化しない山が \(1\) 個以上存在するので、最小値 \(tk\) は不変である必要があります。しかし、移動前に \(\sum_i (A_i-tk) \lt K\) が成り立つことからそのような操作は \(K\) 回行えず、矛盾が発生します。

\(P\) 状態でない状態から必ず \(P\) 状態へ移動できる

現在の最小値を \(m = qK + r, 0 \leq r \lt K\) 、最小値を取る山を \(1\) 個取り \(j\) と置きます。
\(r = 0\) かどうかで場合分けします。
\(r \gt 0\) の場合は山 \(j\) 以外の山の石の個数を \(qK\) まで減らせばよいです。 \(r = 0\) の場合は、山 \(j\) を変更せずそれ以外の山を \(m\) まで減らせばよいです。(元々の状態は \(P\) 状態でないため \(\sum_i (A_i - m) \geq K\) が成り立つことから、適切に操作すれば達成可能です。)
よっていずれの場合も \(P\) 状態へ移動できました。

以上より

• 手番を完遂できない \(\to\) \(P\) 状態である
• \(P\) 状態から \(P\) 状態へ移動できない
• \(P\) 状態でない状態から必ず \(P\) 状態へ移動できる

ことが示されました。よって \(P\) 状態がちょうど手番側の負け状態であることが示されました。簡単に説明すると、\(P\) 状態でない状態で手番が回ってくるプレイヤーは \(P\) 状態へ移動することが必勝戦略となります。初期状態が \(P\) 状態かどうかは \(\mathrm{O}(K)\) で計算できます。

• 実装例(C++)

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int T;
  cin >> T;
  while (T--) {
    int K;
    cin >> K;
    vector<int> A(K + 1);
    for (auto& a : A) cin >> a;
    int m = *min_element(begin(A), end(A));
    long long S = 0;
    for (auto& a : A) S += a - m;
    if (m % K == 0 && S < K) {
      cout << "Bob" << "\n";
    } else {
      cout << "Alice" << "\n";
    }
  }
}