AtCoder Regular Contest 087 E - Prefix-free Game

問題ページ
E - Prefix-free Game

考えたこと

• ゲームと言われたのでサンプルについてWin-Loseの探索木を書いてみるがよくわからない
• 01文字列なのでtrie木を書いてみると葉を通らないような位置に頂点を追加する問題に言い換えられることがわかった
• 木上のゲームでgrundy数っぽい感じがしたのでdeforestation を思い出すと同じgrundy数の定義でいける気持ちになったので書く
• trieを書いたことがなかったので手間取っていると終了10分前になっている。サンプルを試すと落ちた。
• trieをバグらせているのかとか色々確認してたらコンテスト終わった
  ----解説を見た----
• trie書いてgrundy数まではあってたけどgrundy数の求め方が間違っていた
• 冷静に考えると操作が別物だし何で同じgrundy数の求め方だと思ってしまったのか謎

学び

• bitのTrie木(完全二分木)のライブラリをつくった
• 解説放送を見たらgrundy数の問題は考えてどうにかなるものではないのでとにかく実験しろと言っていたので今度からそうする
• それっぽい法則を見つけた気分になったときに合ってるか確かめずに実装に入っちゃうのを直す

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define PB push_back

/*
完全二分木
v[now].lch = v.size(); v.PB(node(v[now].d+1)); now = v[now].lch;  // 左に追加
v[now].rch = v.size(); v.PB(node(v[now].d+1)); now = v[now].rch;  // 右に追加
*/
struct node {
  int d, lch, rch;
  node() {lch=rch=d=-1;}
  node(int d):d(d){lch=rch=-1;}
};
vector<node> v;

int n, l, ans;
string s[100010];

signed main(void)
{
  cin >> n >> l;
  REP(i, n) cin >> s[i];

  v.PB(node(0));
  REP(i, n) {
    int now = 0;
    REP(j, s[i].size()) {
      if(s[i][j] == '0') {
        if(v[now].lch != -1) now = v[now].lch;
        else {
          v[now].lch = v.size();
          v.PB(node(v[now].d+1));
          now = v[now].lch;
        }
      } else {
        if(v[now].rch != -1) now = v[now].rch;
        else {
          v[now].rch = v.size();
          v.PB(node(v[now].d+1));
          now = v[now].rch;
        }
      }
    }
  }

  int ret = 0;
  for(auto i: v) {
    if(i.lch == -1 && i.rch == -1) continue;
    if(i.lch == -1 || i.rch == -1) ret ^= (l-i.d)&(i.d-l);
  }

  if(ret) cout << "Alice" << endl;
  else cout << "Bob" << endl;

  return 0;
}