ABC480 B - Invalid Vote
人の候補者がいて、候補者 の名前は です(名前はすべて異なります)。 枚の投票用紙があり、投票用紙 には文字列 が書かれています。各投票用紙は次のように扱われます。
- と名前が完全に一致する候補者がいれば、その候補者に 1 票入る。
- そうでなく、 を 1 文字書き換えると名前が一致する候補者がちょうど 1 人いれば、その候補者に 1 票入る。
- どちらでもなければ無効票になる。
各候補者の得票数を求める問題です(、)。
書かれているとおりに調べます。
「 を 1 文字書き換えると に一致する」は、 と の長さが等しく、異なる文字の位置がちょうど 1 か所であること(ハミング距離が であること)と同じです。完全に一致する候補者がいないときは、この条件を満たす候補者を数え、ちょうど 1 人ならその人に 1 票を入れます。
計算量は、名前の長さの最大値を として です。
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