ARC 151

Fri, Aug 1, 2025

A. Equal Hamming Distances

https://atcoder.jp/contests/arc151/tasks/arc151_a

自力 AC.

文字列 $X, Y$ のハミング距離を $d(X, Y)$ とする。はじめ $U = 0\cdots0$ で初期化し、位の小さい方から $i$ 桁目を変えたときに $|d(S, U) - d(T, U)|$ が小さくなるならそれを採用、そうでなければそのままにするということを繰り返す。 $|d(S, U) - d(T, U)|$ が 0 になったら終了。0 にならなかったら -1 を出力。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    string S, T;
    cin >> S >> T;

    string U = string(N, '0');
    reverse(all(S));
    reverse(all(T));

    ll sd = 0, td = 0;
    rep(i, N) {
        sd += S[i] != U[i];
        td += T[i] != U[i];
    }
    if (sd == td) {
        cout << U << endl;
        return;
    }

    int ok = 0;
    rep(i, N) {
        ll tmps = sd, tmpt = td;
        if (S[i] == '1')
            tmps--;
        else
            tmps++;
        if (T[i] == '1')
            tmpt--;
        else
            tmpt++;

        if (abs(tmps - tmpt) < abs(sd - td)) {
            U[i] = '1';
            sd = tmps;
            td = tmpt;
        }

        if (sd == td) {
            ok = 1;
            break;
        }
    }

    reverse(all(U));
    string ans = U;
    if (!ok)
        ans = "-1";
    cout << ans << endl;
}