[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) C. Binary String Reconstruction

2020年9月4日2020年12月13日

問題

方針

文字列 \( w \) と自然数 \( x \) が与えられたとき次の条件を満たす文字列 \( w \) を答えます。

1. \( i – x \geq 0 \wedge w_{i-x} = 1 \) ならば \( s_i = 1 \)
2. \( i + x \leq n \wedge w_{i+x} = 1 \) ならば \( s_i = 1 \)
3. 1 と 2 を両方満たさないとき \( s_i = 0\)

まず初めに、\( w \) を 1 だけからなる文字列とします。条件 3 から、\( s_i = 0\) となる整数 \( i \) に対して、\( w_{i -x} = 0 \) 、\( w_{i + x} = 0 \) とします。

次に、\( s_{i} = 1 \) となる整数 \( i \) に対して、 \( w_{i – x} = 1 \vee w_{i + x} = 1 \) を満たす \( i \) が存在するとき、条件を満たす文字列は存在しますが、そうではないとき答えは-1となります。

コード

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

string solve(int n, int x, string s) {
    string w(n, '1');
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') {
            if (i - x >= 0) w[i - x] = '0';
            if (i + x < n) w[i + x] = '0';
        }
    }
    for (int i = 0; i < n; i++) {
        if (s[i] == '0') continue;
        if (i - x >= 0 && w[i - x] == '1') continue;
        if (i + x < n && w[i + x] == '1') continue;
        return "-1";
    }
    return w;
}

int main() {
    int t;
    cin >> t;
    string ans[t];
    string s;
    int x;
    for (int i = 0; i < t; i++) {
        cin >> s >> x;
        ans[i] = solve(s.length(), x, s);
    }
    for (string i : ans) {
        cout << i << "\n";
    }
    return 0;
}