問題
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; }