ABC268-G Random Student ID

問題

atcoder.jp

N 人の新入生がいて、それぞれの名前が英小文字で与えられる。学籍番号は英小文字の順序に従って辞書順で並べたときの順番で 1-indexed に振られる。 英小文字の順序をランダムに定義したとき、学籍番号の期待値は？

解法

例えば abc という文字列を考えた時、英小文字の順序に依らず ab よりは辞書順で後に振られることになる。また、 abcd よりは前に振られる。これらの順序は「その文字列が他の文字列を接頭辞として含んでいるか、またその文字列が他の文字列の接頭辞として含まれているか」によって決められる。 M 個の文字列の集合に対していずれのペアもこの関係を満たさない時は、集合の 1, \dots, M 番目になるかが等確率に決まる。

以上の性質を踏まえると、ある文字列集合 S に含まれる文字列 T \in S が S 内で何番目になりうるかは、 S 内で T が T 以外で接頭辞として含む文字列の個数を X_T、 T 以外に T を接頭辞として含む文字列の個数を Y_T とすると、 T より前に少なくとも X_T 個、後ろに少なくとも Y_T 個並ぶはずなので、

X_T + 1, X_T + 2, \dots, N - Y_T

のいずれかであり、これらの内から一つが等確率で与えられるので求める期待値は

\frac{(X_T + 1) + (X_T + 2) + \dots + (N - Y_T)}{(N - Y_T) - (X_T + 1) + 1} = \frac{\frac{((N - Y_T) - (X_T + 1) + 1) ((X_T + 1) + (N - Y_T)}{2}} {(N - Y_T) - (X_T + 1) + 1} = \frac{X_T + 1 + N - Y_T}{2}

X_T, Y_T は文字列集合 S を最初にソートしておき文字列 T \in S を前から順に取り出していくことにして、接頭辞 U が T を調べるより前に出てきていれば Y_U, X_T をそれぞれインクリメントすることで求められる。

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;

int main() {
  // 入力　S0 に元の順序を持っておくことにしてソートしておく
  int N; cin >> N;
  vector<string> S(N); for (int i = 0; i < N; i++) cin >> S[i];
  const auto S0 = S;
  sort(S.begin(), S.end());
  
  // 文字列 T について、T の接頭辞でありかつ S 内に含まれる文字列の個数 X[T] と、T を接頭辞として含みかつ S 内に含まれる文字列の個数 Y[T] の計算　ソートしておいた順番に計算
  map<string, int> X, Y;
  for (string T : S) {
    string U = "";
    for (char x : T) {
      U += x;
      if (Y.find(U) != Y.end()) {
        X[T]++;
        Y[U]++;
      }
    }
    Y[T] = 0;
  }
  
  // 答えを出力
  using mint = atcoder::modint998244353;
  const mint inv2 = mint(1) / 2;
  for (string T : S0) {
    mint ans = mint(X[T] + 1 + N - Y[T]) * inv2;
    cout << ans.val() << '\n';
  }
  
  return 0;
}

感想

trie 木について何も知らなかったし、今も分かっていないが、解けた。 初めてコンテスト中に ABC-G を通せたので嬉しい。