テーマ別競プロ勉強会3

Grundy数の導入はこの前書きましたが、まとまりが悪く、また応用問題の話が無かったのでまとめます。

Grundy数とは

• 各盤面の状態に対応する数値である
• 0が負け、1以上が勝ち
• Grundy数は次の盤面のGrundy数として取り得ない最小の整数
• 言い換えると、次の手でそのGrundy数未満の数に遷移できる
• 複数の盤面のGrundy数は各盤面をxor取ったもの

かなり抽象的ですね。これで、どうやって勝つのかというと、相手のターンに全体の盤面のGrundy数が0となるように調整すればいいです。そのような取り方が存在するのか怪しい所ですが、Nimと同じく証明できます。

例えば山が3つあって、Grundy数が2進数で100, 11, 10の時、この山のGrundy数は101ですね。この中で最も大きい要素(100)を全体のGrundy数(101)にxorかけたもの(100 xor 101 = 1)に変化させると良いです。そのような値は元の数より小さい事はすぐ分かるので可能です。

何故そのような事が思いつけたのかは前回の記事を読んで下さい。本質的な部分はGrundy数は場合によっては増やすように遷移できるが、そのような事をするメリットは無いという部分です。

また、複数の盤面のGrundy数をxorでマージできるという性質はとても有効で、盤面が段々増えていく問題(例えば紙を切ってバラバラにするとか)で使えます。

茶碗と豆

ARC038 Cです。

これの初期位置によって独立にgrundy数を求め、それをxorしていけば良いのはすぐ気づくかと思います。また、Aの値は0か1に帰着させれる事もすぐ分かります(2以上の時は真似っ子戦略がとれます、別な言い方をするとx xor x = 0なので)

すると100/104はとれます。これは簡単です。これが出来ないならgrundy数が理解出来ていないので復習して下さい。

残りの4点はそこそこ難しいです。Segment Treeを使えば良さそうですが、単にGrundy数のSegment Treeでは不十分です。もしこの方針でいくなら集合を全て持つ必要がありなかなか大変そうです。

逆の視点で考えましょう。各Grundy数となるような地点を考えるのはどうでしょうか。この問題は左から順番に入れていき、右側は固定されているので、各Grundy数に対する一番右側の地点のみを記録すればいいですね。

そのような配列に対してi-Ci未満の地点が入っているようなGrundy数が答えとなります。これはSegment Tree上での二分探索なので普通に実装してO(n (log n)^2)、効率的に実装するとO(n log n)となります。ちなみにO(n (log n)^2)でも間に合います。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>
using namespace std;

typedef long long ll;
const ll INF = 1LL << 60;

template <typename T>
class SegmentTree {
  ll n;
  vector<T> node;
  function<T(T, T)> fun, fun2;
  bool customChange;
  T outValue, initValue;
public:
  void init(ll num, function<T(T, T)> resultFunction, T init, T out, function<T(T, T)> changeFunction = NULL) {
    // changeFunction: (input, beforevalue) => newvalue
    fun = resultFunction;
    fun2 = changeFunction;
    customChange = changeFunction != NULL;
    n = 1;
    while (n < num) n *= 2;
    node.resize(2 * n - 1);
    fill(node.begin(), node.end(), init);
    outValue = out;
    initValue = init;
  }
  void valueChange(ll num, T value) {
    num += n-1;
    if (customChange) node[num] = fun2(value, node[num]);
    else node[num] = value;
    while (num > 0) num = (num - 1) / 2, node[num] = fun(node[num * 2 + 1], node[num * 2 + 2]);
  }
  T rangeQuery(ll a, ll b, ll l = 0, ll r = -1, ll k = 0) { // [a, b)
    if (r == -1) r = n;
    if (a <= l && r <= b) return node[k];
    if (b <= l || r <= a) return outValue;
    ll mid = (l + r) / 2;
    return fun(rangeQuery(a, b, l, mid, 2*k+1), rangeQuery(a, b, mid, r, 2*k+2));
  }
};

ll n, c[100001], a[100001], grundy[100001], ans;
SegmentTree<ll> sgt;
ll lmin(ll a, ll b) { return min(a, b); }

ll get(ll x) {
  ll lb = 0, ub = n+1;
  while (lb + 1 < ub) {
    ll mid = (lb + ub) / 2;
    if (sgt.rangeQuery(0, mid) >= x) lb = mid;
    else ub = mid;
  }
  return lb;
}

int main() {
  scanf("%lld", &n);
  for (ll i = 1; i <= n; i++) scanf("%lld%lld", &c[i], &a[i]), a[i] %= 2;
  sgt.init(n+1, lmin, -1, INF);
  sgt.valueChange(0, 0);
  for (ll i = 1; i <= n; i++) {
    ll g = get(i - c[i]);
    grundy[i] = g;
    if (a[i]) ans = ans xor g;
    sgt.valueChange(g, i);
  }
  if (ans == 0) printf("Second\n");
  else printf("First\n");
}

Game on Tree

AGC017 Dです。

これ、1100点問題ですけどそこまで難しくありません。上記の理論が完全に理解出来ていれば500点問題くらいじゃないかなと思います。考えましょう。

...

今回注目すべきは辺なので少しややこしいです。ここで各頂点に対して、それより上の部分を削って、その頂点(以降Vと呼びます)が根となる根付き木のgrundy数を定義します。

もし、Vが末端で子が無い時は...これは負けの状態ですね。grundy数は0です。

Vの子が1つで子のgrundy数がaの時、Vのgrundy数は何になるでしょうか。子の木がどのような構造であれこれは必ず先手が勝つのでgrundy数は1以上です。なんとなく、grundy数はa+1になりそうな感じがしませんか？実際これは正しいです。

これが正しい軽い説明をします。とりあえずそのような形でgrundy数を定義します。すると、子のgrundy数をx(1<=x<=a)減らす操作はVのgrundy数をx減らす事になり、Vのgrundy数をa+1個減らす操作は親子を結ぶ辺を切る操作に当たり、grundy数が満たすべき性質は満たしているからです。(証明問題なら0点ですね。これの説明難しい)

前回の話に帰着させると、grundy数はk-完全DAGに帰着させる事が出来ます。子と親を結ぶ辺は必勝法(1-完全DAGに相当)になり、その分1個ずれる感覚があれば簡単に思いつけると思います。

後はやるだけです。子のgrundy数を求めて、それに+1したものをxorするのを再帰的に繰り返せば解けます。

#include<cstdio>
#include<vector>
using namespace std;

typedef long long ll;

ll n, x, y;
vector<ll> e[100000];

ll dfs(ll x, ll par) {
  ll ans = 0;
  for (ll i : e[x]) if (i != par) {
    ans = ans xor (dfs(i, x) + 1);
  }
  return ans;
}

int main() {
  scanf("%lld", &n);
  for (ll i = 0; i < n-1; i++) {
    scanf("%lld%lld", &x, &y);
    x--; y--;
    e[x].push_back(y);
    e[y].push_back(x);
  }
  printf("%s\n", dfs(0, -1) == 0 ? "Bob" : "Alice");
}