B - AquaMoon and Stolen String

cpcodeforcesdiv2string

最終更新日

Table of Contents

Loading...

問題

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

問題文

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

制約

サンプル

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 について、アルファベットの出現回数は変わらないはず。
最初にあった nn 個 と 残された n1n-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; }