問題
https://codeforces.com/contest/1546/problem/B (新しいタブで開く)
問題文
個の 文字からなる文字列から、2 つの要素からなる 個のペアを作ると、 個余った。
それぞれのペアを に対して、 をいくつか選んで とした。
swap 前の 個の文字列と、ペアを成した 個の文字列から、余った文字列を求めてね。
制約
- は奇数
- の総和は を超えない
サンプル
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 について、アルファベットの出現回数は変わらないはず。
最初にあった 個 と 残された 個それぞれのグループで、各 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;
}