コンテンツにスキップ

ABC480 B - Invalid Vote

サイト
AtCoder
コンテスト
ABC480
問題
B - Invalid Vote
難易度
201

NN 人の候補者がいて、候補者 ii の名前は SiS_i です(名前はすべて異なります)。MM 枚の投票用紙があり、投票用紙 jj には文字列 TjT_j が書かれています。各投票用紙は次のように扱われます。

  • TjT_j と名前が完全に一致する候補者がいれば、その候補者に 1 票入る。
  • そうでなく、TjT_j を 1 文字書き換えると名前が一致する候補者がちょうど 1 人いれば、その候補者に 1 票入る。
  • どちらでもなければ無効票になる。

各候補者の得票数を求める問題です(1≤N,M≤1001 \le N, M \le 100、1≤∣Si∣,∣Tj∣≤101 \le |S_i|, |T_j| \le 10)。

書かれているとおりに調べます。

「TjT_j を 1 文字書き換えると SiS_i に一致する」は、TjT_j と SiS_i の長さが等しく、異なる文字の位置がちょうど 1 か所であること(ハミング距離が 11 であること)と同じです。完全に一致する候補者がいないときは、この条件を満たす候補者を数え、ちょうど 1 人ならその人に 1 票を入れます。

計算量は、名前の長さの最大値を LL として O(NML)O(NML) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/string/string.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VS(S, N);
VS(T, M);
vl ans(N);
for (str t : T) {
if (contains(S, t)) {
ans[index(S, t)]++;
continue;
}
vl cand = indices_if(S, [&](str s) { return len(t) == len(s) && hamming_distance(t, s) == 1; });
if (len(cand) == 1) {
ans[cand[0]]++;
}
}
for (ll a : ans)
print(a);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

contains(S, t) は S に t が含まれるか、index(S, t) はその位置を返します。indices_if は条件を満たす要素の位置をすべて集めた列を返し、hamming_distance は長さの等しい 2 つの文字列で異なる文字の個数を返します。hamming_distance は長さが等しいことを前提にしているので、先に len(t) == len(s) を確かめています。

使用ライブラリ:cpp_include@9c33ee7