Codeforces Round #324 (Div. 2) C. Marina and Vasya

Codeforces Round #324 (Div. 2) に参加しました。結果は 4 完でした。D は問題としては結構面白いと思ったんですが確信を持てないのがちょっと…

問題

codeforces.com

解法

s1, s2 の i 文字目と s3 の i 文字目と, f(s1, s3)(f1 とする) と f(s2, s3)(f2 とする) の関係は以下のようになります。
s1[i] == s2[i] かつ s3[i] == s1[i] -> f1 と f2 は 0 増える
s1[i] == s2[i] かつ s3[i] != s1[i] -> f1 と f2 は 1 増える
s1[i] != s2[i] かつ s3[i] == s1[i] かつ s3[i] != s2[i] -> f2 のみ 1 増える
s1[i] != s2[i] かつ s3[i] != s1[i] かつ s3[i] == s2[i] -> f1 のみ 1 増える
s1[i] != s2[i] かつ s3[i] != s1[i] かつ s3[i] != s2[i] -> f1, f2 は 1 増える

ということで, s1 と s2 のうち, s1[i] != s2[i] を満たす i の数を num とすると, 少なくとも (num+1)/2 以上の値が f1, f2 で出てきます。なので, t がこの値未満の場合は -1 を出力します。

他の場合は, 適当に s3 を調整すれば条件を満たせます。
s1[i] != s2[i] を満たす i の中から, (f1, f2 は 1 増える) をを選ぶ数を決め打ちすると, 他の数も決まっていくのでそれを決定します。だいぶ頭がこんがらがりますが。

void no() {
    cout << -1 << endl;
    exit(0);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, t;
    cin >> n >> t;
    string s1, s2;
    cin >> s1;
    cin >> s2;
    vector<int> diff, same;
    for (int i = 0; i < n; i++) {
        if (s1[i] != s2[i]) diff.push_back(i);
        else same.push_back(i);
    }
    int num = diff.size();
    int can = n-num;
    int least = (num+1)/2;
    if (least > t) no();
    string ans;
    for (int i = 0; i < n; i++) ans += 'e';
    for (int i = least; i <= num; i++) {
        int rest = t-i; // same から違くする数
        if (rest < 0 || rest > can) continue;
        for (int j = 0; j < rest; j++) {
            for (char c = 'a'; c <= 'c'; c++) {
                if (c != s1[same[j]]) ans[same[j]] = c;
            }
        }
        for (int j = rest; j < can; j++) ans[same[j]] = s1[same[j]];
        int snum = num-i;
        for (int j = 0; j < snum; j++) ans[diff[j]] = s1[diff[j]];
        for (int j = snum; j < 2*snum; j++) ans[diff[j]] = s2[diff[j]];
        for (int j = 2*snum; j < num; j++) {
            for (char c = 'a'; c <= 'c'; c++) {
                if (c != s1[diff[j]] && c != s2[diff[j]]) ans[diff[j]] = c;
            }
        }
        cout << ans << endl;
        return 0;
    }
    cout << -1 << endl;
    return 0;
}