解法

よくない形になってるところを解消して回るやつ。 MSBからそれぞれ処理していき上に伝播させていく。 $0, 1$だけでなく$2$も許すと実装が楽。 $O(N + M + K)$。

問題で指示されているのは「次を$K$回やれ: bit積 $Z = X \And Y$ とおいて加算 $X \gets X + Z$ と $Y \gets Y + Z$ で更新する」。 愚直にやると定数倍が小さいとはいえ $O(KN)$。 いくつか観察をしよう。 まずbit積の性質から $X_i = Y_i = 1$ であるような位置$i$にのみ注目すればよいことが分かる。 さらにそのような位置から影響は上側に伝播していく。 他の $j \gt i$ を見たとき $X_j = Y_j = 0$ なら気にしなくてよい。 $X_j = Y_j = 1$ なら $j$ についても同様に等速で伝播が発生するので $X_j = Y_j = 0$ と同じとみなせる。 一方 $X_j \ne Y_j$ なら問題で、繰り上がりの処理が発生する。

ここまでにより位置$i$を上からやっていくとよさそうという気持ちになる。 ここである種の転置も隠れていることに注意。 つまり「すべての位置$i$について処理することを$K$回やる」のでなくて「位置$i$を上から順に見て順番に$K$回処理する」。 計算量が不安ではあるがいけそうな気がするので実装すると通る。 たぶん証明もできるがそこそこ手間そう。

メモ

  • 体感$900$点 (解けたので)
  • いつもこういうのカット除去ぽいなあってなりながら解いてる

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = int(n) - 1; (i) >= 0; -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

pair<string, string> solve(int n, int m, int k, string s, string t) {
    reverse(ALL(s));
    reverse(ALL(t));
    REP (i, m + k + 100) s.push_back('0');
    REP (j, n + k + 100) t.push_back('0');

    stack<int> stk;
    function<void (int, int)> go = [&](int i, int k1) {
        assert (k1 >= 0);
        if (not stk.empty()) {
            assert (stk.top() >= i);
            if (stk.top() == i) stk.pop();
        }

        if (s[i] == '1' and t[i] == '1') {
            if (k1 == 0) {
                // nop
            } else {
                s[i] = '0';
                t[i] = '0';
                int j = stk.empty() ? INT_MAX : stk.top();
                if (k1 < j - i) {
                    assert (s[i + k1] == '0');
                    assert (t[i + k1] == '0');
                    s[i + k1] = '1';
                    t[i + k1] = '1';
                } else {
                    stk.pop();
                    s[j] += 1;
                    t[j] += 1;
                    go(j, k1 - (j - i));
                }
            }

        } else if (s[i] == '1' and t[i] == '0') {
            stk.push(i);

        } else if (s[i] == '0' and t[i] == '1') {
            stk.push(i);

        } else if (s[i] == '0' and t[i] == '0') {
            // nop

        } else if (s[i] == '2' and (t[i] == '0' or t[i] == '1')) {
            s[i] = '0';
            s[i + 1] += 1;
            go(i + 1, k1);
            if (t[i] == '1') stk.push(i);

        } else if ((s[i] == '0' or s[i] == '1') and t[i] == '2') {
            t[i] = '0';
            t[i + 1] += 1;
            go(i + 1, k1);
            if (s[i] == '1') stk.push(i);

        } else {
            assert (false);
        }
    };
    REP_R (i, n + m) {
        go(i, k);
    }

    while (s.back() == '0') s.pop_back();
    while (t.back() == '0') t.pop_back();
    reverse(ALL(s));
    reverse(ALL(t));
    return make_pair(s, t);
}

int main() {
    int n, m, k; cin >> n >> m >> k;
    string s; cin >> s;
    string t; cin >> t;
    tie(s, t) = solve(n, m, k, s, t);
    cout << s << endl;
    cout << t << endl;
    return 0;
}