Educational Codeforces Round 34 E. Swapping Characters

公式解説をベースにした詳細な解説をします

解説

計算量の考察

最初に計算量についての考察をしておきます.

  •  1 \leq k \leq 2500
  •  2 \leq n \leq 5000
  •  k \cdot n \leq 5000

一見すると  O(kn) しか許されないように見えますが,3 番目の制約を考慮すると  O(k^{2}n) もしくは  O(kn^{2}) が許されることが分かります.

愚直解

素直に全探索することを考えてみます.

ある文字列における任意の文字ペアをスワップして得られる文字列は  n(n+1)/2 個あります.これをオリジナルの文字列  s だと仮定して,残りの文字列とそれぞれ突き合わせて差分を確認することで答えを得られますが,計算量は  O(kn^{3}) となり TLE します.

また,文字列ごとに  n(n+1)/2 個の文字列を列挙して連想配列などで数え上げる方法も考えられますが( k 回出現した文字列が答えとなる),この方法だと MLE します(しました).

想定解

愚直解の前者の計算量を改善することで解くことができます.

面倒ですが,真っ先に文字列の検証を行う必要があります.文字列  s_{1}, ..., s_{k} はオリジナルの文字列  s から 1 回のスワップで得られる文字列であるため,当然ながら文字列を構成する各文字の個数は一致するべきですが,その保証はないので確認する必要があります.それが満たされていなければ  -1 が答えです.サンプル 3 がまさにこのケースとなっています.計算量は  O(kn) です.

異なる文字列ペア  (s_{x}, s_{y}) を探索して 1 つ見つけます.これが見つからなければ全体で文字列は 1 種類しかないということですから,適当に文字ペアをスワップすれば答えになります( k = 1 のときもまとめて処理できるような実装にしておく).計算量は  O(k^{2}n) です.

異なる文字列ペア  (s_{x}, s_{y}) において, s_{x,p} \neq s_{y,p} なるインデックス  p を探索して配列  pos に格納します.例えば, s_{x} = "abcd",  s_{y} = "aacc" のとき  pos = \{1, 3\} です(0-indexted).このとき, pos のサイズ  \mathrm{size}(pos) が 4 を越えていた場合は辻褄が合わなくなるため  -1 が答えです(オリジナルの文字列  s におけるスワップ位置を上手く選んだとしても,2 つの文字列の違いは高々 4 文字にしかなり得ないため).

 diffpos \in pos を順に取り出し, s_{x} における  diffpos 以外の任意の位置とスワップして得られる文字列  t を考えます.このような文字列  t \mathrm{size}(pos) \cdot (n-1) 個あり,その全てが答えの候補となります.よって,ある文字列  t と各文字列  s_{i} (i \neq x) を突き合わせて一つも矛盾が生じなければそのときの文字列  t が答えになり,すべての文字列  t で矛盾が生じたら  -1 が答えになります.計算量は  O(kn^{2}) です.

文字列を突き合わせたときの確認方法ですが,オリジナルの文字列  s から 1 回だけスワップした際,同じ文字同士であれば 0 箇所,違う文字同士であれば 2 箇所の差分が発生します.つまり,文字列  t と各文字列  s_{i} (i \neq x) の差分  diff をそれぞれ数え上げて  0, 2 にならなければ NG です.さらに, diff = 0 のときは「同じ文字同士のスワップ」が必要になるため,ある文字が 2 個以上含まれていることが要請されることに注意してください(どの文字列も各文字の個数が一致することは事前に確認済みなので,適当な一つの文字列においてある文字が 2 個以上含まれていることも事前に確認しておくと効率的です).

愚直解では文字列  t の候補が  n(n+1)/2 個でしたが,配列  pos を持ち出したことで高々  4(n-1) 個となりオーダーが落ちて全体で  O((k+n)kn) に改善されています.これでもギリギリに見えますが,要所で枝刈りが効くので割と余裕があります.

所感

丁寧な考察と実装が必要で,見た目以上に難しい問題でした.
個人的には問題の文字定義が非直感的で実装がやりづらかったです.

解答例

https://codeforces.com/contest/903/submission/112423089

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
 
    ll K, N; cin >> K >> N;
    VS S(K); REP(i,K) cin >> S[i];
 
    // check
    VLL cnt(26,0);
    REP(p,N) cnt[S[0][p] - 'a']++;
    FOR(i,1,K) {
        VLL tmp(26,0);
        REP(p,N) tmp[S[i][p] - 'a']++;
        REP(c,26) if (cnt[c] != tmp[c]) { COUT(-1); return 0; }
    }
 
    bool all_char_diff = true;
    REP(c,26) if (cnt[c] >= 2) all_char_diff = false;
 
    // search s_x != s_y
    ll x = -1, y = -1;
    [&]() -> void {
        REP(i,K-1) FOR(j,i+1,K) {
            if (S[i] != S[j]) { x = i; y = j; return; }
        }
    }();
    if (x == -1) { swap(S[0][0], S[0][1]); COUT(S[0]); return 0; }
 
    VLL pos;
    REP(p,N) if (S[x][p] != S[y][p]) pos.push_back(p);
    if (SZ(pos) > 4) { COUT(-1); return 0; }
 
    string& t = S[x];
    for (ll diffpos : pos) {
        REP(p1,N) if (p1 != diffpos) {
            bool ok = true;
            swap(t[p1], t[diffpos]);
            REP(i,K) if (i != x) {
                ll diff = 0;
                REP(p2,N) if (S[i][p2] != t[p2]) diff++;
                if (diff != 0 && diff != 2) { ok = false; break; }
                if (diff == 0 && all_char_diff) { ok = false; break; }
            }
            if (ok) { COUT(t); return 0; }
            swap(t[p1], t[diffpos]);
        }
    }
    COUT(-1);
 
    return 0;
}