CF Round #732 B - AquaMoon and Stolen String


Tags:cpcodeforcesdiv2string

問題

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 個の文字列から、余った文字列を求めてね。

制約

  • 1t1001 \le t \le 100
  • 1n,m1051 \le n, m \le 10^5
  • nn は奇数
  • nmn \cdot m の総和は 10510^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 について、アルファベットの出現回数は変わらないはず。
最初にあった 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;
}