【AtCoder】ABC 480 B - Invalid Vote

2026-10-20

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 201 / NoviSteps: 5Q / 配点: 200 点

問題概要

選挙に $N$ 人の候補者が立候補している。各候補者の名前は英小文字からなり、互いに異なる。候補者 $i$ の名前は $S_i$ である。

$M$ 枚の投票用紙が投じられ、投票用紙 $j$ には英小文字からなる文字列 $T_j$ が書かれていた。

$T_j$ が名前に完全に一致している候補者がいる場合、その候補者に $1$ 票が入る。そうでなく、 $T_j$ を $1$ 文字書き換えて名前が一致するような候補者がちょうど $1$ 人いる場合、その候補者に $1$ 票が入る。そうでない場合、それは無効票となる。

$i=1,2,\dots,N$ について、候補者 $i$ に何票入るかを求めよ。

制約

$1 \leq N, M \leq 100$
$1 \leq |S_i| \leq 10$
$1 \leq |T_j| \leq 10$
$N$ と $M$ は整数

考察

基本的には言われたことをやるだけ。

以下の処理を正確に実装していこう。

各 $i = 1, 2, \dots, N$ について、 $T_i$ に注目する。
$i$ $i$ を固定したときの各 $j = 1, 2, \dots, N$ $j = 1, 2, \dots, N$ について、 $S_j$ $S_{j}$ と $T_i$ $T_{i}$ を比較する。
1. $S_j = T_i$ ならば、候補者 $j$ に $1$ 票を入れて、次の $T_i$ に進む。
2. そうでない場合、もし $|S_j| \neq |T_i|$ ならば、次の $S_j$ に進む。
3. そうでない場合、 $S_j$ $S_{j}$ と $T_i$ $T_{i}$ の文字列を比較して、異なる文字の個数を数える。
  1. 異なる文字の個数が $1$ ならば、候補者 $j$ を $1$ 票の候補者として記録する。
  2. $1$ 票の候補者が複数いる場合は、無効票として次の $T_i$ に進む。
  3. $1$ 票の候補者がちょうど $1$ 人いる場合は、その候補者に $1$ 票を入れて、次の $T_i$ に進む。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5. 
6.// ======================================== //
7. 
8.int main()
9.{
10.    int N, M;
11.    cin >> N >> M;
12.    vector<string> S(N);
13.    rep(i, 0, N) cin >> S[i];
14. 
15.    vector<int> cnt(N, 0);
16.    rep(i, 0, M) {
17.        string T;
18.        cin >> T;
19. 
20.        int cand = 0, near = 0, exact = -1;
21.        rep(j, 0, N) {
22.            if (S[j] == T) {
23.                exact = j;
24.                break;
25.            }
26. 
27.            if (S[j].size() != T.size()) continue;
28. 
29.            int mismatch = 0;
30.            rep(k, 0, S[j].size()) {
31.                if (S[j][k] != T[k]) {
32.                    mismatch++;
33.                    if (mismatch >= 2) break;
34.                }
35.            }
36. 
37.            if (mismatch == 1) {
38.                cand++;
39.                near = j;
40.            }
41.        }
42. 
43.        if (exact != -1) cnt[exact]++;
44.        else if (cand == 1) cnt[near]++;
45.    }
46. 
47.    rep(i, 0, N) cout << cnt[i] << endl;
48. 
49.    return 0;
50.}