ABC483 E - Typo Pairs
- サイト
- AtCoder
- コンテスト
- ABC483
- 問題
- E - Typo Pairs
- 難易度
- 1473
英小文字からなる長さ の文字列が 個与えられます。異なる位置の個数(ハミング距離)が 以下である文字列の組 () を数える問題です(、)。
文字を隠して一致する組を数える
Section titled “文字を隠して一致する組を数える” つの文字列で異なる位置が高々 つなら、その位置を隠すと同じ文字列になります。英小文字には登場しない @ を使い、各文字列から次の文字列を作って個数を数えます。
- 元の文字列
- か所を
@に置き換えた文字列すべて - か所を
@に置き換えた文字列すべて
同じ文字列が 個できたら、それを作る元の文字列の組は 個です。ただし、隠す位置の選び方によって同じ組を何回も数えるので、補正が必要です。
ハミング距離ごとに重複を補正する
Section titled “ハミング距離ごとに重複を補正する”@ が 個ある文字列について を合計した値を とします。ある文字列の組が各 に何回数えられるかは、ハミング距離によって次のようになります。
| ハミング距離 | |||
|---|---|---|---|
距離 なら、異なる か所を隠す方法だけで一致します。距離 なら、異なる位置と、それ以外の か所のいずれかを隠すことで に数えられます。距離 なら、どの位置を隠しても一致します。距離 以上の組は、どこを か所隠しても一致しません。
まず では、距離 の組をちょうど 回数えています。距離 の組も 回にするため、 を引きます。
この時点で距離 の組が数えられる回数は
なので、さらに を足すと、その回数も になります。よって答えは
です。コードでは、作った文字列に含まれる @ の個数に応じて、この係数を掛けています。
各文字列から 個の文字列を作り、コピーやハッシュの計算に かかるので、ハッシュ表の操作が平均的に定数時間で行えるとすると、計算量は です。 なので十分間に合います。
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();}