B - AquaMoon and Stolen String

問題

https://codeforces.com/contest/1546/problem/B (新しいタブで開く)

問題文

$n$ 個の $m$ 文字からなる文字列から、2 つの要素からなる $\frac{n-1}{2}$ 個のペアを作ると、 $1$ 個余った。
それぞれのペアを $(s, t)$　に対して、 $i$ をいくつか選んで $\mathrm{swap}(s_i, t_i)$ とした。
swap 前の $n$ 個の文字列と、ペアを成した $n-1$ 個の文字列から、余った文字列を求めてね。

制約

• $1 \le t \le 100$
• $1 \le n, m \le 10^5$
• $n$ は奇数
• $n \cdot m$ の総和は $10^5$ を超えない

サンプル

3
3 5
aaaaa
bbbbb
ccccc
aaaaa
bbbbb
3 4
aaaa
bbbb
cccc
aabb
bbaa
5 6
abcdef
uuuuuu
kekeke
ekekek
xyzklm
xbcklf
eueueu
ayzdem
ukukuk

ccccc
cccc
kekeke

考察

それぞれの index について、アルファベットの出現回数は変わらないはず。
最初にあった $n$ 個 と 残された $n-1$ 個それぞれのグループで、各 index におけるアルファベットの出現回数を数える。
1 つだけ出現回数が異なるアルファベットがあるはずで、それが余った文字。

コード

https://codeforces.com/contest/1546/submission/122079157 (新しいタブで開く) (見づらい)

https://codeforces.com/contest/1546/submission/183294937 (新しいタブで開く) (改良版)

void solve() {
  int n, m;
  cin >> n >> m;
  vector cnt1(m, vector<int>(26, 0));
  vector cnt2(m, vector<int>(26, 0));
  rep(i, n) {
    string s;
    cin >> s;
    rep(j, m) cnt1[j][s[j] - 'a']++;
  }
  rep(i, n - 1) {
    string s;
    cin >> s;
    rep(j, m) cnt2[j][s[j] - 'a']++;
  }
  rep(i, m) {
    rep(j, 26) {
      if (cnt1[i][j] != cnt2[i][j]) {
        cout << (char) ('a' + j);
        break;
      }
    }
  }
  cout << endl;
  return;
}