問題概要

長さ n の 01 文字列 s が与えられる。一部の文字は ? となっており、これらを 0 または 1 に置き換える必要がある。

良い配置とは、1 ≤ i < n を満たす異なる i がちょうど m 個存在し、かつ s[i] ≠ s[i+1] となるものをいう。

すべての良い配置の中で辞書順最小のものを求めよ。解が存在しない場合は Impossible を出力せよ。

解法

まず、現在の文字列における隣接する異なる文字の数を w とする。

補題

任意の 1 < i < n に対して、s[i] を反転させた場合、w の偶奇は変化しない。これは以下の8つのケースで確認できる：

• 101 → 111: w = w - 2
• 111 → 101: w = w + 2
• 010 → 000: w = w - 2
• 000 → 010: w = w + 2
• 100 → 110: w = w
• 110 → 100: w = w
• 011 → 001: w = w
• 001 → 011: w = w

したがって、w の偶奇を変えるには、s[1] または s[n] を変更するしかない。

解法1

s[1] と s[n] を固定することで、w の偶奇を考慮する必要がなくなる。

文字列全体において、w の取りうる最大値 w₁ と最小値 w₂ を求める。

補題より、w₁ - w₂ は常に偶数であるため、(m - w₂) が奇数であれば、w = m となる配置は存在しない。

連続する ? の区間について、その両端の文字を基準に w₁ と w₂ を計算する：

• 両端が同じ文字の場合：w₂ = 0。区間長が偶数なら w₁ = len、奇数なら w₁ = len + 1。
• 両端が異なる文字の場合：w₂ = 1。区間長が偶数なら w₁ = len + 1、奇数なら w₁ = len。

辞書順最小の解を得るために、すべての ? を 0 で埋めた状態から開始し、必要に応じて後ろから 1 に変更していく。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000010;
int T, N, M;
int val[MAXN], pos[MAXN], seg_cnt, unk_cnt;
bool solved = false;
int max_diff, min_diff;
struct Segment {
    int left, right;
} seg[MAXN];

void reset() {
    seg_cnt = unk_cnt = solved = 0;
}

void output_result(int arr[]) {
    for (int i = 1; i <= N; ++i)
        cout << arr[i];
    cout << "\n";
}

void attempt(int fix_l, int val_l, int fix_r, int val_r) {
    max_diff = min_diff = 0;
    static int temp[MAXN];
    for (int i = 1; i <= N; ++i)
        temp[i] = val[i];

    if (fix_l) temp[fix_l] = val_l;
    if (fix_r) temp[fix_r] = val_r;

    for (int i = 1; i < N; ++i) {
        if (temp[i] != 2 && temp[i+1] != 2 && temp[i] != temp[i+1]) {
            min_diff++;
            max_diff++;
        }
    }

    for (int i = 1; i <= seg_cnt; ++i) {
        int len = seg[i].right - seg[i].left - 1;
        max_diff += len;
        if (temp[seg[i].left] == 1 && temp[seg[i].right] == 1)
            max_diff += (len % 2 == 1) ? 1 : 0;
        else if (temp[seg[i].left] == 0 && temp[seg[i].right] == 0)
            max_diff += (len % 2 == 1) ? 1 : 0;
        else
            max_diff += (len % 2 == 1) ? 0 : 1, min_diff += 1;
    }

    if (M < min_diff || M > max_diff || (M - min_diff) % 2 != 0)
        return;

    int current = 0;
    for (int i = 1; i <= unk_cnt; ++i)
        temp[pos[i]] = 0;

    for (int i = 1; i < N; ++i)
        if (temp[i] != temp[i+1])
            current++;

    if (current == M) {
        output_result(temp);
        solved = true;
        return;
    }

    if (current < M) {
        for (int i = unk_cnt; i >= 1 && current < M; --i) {
            if (temp[pos[i]-1] == 0 && temp[pos[i]+1] == 0) {
                temp[pos[i]] = 1;
                current += 2;
            }
        }
        if (current == M) {
            output_result(temp);
            solved = true;
        }
        return;
    }

    if (current > M) {
        for (int i = seg_cnt; i >= 1 && current > M; --i) {
            if (temp[seg[i].left] == 1 && temp[seg[i].right] == 1) {
                for (int j = seg[i].left + 1; j < seg[i].right; ++j)
                    temp[j] = 1;
                current -= 2;
            }
        }
        if (current == M) {
            output_result(temp);
            solved = true;
        }
    }
}

