コンテンツにスキップ

ABC483 E - Typo Pairs

サイト
AtCoder
コンテスト
ABC483
問題
E - Typo Pairs
難易度
1473

英小文字からなる長さ MM の文字列が NN 個与えられます。異なる位置の個数(ハミング距離)が 22 以下である文字列の組 (i,j)(i,j) (i<ji<j) を数える問題です(N≤2×105N \le 2 \times 10^5、2≤M≤62 \le M \le 6)。

文字を隠して一致する組を数える

Section titled “文字を隠して一致する組を数える”

22 つの文字列で異なる位置が高々 22 つなら、その位置を隠すと同じ文字列になります。英小文字には登場しない @ を使い、各文字列から次の文字列を作って個数を数えます。

  • 元の文字列
  • 11 か所を @ に置き換えた文字列すべて
  • 22 か所を @ に置き換えた文字列すべて

同じ文字列が cc 個できたら、それを作る元の文字列の組は (c2)\binom{c}{2} 個です。ただし、隠す位置の選び方によって同じ組を何回も数えるので、補正が必要です。

ハミング距離ごとに重複を補正する

Section titled “ハミング距離ごとに重複を補正する”

@ が kk 個ある文字列について (c2)\binom{c}{2} を合計した値を TkT_k とします。ある文字列の組が各 TkT_k に何回数えられるかは、ハミング距離によって次のようになります。

ハミング距離T2T_2T1T_1T0T_0
22110000
11M−1M-11100
00(M2)\binom{M}{2}MM11

距離 22 なら、異なる 22 か所を隠す方法だけで一致します。距離 11 なら、異なる位置と、それ以外の M−1M-1 か所のいずれかを隠すことで T2T_2 に数えられます。距離 00 なら、どの位置を隠しても一致します。距離 33 以上の組は、どこを 22 か所隠しても一致しません。

まず T2T_2 では、距離 22 の組をちょうど 11 回数えています。距離 11 の組も 11 回にするため、(M−2)T1(M-2)T_1 を引きます。

この時点で距離 00 の組が数えられる回数は

(M2)−M(M−2)\binom{M}{2} - M(M-2)

なので、さらに (M−12)T0\binom{M-1}{2}T_0 を足すと、その回数も 11 になります。よって答えは

T2−(M−2)T1+(M−1)(M−2)2T0T_2 - (M-2)T_1 + \frac{(M-1)(M-2)}{2}T_0

です。コードでは、作った文字列に含まれる @ の個数に応じて、この係数を掛けています。

各文字列から O(M2)O(M^2) 個の文字列を作り、コピーやハッシュの計算に O(M)O(M) かかるので、ハッシュ表の操作が平均的に定数時間で行えるとすると、計算量は O(NM3)O(NM^3) です。M≤6M \le 6 なので十分間に合います。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VS(S, N);
std::unordered_map<str, ll> cnt;
for (str s : S) {
cnt[s]++;
rep(i, M) {
str t = s;
t[i] = '@';
cnt[t]++;
}
rep(i, M) rep(j, i + 1, M) {
str t = s;
t[i] = '@';
t[j] = '@';
cnt[t]++;
}
}
ll ans = 0;
for (const auto &[s, c] : cnt) {
ll k = count(s, '@');
ll pairs = c * (c - 1) / 2;
if (k == 2) {
ans += pairs;
} else if (k == 1) {
ans -= (M - 2) * pairs;
} else {
ans += (M - 1) * (M - 2) / 2 * pairs;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}