Google Code Jam Round 1A 2019 に参加しました (通過失敗)

Cで貪欲に取ればいいということまではわかっていたが、そこから先の実装をバグらせ続け、visibleすら通せず。priority_queueに突っ込んでがちゃがちゃやってたけど、実装が壊れた。単純に50から順番に走査しても充分間に合うのでそうすべきだった。コンテストのほうは、結局Aのvisibleだけ通して8点。Bは読んですらいないという・・・

Cはhiddenも通したので貼っとく。

int compare(string& a, string& b) {
  int na = a.length();
  int nb = b.length();
  int n = min(na, nb);
  int ret = 0;
  for(int i=0; i<n; i++) {
    if (a[i] == b[i]) {
      ret++;
    } else {
      break;
    }
  }
  return ret;
}

void solve() {
  int n; cin >> n;
  vector<string> vec(n);
  rep(i, n) {
    cin >> vec[i];
  }
  rep(i, n) {
    reverse(vec[i].begin(), vec[i].end());
  }
  sort(vec.begin(), vec.end());

  set<int> st;
  for(int i=0; i<n; i++) {
    st.insert(i);  
  }

  vector<vector<int>> mat(n, vector<int>(n, -1)); // メモ化用

  int pairs = 0;
  for(int len=50; len>0; len--) {
    int pos = -1;
    auto it = st.begin();
    while(it != st.end()) {
      int before = *it;
      it++;
      if (it==st.end()) break;
      int after = *it;
      int cnt;
      if (mat[before][after] != -1) {
        cnt = mat[before][after];
      } else {
        cnt = mat[before][after] = compare(vec[before], vec[after]);
      }
      // 直前にペアにしたものとsuffixが同じになっていないか確認
      if (cnt >= len && (pos == -1 || compare(vec[pos], vec[before]) < len)) {
        pairs++;
        pos = after;
        it--;
        st.erase(it++);
        st.erase(it++);
      }
    }
  }
  cout << pairs*2 << '\n';
}

文字列同士の後ろから見たときの共通の長さをメモ化していたが、メモ化しなくても間に合った。

void solve() {
  int n; cin >> n;
  vector<string> vec(n);
  rep(i, n) {
    cin >> vec[i];
  }
  rep(i, n) {
    reverse(vec[i].begin(), vec[i].end());
  }
  sort(vec.begin(), vec.end());

  set<int> st;
  for(int i=0; i<n; i++) {
    st.insert(i);  
  }

  int pairs = 0;
  for(int len=50; len>0; len--) {
    int pos = -1;
    auto it = st.begin();
    while(it != st.end()) {
      int before = *it;
      it++;
      if (it==st.end()) break;
      int after = *it;
      int cnt = compare(vec[before], vec[after]);
      if (cnt >= len && (pos == -1 || compare(vec[pos], vec[before]) < len)) {
        pairs++;
        pos = after;
        it--;
        st.erase(it++);
        st.erase(it++);
      }
    }
  }
  cout << pairs*2 << '\n';
}