void solve() {
    reset();
    cin >> N >> M;
    string str;
    cin >> str;

    for (int i = 1; i <= N; ++i)
        val[i] = (str[i-1] == '?') ? 2 : str[i-1] - '0';

    bool in_seg = false;
    int last_pos = 1;
    for (int i = 2; i < N; ++i) {
        if (val[i] == 2) {
            pos[++unk_cnt] = i;
            in_seg = true;
        } else {
            if (in_seg) {
                seg[++seg_cnt].left = last_pos;
                seg[seg_cnt].right = i;
            }
            last_pos = i;
            in_seg = false;
        }
    }
    if (in_seg) {
        seg[++seg_cnt].left = last_pos;
        seg[seg_cnt].right = N;
    }

    if (val[1] == 2 && val[N] == 2) {
        attempt(1, 0, N, 0);
        if (solved) return;
        attempt(1, 0, N, 1);
        if (solved) return;
        attempt(1, 1, N, 0);
        if (solved) return;
        attempt(1, 1, N, 1);
        if (solved) return;
        cout << "Impossible\n";
        return;
    }

    if (val[1] == 2) {
        attempt(1, 0, 0, 0);
        if (solved) return;
        attempt(1, 1, 0, 0);
        if (solved) return;
        cout << "Impossible\n";
        return;
    }

    if (val[N] == 2) {
        attempt(0, 0, N, 0);
        if (solved) return;
        attempt(0, 0, N, 1);
        if (solved) return;
        cout << "Impossible\n";
        return;
    }

    attempt(0, 0, 0, 0);
    if (solved) return;
    cout << "Impossible\n";
}

int main() {
    cin >> T;
    while (T--)
        solve();
    return 0;
}

解法2

動的計画法を用いたより簡潔な解法。

maxn[i][j] を位置 j が i のときの s[j..n] における w の最大値、minn[i][j] を最小値とする。

遷移式：

• maxn[i][j] = max(maxn[i][j+1], maxn[1-i][j+1] + 1)
• minn[i][j] = min(minn[i][j+1], minn[1-i][j+1] + 1)

初期値：maxn[0][n+1] = maxn[1][n+1] = minn[0][n+1] = minn[1][n+1] = 0

位置 j に値 i を置ける条件：

• minn[i][j] ≤ res ≤ maxn[i][j]
• (res - minn[i][j]) が偶数（ただし s[n] が ? の場合は除く）

ただし、s[j] が ? でない場合、対応する不適切な値の maxn/minn を極端な値に設定する。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;
const int MAXN = 1000010;
int T, N, M;
int s[MAXN];
int dp_max[2][MAXN], dp_min[2][MAXN];

bool can_place(int idx, int val) {
    int target = M;
    if (idx > 1 && val != s[idx-1])
        target--;
    if (target < dp_min[val][idx] || target > dp_max[val][idx])
        return false;
    if (s[N] != 2 && (target - dp_min[val][idx]) % 2 == 1)
        return false;
    return true;
}

void solve() {
    cin >> N >> M;
    string str;
    cin >> str;

    for (int i = 1; i <= N; ++i)
        s[i] = (str[i-1] == '?') ? 2 : str[i-1] - '0';

    dp_max[0][N+1] = dp_max[1][N+1] = 0;
    dp_min[0][N+1] = dp_min[1][N+1] = 0;

    for (int i = N; i >= 1; --i) {
        dp_max[0][i] = max(dp_max[0][i+1], dp_max[1][i+1] + 1);
        dp_min[0][i] = min(dp_min[0][i+1], dp_min[1][i+1] + 1);
        dp_max[1][i] = max(dp_max[1][i+1], dp_max[0][i+1] + 1);
        dp_min[1][i] = min(dp_min[1][i+1], dp_min[0][i+1] + 1);

        if (s[i] == 0) {
            dp_max[1][i] = -INF;
            dp_min[1][i] = INF;
        } else if (s[i] == 1) {
            dp_max[0][i] = -INF;
            dp_min[0][i] = INF;
        }
    }

    if (!can_place(1, 0) && !can_place(1, 1)) {
        cout << "Impossible\n";
        return;
    }

    for (int i = 1; i <= N; ++i) {
        if (can_place(i, 0))
            s[i] = 0;
        else
            s[i] = 1;
        if (i > 1 && s[i] != s[i-1])
            M--;
    }

    for (int i = 1; i <= N; ++i)
        cout << s[i];
    cout << "\n";
}

int main() {
    cin >> T;
    while (T--)
        solve();
    return 0;
}